快排

原文：https://www.jianshu.com/p/7c19949272cd

Chapter3: 更好的查找与排序算法

2. 快速排序算法

1. 什么是快速排序算法

• 分解

  数组 A[p..r] 被划分为两个子数组 A[p...q-1] 和 A[q+1,r] , 使得 A[q] 为大小居中的数，左侧 A[p..q-1] 中的每个元素都 <= 它, 而右侧 A[q+1,r] 中的每个元素都 >= 它。其中计算下标 q 也是划分过程的一部分。

• 解决

  通过递归调用快速排序，分别对子数组 A[p...q-1] 和 A[q...r] 进行排序

• 合并

  不存在合并的问题

所以划分是问题的关键

2. 快排之单向扫描分区法

2.1 基本思想

2.1.1 快排函数

• 找主元
• 对主元左边进行快排(递归调用本函数)
• 对主元右边进行快排(递归调用本函数)
• 上面三步在begin<end 的条件下进行，出口为begin>=end 时

void quickSort(int* arr,int begin,int end){
    if(begin<end){
        int q=partition(arr,begin,end);
        quickSort(arr,begin,q-1);
        quickSort(arr,q+1,end);
    }
}

2.1.2 划分区间(确定主元)的函数

用两个指针将数组划分为3个区间：

• 扫描指针 sp 左边的元素小于主元，sp 初始化指向第二个元素
• 扫描指针 sp 到 第二个bp 指针之间的部分为未知的
• bp 指针之后的元素大于主元，bp 初始化指向最后一个元素

首先选取一个初始主元，这个主元的选取是有讲究的，为了简便起见，这里先选取第一个元素作为初始主元，之后哪怕是用别的方法选取主元，比如随机选取，也是随机选取一个数然后与第一个元素互换值，让主元位于第一个元素的位置

sp 指针初始指向第二个元素，将 sp 所指元素与主元比较，

• 如果这个元素比主元小，则将 sp 移到下一位置，即 sp++
• 如果这个元素比主元大，将该元素与bp 指针所指元素进行交换，bp 指针往前移一个位置，即 bp--

还剩下一个元素时，此时sp 之后是bp, bp 所指元素为尚未确定大小的元素，将sp 移动到该元素上(此时sp 与 bp 重合):

• 如果该元素比主元小，则bp 不动，sp 继续移动到下一位，此时sp 指针位于bp 指针后一位置， sp 指向了从左往右数第一个比主元大的元素, bp 指向了最后一个比主元小的元素
• 如果该元素比主元大，则 sp 不动，bp 移动前一位，此时bp 到了sp 的前一位，sp 指向了从左往右数第一个比主元大的元素, bp 指向了最后一个比主元小的元素
• 主元位置为第一个元素，要将主元交换到合适位置，应该把bp 所指元素与主元交换(因为bp 比主元小，适合交换到左边)

所以函数的出口就是sp > bp 时，即循环在while(sp<=bp) 条件下进行

2.2 代码

2.2.1 伪代码

//快排单向扫描法伪代码
QuickSort(Arr,p,r)
    if p<r
    q=Partition(Arr,p,r);//获取主元，将数组分为左右两部分
    QuickSort(Arr,p,q-1);//对左边递归调用快排
    QuickSort(Arr,q+1,r);//对左边递归调用快排
/*定位主元的函数
参数:Arr 输入数组，p本次要进行切分的起始位置，r本次要进行切分的结束位置
*/
Partition(Arr,p,r){
    pivot=A[p];//将主元设为范围内第一个元素
    sp=p+1;//将`sp` 指针初始化指向范围内第二个元素
    bigger=r;//将第二个指针初始化指向范围内最后一个元素
    while(sp<=bigger){//即未遍历完元素前
        if(A[sp]<=pivot)
            sp++;
        else
            swap(A,sp,bigger);
            bigger--;
    }
    swap(A,p,bigger)；//将biggeer所指元素值与主元值进行交换
    return bigger;//返回主元的位置
}

2.2.2 java代码

public static void main(String[] args){
    int[] arr=Util.getRandomArr(10,1,20);//生成最小值为1，最大值为20的长度为10的随机数组
    Util.print(arr);
    quickSort(arr,0,arr.length-1);
    Util.print(arr);
}
public static void quickSort(int[] A,int p,int r){
    if(p<r){
        int q=partition(A,p,r);
        quickSort(S,p,q-1);
        quickSort(A,q+1,r);
    }
}

public static int partition(int[]A,int p,int r){
    int pivot=A[p];
    int sp=p+1;
    int bigger=r;
    while(sp<=bigger){
        if(A[sp]<=pivot)
            sp++;
        else{
            Util.swap(A,sp,bigger);
            bigger--;
        }
    }
    Util.swap(A,p,bigger);
    return bigger;
}

2.2.3 C++代码

#include<iostream>
#include<cstdlib>

using namespace std;

void quickSort(int* arr,int begin,int end);
int partition(int* arr,int begin,int end);

int main(){
    int arr[6]={1,3,2,5,7,6};
    int arrLen=sizeof(arr)/sizeof(arr[0]);
    quickSort(arr,0,arrLen-1);
    
    for(int i=0;i<arrLen;i++){
        printf("%d ",arr[i]);
    }
}
/*
快速排序算法
参数：arr输入数组，begin当前进行快排的数组区间的起始坐标，end结束坐标 
*/
void quickSort(int* arr,int begin,int end){
    if(begin<end){
        int q=partition(arr,begin,end);
        quickSort(arr,begin,q-1);
        quickSort(arr,q+1,end);
    }
}

/*
快速排序算法的划分区间的函数(找主元) 
参数：arr输入数组，begin当前进行快排的数组区间的起始坐标，end结束坐标 
*/
int partition(int* arr,int begin,int end){
    int pivot=arr[begin];//主元pivot一直是范围内第一个元素，直到遍历完范围内元素后才将其与bp所指元素互换 
    int sp=begin+1;//扫描指针初始化为第2个元素位置
    int bp=end;//第二个指针初始化为最后一个元素位置
    
    while(sp<=bp){
        if(arr[sp]<=pivot)
            sp++;//sp向后移1位
        else{
            //交换sp与bp处的元素
            int tmp=arr[sp];
            arr[sp]=arr[bp];
            arr[bp]=tmp;
            
            bp--;//bp向前移1位
        }   
    }
    int tmp=arr[bp];//交换主元bp位置
    arr[bp]=arr[begin];//即arr[bp]=pivot 
    arr[begin]=tmp;
    
    return bp; //返回主元位置
}

3. 快排之双向扫描分区法

3.1 基本思想

快排函数的基本思想同上 2.1.1

分区函数的基本思想如下：

之前第2点的单向扫描分区法是第一个指针 sp 从左往右扫，遇到小的移到下一位,即 sp++，遇到大的交换该值与 第二个指针bp 的值，bp 指针再往前一位，即 bp++。即只有一个扫描指针 sp, bp 指针是被动移动。

双向扫描分区法就是

• 设置两个扫描指针 left 和 right ,两个指针同时往中间扫

• left 遇到比主元小的元素则移动到下一位，遇到比主元大的元素则暂停移动

• right遇到比主元大的元素则移动到前一位，遇到比主元小的元素则暂停移动

• left 和 right 都暂停后，交换两个指针所指向的值

• 主元的选取还是选取范围内的第一个元素

• 与单向扫描法一样，扫描结束时 left 和 right 指针会交错，left 指针指向第一个比主元大的元素，right 指针指向最后一个比主元小的元素

3.2 代码

3.2.1 伪代码

partition2(A,begin,end){
    pivot=A[begin];//设置主元为范围内的第一个元素
    left=begin+1;//设置left指针指向第一个元素
    right=end;//设置right指针指向最后一个元素
    while(left<=right){//当left和right交错之前
        while(left<=right&&A[left]<=pivot)//因为left在变化所以这里也要有left<=right的判断条件
            left++;
        while(left<=right&&A[right]>=pivot)
            right--;
        if(left<right)//如果left=right就没有交换的必要了
            swap(A,left,right);//不满足两个while1条件时说明left和right都暂停了，交换这两个下标对应的值
    }
    swap(A,begin,right);//将最后一个比主元的值与主元交换位置
    return right;//返回主元位置
}

3.2.2 java代码

public static int partition2(int[]arr,int begin,int end){
    int pivot=arr[begin];
    int left=begin+1;
    int right=end;
    while(left<=right){
        while(left<=right&&arr[left]<=pivot)//因为left在变化所以这里也要有left<=right的判断条件
            left++;
        while(left<=right&&arr[right]>pivot)
            right--;
        if(left<right){
            Util.swap(arr,left,right);
        }
    }
    Util.swap(arr,begin,right);
    return right;
}

3.2.3 C++代码

int partition2(int arr[],int begin,int end){
    int pivot=arr[begin];
    int left=begin+1;
    int right=end;
    while(left<=right){
        while(left<=right&&arr[left]<=pivot)//因为left在变化所以这里也要有left<=right 的判断条件
            left++;
        while(left<=right&&arr[right]>pivot)
            right--;
        if(left<right){//如果left==right就没有交换的必要了
            int tmp=arr[left];
            arr[left]=arr[right];
            arr[right]=tmp;
        }
    }
    int tmp=arr[begin];//交换主元到右指针的位置
    arr[begin]=arr[right];
    arr[right]=tmp;
    
    return right;
}

4. 快排之三指针分区法

4.1 基本思想

对性能提升有点用，但基本没用

其实就是单向扫描法再加一个 ep 指针，ep 初始化为范围内的第2个元素，之后指向并一直指向第一个等于主元的元素

• 初始化：主元pivot 初始化指向给定数组范围内的第一个元素，sp 和ep 初试化为第2个元素的位置，bp 初始化为最后一个元素的位置

• sp 从左向右扫描

  • 遇到比主元小的就移向下一位,sp++
  • 比主元大的就让其与 bp 交换值，并且 bp 往前移一位，bp--
  • 遇到第一个跟主元相等的值就让 ep 指向该位置保持不动，sp 接着往后移动。若下一个仍为与主元相等的值，sp也接着往后移动，ep则始终保持指向第一个与主元相等的值不作移动；若遇到比主元小的值时就交换ep 和sp 的值.....此时小于主元的值被换到了前面，等于主元的值被换到了后面(sp) 的位置，ep++之后，ep 指向的仍为(新的)第一个等于主元的元素，即ep 始终指向第一个等于主元的元素

  举例：假如数组中除了第一个元素(主元)外，只有一个元素与主元相同，那么当 ep 指向其之后，sp 接着向下移动一位，遇到的是< 主元的元素，则与ep互换值，则 ep 指向了< 主元的元素，sp 指向了 = 主元的元素，ep++ ,此时 ep 和 sp 指向同一位置，即 = 主元的元素，sp++ 接着指向下一个小于主元的元素...循环之后这个唯一 = 主元的元素会被移到最后一个比主元小的元素的下一个位置...

  当有多个元素和主元相同、甚至连续分布时可以同理分析，最后全部等于主元的元素集中在中间

• 最后的出口情况，最后当sp 和 bp 都指向同一个元素时，这个元素的大小还未确定，可能是 <, = 或 > ，对这三种情况进行讨论会发现 sp 始终指向第一个大于主元的元素，bp 始终指向最后一个等于主元的元素，ep 始终指向第一个等于主元的元素，所以循环条件还是while(sp<=bp)

• 循环结束后将主元 ep-=1 ,主元再与ep 的值(此时为最后一个小于主元的值)进行交换，交换后刚好ep 指向的又是第一个等于主元的值

 

快排之三指针分区法示意图1

 

快排之三指针分区法示意图2

4.2 代码

扩展

让函数返回两个数的方法：用结构体，返回一个结构体，结构体可包含多个变量

<font color=red>//todo: 写出的代码有bug,查不出来，在网上看看其他博客是怎么实现的</font>

5. 快排在工程实践中的优化

只有在数组已经有序或逆序排好的情况下，快速排序性能为最差情况，这样的话划分过程产生的两个区域中有一个没有元素，另一个包含n-1个元素。此时时间复杂度为 O(n^2)

在平均情况下，哪怕划分点非常偏斜，时间复杂度也仍为 O(nlgn)

两种优化思路：

• 优化中值的选取

  • 随机中值法

    在数组中随机选取一个数与数组的第一个元素值互换，之后的步骤就跟上面的一样了

  • 三点中值法

    就是取中间下标对应的值，第一个元素值，最后一个元素值，取这三个值的中值作为主元,然后将主元与第一个元素的值互换，之后步骤同上

  • 绝对中值法

    设k个元素为一组，则原数组划分为 [N/k]+1 组,对这些组分别进行插入排序，选出它们的中值，这些中值组成一个新的组，再进行插入排序，就得到绝对中值了，这时候时间复杂度就得加个常数项 O(N) 了(原来是 O(NlgN)+O(N) )

    实际应用中三点中值法用得多，绝对中值法用得少

• 待排序列表较短时，用插入排序

  插入排序的时间复杂度准确来说是为 O(n(n-1)/2) , 而插入排序的时间复杂度准确来说是 O(nlg(n)+n) 所以对于n较小时，直接用插入排序是更快的，代入运算发现当 n<=8 时 n(n-1)/2 比 nlg(n)+n 小

6. 参考资料

[1] 快速排序的分析与优化