快速排序的两种实现方法(c语言版本)

不念不忘少年蓝@ 2022-03-02 12:26 206阅读 0赞

经过调研发现，对任意无序整数数组，快速排序有两种实现方法，这里简单阐述下思路：

思路一：随意选择一个基准元，一般选择数组的起始元或末尾元，Weiss这本书上特意搞了个算法来选择基准元，……，总之就是基准元的选择要尽量随机。选定基准元之后，比如选择数组起始元为基准元，从数组右边开始，向左边遍历，遇到比基准元大的跳过，直至遇到比基准元小的元素停下来；再从左边向右边遍历，跳过比基准元小的，直至遇到比基准元大的元素停下来，交换左右两边的元素，再重复之前的遍历，比较和交换步骤，……，这样经过一趟排序就能将整个数组划分为两个部分，左边的部分小于基准元，右边的部分大于基准元，使用“二分法”和递归的思想，我们就能最终快速完成整个数组的排序，借用网上的效果动态如下：

![20190320151833851.gif][]

啊哈磊的这篇文章对快速排序的思想做了非常深入浅出的描述，感兴趣的读者可以看看

[http://bbs.ahalei.com/thread-4419-1-1.html][http_bbs.ahalei.com_thread-4419-1-1.html]

思路二：在不方便从数组最右端向最左端遍历的情形下，比如超长单向链表只有next指针，只能往前遍历不能往后遍历，此时还有一种变通方法，就是，选择数组的首个元素为基准元，使用两个索引，一快一慢，索引1从首个元素的前一个开始(索引为-1)，索引2遍历数组每个元素，发现比基准元小的元素，就让索引1增加1，如果发现两个索引不相等，就交换两个对应两个元素的值，这样的效果等价于把数组分为两部分，比基准元大的部分在基准元的右边，比基准元小的部分在基准元的左边，同样按照“二分法”和递归思想，最后完成整个数组的排序。

下面给出这两种思路的算法实现源码

//description: 给出快速排序的两种实现形式
    //date: 2019-03-16
    
    #include <stdio.h>
    #include <stdlib.h>
    
    int RandomInRange(int min, int max){
        int random = rand()%(max-min+1) + min;
        return random;
    }
    
    int swap(int* a, int* b){
        int tmp = *b;
        *b = *a;
        *a = tmp;
    }
    
    //利用三点确定基准点
    int Median3(int arr[], int left, int right){
        int center = (left+right)/2;
        //使left，center，right升序
        if(arr[left]>arr[center])
            swap(&arr[left], &arr[center]);
        if(arr[left]>arr[right])
            swap(&arr[left], &arr[right]);
        if(arr[center]>arr[right])
            swap(&arr[center], &arr[right]);
    
        //隐藏基准点
        swap(&arr[center], &arr[right-1]);
        return arr[right-1];
    }
    
    int Partition(int arr[], int n, int start, int end){
        if(arr==NULL || n<=0 || start<0 || end >= n){
            printf("Invalid input params, exit ...");
            exit(-1);
        }
    
        //生成随机索引作为基准元素，并放到数组尾部
        int idx = RandomInRange(start, end);
        swap(&arr[idx], &arr[end]);
        //现在arr[end]就是基准元素了
    
        //设置两个索引, small表示比基准元素小的元素的索引
        int small = start - 1;
        for(idx=start; idx<end; idx++){
            if(arr[idx]<arr[end]){
                small++;
                //small指向比基准元素大的，idx指向比基准元素小的，两者交换一下
                if(small != idx)
                    swap(&arr[small], &arr[idx]);
            }
        }
        //将基准元素交换回来
        small++;
        swap(&arr[small], &arr[end]);
    
        return small;
    }
    
    //借用一段插入排序算法
    void InsertSort(int arr[], int n){
        int i,j,t;
        for(i=1; i<n; i++){
            t=arr[i];
            for(j=i; j>0 && t<arr[j-1]; j--){
                arr[j] = arr[j-1];
            }
            arr[j]=t;
        }
    }
    
    #define CutOff 3
    
    void Qsort(int arr[], int left, int right){
        int i,j,pivot;
    
        if(left+CutOff <= right){
            pivot = Median3(arr, left, right);
            i=left;
            j=right-1;
            for(;;){
                while(arr[++i]<pivot){}
                while(arr[--j]>pivot){}
                if(i<j)
                    swap(&arr[i], &arr[j]);
                else
                    break;
            }
            //恢复pivot
            swap(&arr[i], &arr[right-1]);
    
            Qsort(arr, left, i-1);
            Qsort(arr, i+1, right);
        }else{
            //对子数组做插入排序
            InsertSort(arr+left, right-left+1);
        }
    }
    
    //找数组中第k大的元素，即arr[k-1]元素
    void Qselect(int arr[], int k, int left, int right){
        int i,j,pivot;
    
        if(left+CutOff <= right){
            pivot = Median3(arr, left, right);
            i=left;
            j=right-1;
            for(;;){
                while(arr[++i]<pivot){}
                while(arr[--j]>pivot){}
                if(i<j)
                    swap(&arr[i], &arr[j]);
                else
                    break;
            }
            //恢复pivot
            swap(&arr[i], &arr[right-1]);
    
            if(k<=i)
                Qselect(arr, k, left, i-1);
            else if(k>i+1)
                Qselect(arr, k, i+1, right);
        }else{
            //对子数组做插入排序
            InsertSort(arr+left, right-left+1);
        }
    }
    
    void QuickSort2(int arr[], int n){
        Qsort(arr, 0, n-1);
    }
    
    
    void QuickSort(int arr[], int n, int start, int end){
        if(start == end)
            return;
    
        int pivot = Partition(arr, n, start, end);
        if(pivot>start)
            QuickSort(arr, n, start, pivot-1);
        if(pivot<end)
            QuickSort(arr, n, pivot+1, end);
    }
    
    int main(){
        int a[] = {4,12,35,98,4,44,58,13,15};
        int i, n=sizeof(a)/sizeof(int);
        //QuickSort(a, n, 0, n-1);
        //QuickSort2(a, n);
        Qselect(a, n/2, 0, n-1);
        printf("%d\n", a[n/2]);
    
        for(i=0; i<n; i++)
            printf("%d ", a[i]);
        printf("\n");
    
        return 0;
    }

下面是函数运行效果截图

![20190320154754756.png][]

**引申**

使用快速排序的思想，还可以高效解决“**查找第k大数**”的问题，特别是“**查找数组中位数**”的问题，这是后话，打算今后另做一篇博文分析。

[求无序数组的中位数(c语言版本)][c]

**参考文献**

\[1\]. Allen Weiss 《数据结构与算法分析---C语言描述》第2版第七章

\[2\].何海涛 《剑指Offer名企面试官精讲典型编程题》第2版p.80

[20190320151833851.gif]: /images/20220302/91fb1ce4e2564a5e800097cda9566326.png
[http_bbs.ahalei.com_thread-4419-1-1.html]: http://bbs.ahalei.com/thread-4419-1-1.html
[20190320154754756.png]: /images/20220302/a05587ed4766498da135786670a968b8.png
[c]: https://blog.csdn.net/tao_627/article/details/88743152