快速排序-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

快速排序

简介: 快速排序

quickSort

在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序法

对 arr[l,r] 进行partition(划分操作)

参考标准是首元素arr[l]=v,把整个数组分成两部分,arr[l+1,j]<v,arr[j+1,i-1]>v,arr[i]是即将要进行排序的元素

  1. 若arr[i]>v,则元素e要放到紫色部分,i++即可
  2. 若arr[i]<v,则元素e要放到橙色部分,用arr[j+1]与e进行交换,j++即代表橙色部分增加1,i++即可
  3. 当i>r代表所有元素都已经排序,再把arr[l]与arr[j]进行交换,此时整个数组划分为两部分,partition操作完成

template<typename T>

int __partition(T arr[],int l,int r){

    //第一个元素设置为参考标准

    T v=arr[l];

    //从arr[l+1]开始对元素进行划分

    //初始时就要保证arr[l+1,j]<v,arr[j+1,i)>v,arr[i]是即将要排序的元素,那么i=l+1

    int j=l,i=l+1

    for(i;i<=r;i++ ){

        if(arr[i]<v){

            swap(arr[i],arr[j+1]);

            j++;

        }

    }

    swap(arr[l],arr[j]); 

    return j;

}

template <typename T>

void __quickSort(T arr[],int l,int r) {

    if(l>=r)

        return;

    //二分操作:将arr中的[l,r]划分为两部分,返回参考标准的坐标j

    int j=__partition(arr,l,r);

   //递归

    __quickSort(arr,l,j-1);

    __quickSort(arr,j+1,r); 

}

//快速排序

template<typename T>

void quickSort(T arr[],int n) {

    __quickSort(arr,0,n-1);

}

n = 1000000

quickSort : 0.727 s

优化1:穿插使用插入排序

对于所有高级排序算法,都可以这么进行优化:

快要递归到底时,可以使用插入排序,当递归到数组数量非常小的时候,可以改为使用插入排序来提高性能

template <typename T>

void __quickSort(T arr[],int l,int r) {

//  if(l>=r)

//      return;

    if(r-l<=15){

        insertionSort(arr,l,r);

        return;

    }

    int j=__partition(arr,l,r);

    __quickSort(arr,l,j-1);

    __quickSort(arr,j+1,r); 

}

n = 1000000

quickSort : 0.685 s

与归并排序的比较

归并排序

通过二分法达到log(n)这样一个层级,然后在通过O(n)的归并操作,就形成了nlog(n)的归并排序

快速排序

快速排序也是不断的将数组一分为二的过程,不过我们需要找到一个标准点,将标准点左边和右边进行划分。

区别

  1. 归并排序每次划分都是平均分配
  2. 快速排序的划分操作无法保证每次都是平均分配,即划分出的子数组可能是一大一小的。即不能完全保证二叉树的高度就是logn,最差情况下,快速排序会退化为O(n^2)

    当数组完全有序时,二叉树高度是n,每层处理的复杂度又是n,那么时间复杂度为O(n^2)。

解决在有序数组中慢

上面的快速排序法中我们是使用数组首元素作为参考标准,修改为随机选择元素作为参考标准,此时退化为O(n^2)的概率接近为0

随机化快速排序法

template<typename T>

int __partition(T arr[],int l,int r){

    //随机选择一个元素与首元素交换,此时的首元素很大概率是平均值

    T random=arr[rand()%(r-l+1)+l];

    swap(arr[l],random); 

    T v=arr[l]; 

    int j=l,i=l+1

    for(i;i<=r;i++ ){

        if(arr[i]<v){

            swap(arr[i],arr[j+1]);

            j++;

        }

    }

    swap(arr[l],arr[j]); 

    return j;

}

template <typename T>

void __quickSort(T arr[],int l,int r) {

    if(r-l<=15){

        insertionSort(arr,l,r);

        return;

    }

    int j=__partition(arr,l,r);

    __quickSort(arr,l,j-1);

    __quickSort(arr,j+1,r); 

}

template<typename T>

void quickSort(T arr[],int n) {

    //当前时间戳作为随机数种子

    srand(time(0));

    __quickSort(arr,0,n-1);

}

缺陷

即使参考标准v选在一个平衡位置,但当数组中有大量重复的元素,等于v的元素也非常多,一样会导致数组被划分为两个极度不平衡的部分,快速排序又退化为O(n^2)级别的算法

