快速排序用C [英] quick sort in C

问题描述

我试图用快速排序为我的项目，但它不工作。我不能揣摩出bug是。人谁可以帮我指点迷津？谢谢你。

 无效快速排序（INT ARR []，int类型的，INT B）{
    如果（一个或下; = b）的{
        INT键= ARR [A];
        INT指数= A;
        INT I =一，J = B;
        而（ⅰ＆下; = j）条{
            对于（;常用3 [J]＆GT;钥匙;  -  J）;
            INT TEMP = ARR [J]。
            ARR [J] =键;
            ARR [指数] =温度;
            指数= j的;
            为（;常用3 [1]  - ;密钥; ++ i的）;
            TEMP = ARR [I]
            改编[I] =键;
            ARR [指数] =温度;
            指数= I;
            }
        快速排序（ARR，A指数）;
        快速排序（ARR，指数，B）;
        }
    否则返回;
}
 

解决方案

您内环做到这一点：

• 从数组的右手边检查发现，应该是键左侧的元素。


• 插拔找到的元素与键，位于首页和更新首页到键的新位置


• 从阵列的左手侧的检查发现，应该是键右边的元素。


• 插拔找到的元素与键，位于首页和更新首页到键的新位置

在世界上，为什么你想做到这一点？你应该这样做：

• 从数组的右手边检查发现，应该是键左侧的元素。


• 从阵列的左手侧的检查发现，应该是键右边的元素。


• 如果找到，交换他们。如果没有，就把枢轴在合适的位置，然后退出环

我不是100％肯定，但我认为在你的快速排序版本洗牌键周围可能是你的问题的罪魁祸首。找出最好的办法是一步地调试code步骤，看看它出了问题。

下面是实施根据上述我的建议，有一些测试案例在一起：

 无效掉期（INT ARR []，INT I，诠释J）{
    INT TEMP = ARR [J]。
    ARR [J] =改编[I]
    改编[I] =温度;
}无效quicksort0（INT ARR []，int类型的，INT B）{
    如果（一个或GT; = b）的
        返回;    INT键= ARR [A];
    INT I = A + 1，J = B;
    而（I＆LT; j）条{
        而（I＆LT; J＆安培;＆安培;常用3 [J]＆GT; =键）
            --j;
        而（ⅰ＆所述; J＆放大器;＆放大器;常用3 [1]  -  =键）
            ++我;
        如果（ⅰ＆所述; j）条
            掉期（ARR，I，J）;
    }
    如果（改编[一个]≥常用3 [I]）{
        掉期（ARR，A，I）;
        quicksort0（ARR，A，I  -  1）;
        quicksort0（ARR，I + 1，B）;
    }否则{//没有左手侧
        quicksort0（ARR，A + 1，B）;
    }
}无效快速排序（INT ARR []，INT LEN）{
    quicksort0（ARR，0，LEN  -  1）;
}诠释主（）{
    INT A1 [] = {};
    INT A2 [] = {1};
    INT A3 [] = {1,1};
    INT A4 [] = {1，2，3，4，5};
    INT A5 [] = {5,4，3，2，1};
    INT A6 [] = {9,2，6，7，5,4，0,2，7,5};    快速排序（A1，0）;
    快速排序（A2，1）;
    快速排序（A3，2）;
    快速排序（A4，5）;
    快速排序（A5，5）;
    快速排序（A6，10）;
    快速排序（A6，10）;
}
 

I'm trying to use quick sort for my project but it doesn't work. And I can't figure out where the bug is. Anyone who can help me figure it out? Thank you.

void quicksort(int arr[],int a, int b){
    if(a<=b){
        int key=arr[a];
        int index=a;
        int i=a, j=b;
        while(i<=j){
            for(;arr[j]>key;--j);
            int temp=arr[j];
            arr[j]=key;
            arr[index]=temp;
            index=j;
            for(;arr[i]<key;++i);
            temp=arr[i];
            arr[i]=key;
            arr[index]=temp;
            index=i;
            }
        quicksort(arr,a,index);
        quicksort(arr,index,b);
        }
    else return;
} 

解决方案

Your inner loop does this:

• Check from the right-hand-side of the array to find an element that should be on the left side of key.
• Swap any found element with key, located at index and update index to key's new location
• Check from the left-hand-side of the array to find an element that should be on the right side of key.
• Swap any found element with key, located at index and update index to key's new location

Why in the world would you want to do this? You should do this:

• Check from the right-hand-side of the array to find an element that should be on the left side of key.
• Check from the left-hand-side of the array to find an element that should be on the right side of key.
• If found, swap them. If not, put the pivot in the right position and exit loop

I'm not 100% sure, but I think that shuffling the key around in your version of quicksort may be the culprit of your problem. The best way to find out is to debug your code step by step and see where it goes wrong.

Here's the implementation according to my suggestion above, together with a few test-cases:

void swap(int arr[], int i, int j) {
    int temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}

void quicksort0(int arr[], int a, int b) {
    if (a >= b)
        return;

    int key = arr[a];
    int i = a + 1, j = b;
    while (i < j) {
        while (i < j && arr[j] >= key)
            --j;
        while (i < j && arr[i] <= key)
            ++i;
        if (i < j)
            swap(arr, i, j);
    }
    if (arr[a] > arr[i]) {
        swap(arr, a, i);
        quicksort0(arr, a, i - 1);
        quicksort0(arr, i + 1, b);
    } else { // there is no left-hand-side
        quicksort0(arr, a + 1, b);
    }
}

void quicksort(int arr[], int len) {
    quicksort0(arr, 0, len - 1);
}

int main() {
    int a1[] = { };
    int a2[] = { 1 };
    int a3[] = { 1, 1 };
    int a4[] = { 1, 2, 3, 4, 5 };
    int a5[] = { 5, 4, 3, 2, 1 };
    int a6[] = { 9, 2, 6, 7, 5, 4, 0, 2, 7, 5 };

    quicksort(a1, 0);
    quicksort(a2, 1);
    quicksort(a3, 2);
    quicksort(a4, 5);
    quicksort(a5, 5);
    quicksort(a6, 10);
    quicksort(a6, 10);
}

这篇关于快速排序用C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！