排序算法七——快速排序

旧城等待， 2022-06-10 04:57 189阅读 0赞

# **排序算法七：快速排序** #

快速排序的大致思想是：先随便选一个值，然后比这个值小的放在它左边，比它大的放在它右边。这样这组数字就被分成了两组， 然后再在左边那一组数字里面选一个值，比这个值大的放在它左边，比这个值大的放在它右边。就这样一直递归调用自己，到最后只剩一个值的时候，整组数都排好序了。  
算法有两个函数，函数Quick\_sort跟函数Partition， 函数Quick\_sort主要用来递归调用自己，最主要的函数Partition是用来随机取键值，然后把一组数分成两组，再返回键值的位置。

**下图是我画了一个多小时的图解：（自我感觉画的很清楚 ）**  
画到后面就没画小框框了。

![这里写图片描述][SouthEast]  
![这里写图片描述][SouthEast 1]

**这个图是只画了第一次找键值位置的图解，下面每次找键值位置都跟这个一样，只不过一直都在递归调用。**

**快速排序代码：**

File name:7quick_sort.c
    
         Author: Tang Zhiqian
    
          Date:2017-08-10 11:04
    *****************************************************/
    //快速排序
    
    #include <stdio.h>
    
    #define MAX 10
    
    typedef int ElementType;
    typedef ElementType ARR[MAX];
    
    ARR arr = {
       6,9,1,7,5,8,3,0,4,2};
    void QuickSort(ARR arr,int low,int high);
    int Partition(ARR arr,int low,int high);
    void print(ARR arr);
    
    int main()
    {
    
        QuickSort(arr,0,MAX - 1);
        print(arr);
    
        return 0;
    }
    
    void QuickSort(ARR arr,int low,int high)
    {
        int pivot;    //轴枢的位置
        if (low < high)
        {
            pivot = Partition(arr,low,high);
    
            QuickSort(arr,low,pivot - 1);    //对低子表快速排序
            QuickSort(arr,pivot + 1,high);    //对高子表快速排序
        }
    }
    
    int Partition(ARR arr,int low,int high)
    {
        int pivotkey;    //枢轴的值
        pivotkey = arr[low];   //我们枢轴取第一个值
        while(low < high)
        {
            while(low < high && arr[high] >= pivotkey)   //必须从high开始比，因为开始arr[low]等于pivot
            {
                high--;
            }
            //出了这个while说明 arr[high] 小于枢轴的值
    
            arr[low] = arr[high];    //把high的值赋值给low
    
            while(low < high && arr[low] <= pivotkey)
            {
                low++;
            }
            //出了这个while说明arr[low] 大于枢轴的值，它在低位不能比枢轴数字大，所以要移动
    
            arr[high] = arr[low];    //所以把此时low的值赋值给high。此时的high就是刚刚赋值给上一个low的位置
                                     //迷糊的很啊
        }
    
        arr[low] = pivotkey;    //当low跟high一样的时候，跳出大的while循环，然后把枢轴的值放进去
        print(arr);
    
        return low;    //返回枢轴的位置
    }
    
    void print(ARR arr)
    {
        int i;
        for (i = 0; i < MAX; i++)
        {
            printf("%d ",arr[i]);
        }
        printf("\n");
    }

程序运行结果：  
![这里写图片描述][SouthEast 2]

看第一次排完序是不是：2 4 1 0 5 3 6 8 7 9，跟我上面图解的结果一样滴！  
美滋滋。

时间复杂度O（nlogn），空间复杂度也是O（nlogn）,因为递归用到栈空间。  
还有就是稳定性，快速排序不是稳定的排序，看我画的图就知道了，值是跳来跳去的，跳跃性传递。

[SouthEast]: /images/20220610/a71b36cb8dec4e66a5b4613bbf135cae.png
[SouthEast 1]: /images/20220610/8477233934254c529d4c40538aa693c3.png
[SouthEast 2]: /images/20220610/425c6c4c67f2483b86957320093f5487.png