解决在含有大量重复元素数组中慢

上述是将partition操作后的两部分都放在数组的一端,i从左到右递增,直到遍历完整个数组。现在将划分的两部分,分别放在数组两端,左右两边的指针同时向内移动,双路快速排序法

游标i和游标j同时向中间移动,直到arr[i]>=v,i停止移动;arr[j]<=v,j停止移动;当两者都停下时交换arr[i]和arr[j],i++,j--。重复上述操作,直到i>j。此时i在第一个>=v的位置,j在最后一个<=v的位置,参考标准arr[l]是在<=v的部分,所以交换arr[l]和arr[j],此时j就是参考标准应该处于的位置

左右部分都可以接收等于v的元素,把等于v的元素分散到左右两部分,保证在含有大量重复元素的数组能平均划分为两部分

双路快速排序法

template<typename T>

int __partition2(T arr[],int l,int r) {

    swap(arr[l],arr[rand()%(r-l+1)+l]);

    T v=arr[l];

    //区间:arr[l+1,i)<=v,arr(j,r]>=v,要保证这两部分的区间都为空

    int i=l+1,j=r;

    while(true) {

        while(i<=r&&arr[i]<v) i++;

        while(j>=l+1&&arr[j]>v) j--;

        if(i>j) break;//当i>j,划分完成,直接跳出循环

        swap(arr[i],arr[j]);

        i++;

        j--;

    }

    swap(arr[l],arr[j]);

    return j;

}

template <typename T>

void __quickSort2(T arr[],int l,int r) {

    if(r-l<=15) {

        insertionSort(arr,l,r);

        return;

    }

    //二分操作:将arr中的[l,r]划分为两部分,返回参考标准的坐标j

    int j=__partition2(arr,l,r);

    __quickSort2(arr,l,j-1);

    __quickSort2(arr,j+1,r);

}

//双路快速排序法

template<typename T>

void quickSort2(T arr[],int n) {

    //当前时间戳作为随机数种子

    srand(time(0));

    __quickSort2(arr,0,n-1);

}

三路快速排序法

Quick Sort 3 Ways

之前划分都是把数组划分为两部分,而三路快速排序则把数组分为三部分(<v,=v,>v),之后递归对<v;>v两部分继续进行三路快速排序

arr[i]是将要处理的元素

  1. 如果arr[i]=v,那么直接纳入蓝色部分,i++
  2. 如果arr[i]<v,那么arr[i]和arr[lt+1]交换,lt++,i++
  3. 若果arr[i]>v,那么arr[i]和arr[gt-1]交换,gt--,i索引则无需维护,因为跟arr[gt-1]本来就是未处理的元素
  4. i一直递增直到与gt重合时,将arr[l]与最后一个小于v的arr[lt]交换,此时arr[lt]是数组中第一个等于v的元素
  5. 调用递归对<v;>v继续进行三路快速排序

//三路快速排序处理arr[l,r]

//将arr[l,r]分为<v;==v;>v三部分

template <typename T>

void __quickSort3(T arr[],int l,int r) {

    if(r-l<=15) {

        insertionSort(arr,l,r);

        return;

    }

    //partition

    swap(arr[l],arr[rand()%(r-l+1)+l]);

    int v=arr[l];

    //<v:[l+1,lt]

    //==v:[lt+1,i)

    //>v:[gt,r]

    int lt=l,gt=r+1;

    for(int i=l+1;i<gt;){

        if(arr[i]>v){

            swap(arr[i],arr[gt-1]);

            gt--;//i无需维护,因为arr[gt-1]本来就是未处理的元素

        }else if(arr[i]<v){

            swap(arr[i],arr[lt+1]);

            i++;

            lt++;

        }else{

            i++;

        }

    }

    swap(arr[l],arr[lt]);

    __quickSort3(arr,l,lt-1);

    __quickSort3(arr,gt,r);

}

//三路快速排序法

template<typename T>

void quickSort3(T arr[],int n) {

    //当前时间戳作为随机数种子

    srand(time(0));

    __quickSort3(arr,0,n-1);

}

partition操作

参考标准是首元素arr[l],使得arr[l+1,j]<v,arr[j+1,i)>v,i是将要插入的元素

双路快速排序


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章