quicksort / quickselect-白红宇

quicksort / quickselect

阅读量：6336 次

发布时间：2019-06-22

本文共 1728 字，大约阅读时间需要 5 分钟。

复习quicksort的两种写法，pivot的选取不唯一，甚至可以随机选取，然后交换一下位置即可。两种方法的 partition 不一样，都很好理解。

quickselect 是找数组第k大的元素，本质和quicksort一样，partition函数共用，找第k个元素在的那一侧。需要注意递归的时候k需要根据情况变动。

quickselect时间复杂度 O(n)，最坏情况O(n^2)。

写法一：当时学C++教的方法

以 a[low] 作为 pivot，每次循环先从右向左，再从左往右，填补空缺。最后 low==high，把 pivot 放到这个位置即可。

#include 
     
      int partition(vector
      
        &a, int low, int high){    int pivot=a[low];    while (low
       
        =pivot) --high;        if (low

&a, int low, int high){ if (low>=high) return; int pivotIndex=partition(a,low,high); quicksort(a,low,pivotIndex-1); quicksort(a,pivotIndex+1,high);}int quickselect(vector

&a, int low, int high, int k){ if (low==high) return a[low]; int pivotIndex=partition(a,low,high); int len=pivotIndex-low+1; if (k==len) return a[pivotIndex]; else if (k

a={ 1,5,8,3,2}; int n=a.size(); quicksort(a,0,n-1); for (auto x:a) cout<

<<' '; cout << endl; for (int k=1;k<=n;++k) cout<

<<' '; return 0;}

写法二：算法导论写法

以 a[high] 作为 pivot (用a[low]的话写起来稍作修改即可)，然后一个 for 循环 low~high-1，遇到大的不管，遇到小的都放到前面。最后 pivot 放在小的元素后面即可。

#include 
     
      int partition(vector
      
        &a, int low, int high){    int pivot=a[high];    int k=low;    for (int i=low;i

&a, int low, int high){ if (low>=high) return; int pivotIndex=partition(a,low,high); quicksort(a,low,pivotIndex-1); quicksort(a,pivotIndex+1,high);}int quickselect(vector

&a, int low, int high, int k){ if (low==high) return a[low]; int pivotIndex=partition(a,low,high); int len=pivotIndex-low+1; if (k==len) return a[pivotIndex]; else if (k

a={

1,5,8,3,2}; int n=a.size(); quicksort(a,0,n-1); for (auto x:a) cout<

<<' '; cout << endl; for (int k=1;k<=n;++k) cout<

<<' '; return 0;}

reference: