3.2 快速排序算法

2019-03-23  本文已影响0人  Aurochsy

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

2. 快速排序算法

1. 什么是快速排序算法

所以划分是问题的关键

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

2.1 基本思想

2.1.1 快排函数
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 所指元素为尚未确定大小的元素，将sp 移动到该元素上(此时sp 与 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 指针是被动移动。

双向扫描分区法就是

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个元素，之后指向并一直指向第一个等于主元的元素

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

4.2 代码

扩展

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

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

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

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

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

两种优化思路：

6. 参考资料

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

上一篇 下一篇

猜你喜欢

热点阅读