快速排序c程序

Question

我最近通过https://www.geeksforgeeks.org/quick-sort/学习了快速排序，但发现很难理解。因此，据我所知，编写了以下程序。

#include <stdio.h>
void quick_sort(int[],int,int);
int main(){
    int arr[100];
    int n;
    printf("Enter the elements :");
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i++){
        printf("%d:",i+1);
        scanf("%d",&arr[i]);
    }
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    for(int i = 0; i < n; i++){
        printf("%d ",arr[i]);
    }
    printf("\n");

    quick_sort(arr,0,n - 1);

    for(int i = 0; i < n; i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}


void quick_sort(int arr[],int pivot_, int right_){
    //Base condtion.
    if(pivot_ == right_ )//pivot = left = right == no more check
        return;
    int i ;
    int pivot, left ,right;
    pivot = pivot_;//first element...
    right = right_;//last element...
    left = pivot + 1; // second element.
    int middle;
    while( left <= right ){
        if(arr[left] >= arr[pivot]){
            if(arr[right] <= arr[pivot]){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                right --;
                left ++;
            }else{
                right --; // left > pivot but right !< pivot
            }
        }else{
            left ++;// left is not > pivot.
        }
    }
    i = pivot + 1;
    while(arr[i] < arr[pivot]) i++;
    i--; // last smaller value than pivot encountered.
    middle = i; // swappppppp..
    int temp = arr[pivot];
    arr[pivot] = arr[i];
    arr[i] = temp;
    // now left of i is less than pivot and right of is greater than pivot. 

    quick_sort(arr,0,middle);
    quick_sort(arr,middle + 1,right_);
}

Answer 1

这是一种从单元测试中获益的功能。我用C++和GoogleTest编写了一些简单的测试：

extern "C" {
    void quick_sort(int arr[],int pivot_, int right_);
}

#include <gtest/gtest.h>

#include <algorithm>
#include <iterator>
#include <numeric>

TEST(quick_sort, empty)
{
    int a[1] = {};
    quick_sort(a, 0, 0-1);
    EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

TEST(quick_sort, one_element)
{
    int a[] = { 0 };
    quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
    EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

TEST(quick_sort, two_same)
{
    int a[] = { 0, 0 };
    quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
    EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

TEST(quick_sort, two_asc)
{
    int a[] = { 0, 1 };
    quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
    EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

TEST(quick_sort, two_desc)
{
    int a[] = { 1, 0 };
    quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
    EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

TEST(quick_sort, three_123)
{
    int a[] = { 1, 2, 3 };
    quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
    EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

TEST(quick_sort, three_231)
{
    int a[] = { 2, 3, 1 };
    quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
    EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

TEST(quick_sort, three_312)
{
    int a[] = { 3, 1, 2 };
    quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
    EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

TEST(quick_sort, four)
{
    int a[] = { 3, 1, 2, 0 };
    quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
    EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

TEST(quick_sort, large)
{
    int a[100];
    std::iota(std::rbegin(a), std::rend(a), -50);
    quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
    EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

这首先强调的是不寻常的调用约定-- right_是一个包容的绑定，但是没有任何指导，大多数C代码都会期望有一个排他性绑定。

(顺便说一句，我还要指出，pivot_对大多数调用者来说并不是很有意义--我认为left是一个更好的名字选择。)

我们看到的第二件事(通过在Val差伦下运行)是当我们在这里运行数组的末尾时，未定义的行为：

    while(arr[i] < arr[pivot]) i++;

在此代码准备就绪之前，需要对其进行修复。

Answer 2

1)“比较”函数在哪里? 2)快速排序()函数的原型缺少该参数

发布的代码(充其量)只能处理整数数组。也就是说，它不会处理结构数组或字符串数组，等等。

有关:printf(“输入元素:")；scanf("%d"，&n)；这不能通知用户输入的第一个数字实际上是以下数字的数目。

代码不起作用！

下面是发布代码的典型运行：

Enter the elements :3
1:3
2:2
3:1
3 2 1 

然后，所发布的代码会使CPU最大，并且不会完成排序。