经典算法之快速排序

算法

字数统计: 860阅读时长: 3 min

 2018/06/02   Share

前言

快速排序法在众多时间复杂度为N*logN的排序方法中效率极高，因此经常被使用。例如java中的Arrays.sort()还有python中的sort()都是采用优化过后的快速排序法。
要直接写出快速排序法并不简单，因此我写了这篇文章来谈谈对快速排序法的理解。

实现

快速排序是由C. A. R. Hoare在1962年提出的，是对冒泡排序法的一种改进。它的基本思想是：
1.从数组中取出一个数作为比较数。(一般为区间第一个数)
2.分区。将比这个数大的数放在它的右边，小于等于它的数放在左边。
3.再对左右两个分区进行第二步，知道各个分区只有一个数。
举个小数组的例子：

0	1	2	3	4	5	6	7
67	3	54	23	41	78	12	73

初始时，i=0,j=7,X=a[i]=67 由于X等于第一个数，相当于在a[0]上挖了一个坑，可以将其他位置的数填到这里。接着从j开始向前找到一个比X小或相等的数。当j=6时，条件符合。将a[6]的值赋给a[0]。然后i++。这样又在a[6]上挖了一个坑。之后再从i开始找到一个比X大的数，当i=5符合条件，将a[6]=a[5],j- -。此时数组变为：

0	1	2	3	4	5	6	7
12	3	54	23	41	78	78	73

i=5,j=5,X=67；如果i与j不相等，则重复上面的步骤，先从后往前找，再从前往后找。当i==j时退出。然后将X的值填入下标i中。此时可以发现，在a[5]之前的数都小于它，在a[5]之后的数都大于它。之后再对0--4和6--7两个子区间进行上述步骤即可。 # 代码由此我们便可写出挖坑填数的代码：

int AdjustArray(int a[], int left, int right) //返回i==j时的数组下标
{  
    int i = left, j = right;  
    int x = a[left]; //a[left]即为第一个数  
    while (i < j)  
    {  
        // 从右向左找小于x的数来填a[i]  
        while(i < j && a[j] >= x)   
            j--;    
        if(i < j)   
        {  
            a[i] = a[j]; //将a[j]填到a[i]中，a[j]就形成了一个新的坑
            i++;  
        }  
  
        // 从左向右找大于或等于x的数来填a[j]  
        while(i < j && a[i] < x)  
            i++;    
        if(i < j)   
        {  
            a[j] = a[i]; //将a[i]填到a[j]中，a[i]就形成了一个新的坑  
            j--;  
        }  
    }  
    //退出时，i等于j。将x填到这个坑中。  
    a[i] = x;  
  
    return i;  
} 
void quick_sort(int a[], int left, int right)  
{  
    if (left < right)  
    {  
        int i = AdjustArray(a, left, right);//先成挖坑填数法调整a[]  
        quick_sort(a, left, i - 1); // 递归调用   
        quick_sort(a, i + 1, right);  
    }  
}

对代码优化之后即可得到简洁的快速排序法：

void quick_sort(int a[], int left, int right)  
{  
    if (left < right)  
    {  
        int i = left, j = right, x = a[left];  
        while (i < j)  
        {  
            while(i < j && a[j] >= x) // 从右向左找第一个小于x的数  
                j--;    
            if(i < j)   
                a[i++] = a[j]; //也可以不i++，无影响，下面j--同理
              
            while(i < j && a[i] < x) // 从左向右找第一个大于等于x的数  
                i++;    
            if(i < j)   
                a[j--] = a[i];  
        }  
        a[i] = x;  
        quick_sort(a, left, i - 1); // 递归调用   
        quick_sort(a, i + 1, right);  
    }  
}

快速排序法在理解上并不是很难，网上还有许多优化过的版本，这里不再细谈。

原文作者：Zer0e

原文链接：https://re0.top/2018/06/02/quicksort/

发表日期：六月 2日 2018, 7:20:28 晚上

更新日期：June 15th 2020, 9:35:36 pm

Next Post

经典算法之归并排序
Previous Post

Linux下反弹shell的几种方式

CATALOG

1. 前言
2. 实现

