排序方法（4）：快速排序

港控/mmm° 2022-05-28 13:36 73阅读 0赞

# 快速排序 #

参考：  
[https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95][https_baike.baidu.com_item_E5_BF_AB_E9_80_9F_E6_8E_92_E5_BA_8F_E7_AE_97_E6_B3_95]

[http://cuijiahua.com/blog/2017/12/algorithm\_4.html][http_cuijiahua.com_blog_2017_12_algorithm_4.html]

## 一、原理 ##

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

## 二、步骤 ##

设要排序的数组是A\[0\]……A\[N−1\]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。  
一趟快速排序的算法是：  
\- 1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；  
\- 2）以第一个数组元素作为关键数据，赋值给key，即key=A\[0\]；  
\- 3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A\[j\]，将A\[j\]和A\[i\]互换；  
\- 4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A\[i\]，将A\[i\]和A\[j\]互换；  
\- 5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A\[j\]不小于key,4中A\[i\]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

## 三、例子 ##

假设有一组数\{6,10,1,2,8,5,9,7,3,4,0\}

下标    0    1    2    3    4    5    6    7    8    9    10
    数据    6    10   1    2    8    5    9    7    3    4    0

此时i=0,j=10,key=6

从右边开始把比key小的值与0位的6进行换位操作。因此对于上述例子，右边第一个数为0，比6小，进项换位操作，完成第一次比较：

下标    0    1    2    3    4    5    6    7    8    9    10
    数据    0    10   1    2    8    5    9    7    3    4    6

此时i=0，j=10,key=6

接着进行第二次比较，从左边开始把比6大的数字与6进行换位操作，完成第二次比较：

下标    0    1    2    3    4    5    6    7    8    9    10
    数据    0    6    1    2    8    5    9    7    3    4    10

上面两次比较是一个循环，接下来递减变量j和i,只需要不断的重复上面的操作，直至i=j为止。

然后，对key两边的数据，再分组分别进行上述的过程，直到不能再分组为止。

## 四、算法实现 ##

### C语言 ###

#include "stdio.h"
    
    void quick_sort(int a[], int left, int right);
    
    void quick_sort(int a[], int left, int right)
    {
        if (left >= right)
        {
            return;
        }
        int i = left;
        int j = right;
        int key = a[left];
    
        while (i < j)
        {
            while (i < j && key <= a[j])            
            {
                j--;
            }
            a[i] = a[j];
            while (i < j && key >= a[i])
            {
                i++;
            }
            a[j] = a[i];
        }
        a[i] = key;
        quick_sort(a, left, i - 1);
        quick_sort(a, i + 1, right);
    }
    
    int main()
    {
            int number[] = { 6,10,1,2,8,5,9,7,3,4,0 };
            int i;
            int n = sizeof(number) / sizeof(number[0]);
            printf("原始数据：\n");
            for (i = 0; i < n; i++)
            {
                printf("%d\t", number[i]);
            }
            printf("\n\n");
    
            quick_sort(number, 0,n-1);
            printf("\n返回结果：\n");
            for (i = 0; i < n; i++)
            {
                printf("%d\t", number[i]);
            }
            printf("\n");
    }

### 运行结果 ###

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

[https_baike.baidu.com_item_E5_BF_AB_E9_80_9F_E6_8E_92_E5_BA_8F_E7_AE_97_E6_B3_95]: https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
[http_cuijiahua.com_blog_2017_12_algorithm_4.html]: http://cuijiahua.com/blog/2017/12/algorithm_4.html
[SouthEast]: /images/20220528/675b5b4162b348219ab8aa5bc6270573.png