SilentSpiral

Maybe QuickSort?

1.Quick Selection

目标：在n个数中找到前k大的数（或者第k大的数）

如果使用小根堆来求解的话，时间复杂度是\(O(nlogk)\)

Quick Selection算法可以在平均\(O(n)\)的时间复杂度内求解。(看起来很美好)

快速选择算法要求把全部数据装入内存，而建堆则不必一次性装入所有数据

所以堆可以处理海量数据的TopK问题

数据较少时，快速选择算法有理论上的优势

原理

Quick Selection算法和Quick Sort算法是同由东尼霍尔提出，这两者之间有很大的相似之处——分治，即将问题的规模一次次的减小，直到求出最终解。

  1. 随机产生一个pivot
  2. 根据这个pivot，将小于其的数放左边，大于其的数放右边
  3. 更新第n大数的估计值的位置，选择其中一边，直到=n
  4. 重复2、3步骤

快速排序算法使用了分治法，快速选择则使用了减治法

1
2
3
4
5
6
7
8
9
10
11
12
int QuickSelection(int *q, const int &k, int low, int high){ //应传入k-1
    if (low < high){
        int mid = Partition(q, low, high);
        if (mid<k) {
            return QuickSelection(q, k,mid+1, high);
        }else if (mid>k){
            return QuickSelection(q, k,low, mid-1);
        }else{
            return q[k];
        }
    }
}

由于递归不再是快排一样的树形递归，此处也可以考虑把递归改成循环

反正开了O2以上的优化这里就是尾递归了，效率上区别不大但是参数太多显得不够优雅

1
2
3
4
5
6
7
8
9
10
11
12
int QuickSelection(int *q, int k, int length){//应传入k-1, 或者函数内k--
    int low = 0, high = len;
    int mid = partition(a,low,high);
    while(mid!=k){
        if (k>mid) 
            low=mid+1;
        else 
            high=mid-1;
        mid = partition(a,low,high);
    }
    return q[mid]
}

（网上没找到代码自己写的）

2.Partition的三种实现

快速排序的双指针交换部分可以单独封装出来，提高可读性

1
2
3
4
5
6
7
void QuickSort(int a[], int low, int high){
    if (low < high){
        int q = Partition(a, low, high);
        QuickSort(a, low, q - 1);
        QuickSort(a, q + 1, high);
    }
}

Partition函数有三种实现方式

左右指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
int Partition(int* a,int left,int right){//左右指针法    
    int key = right;//利用key作为基准值的下标  
    while (left < right){//左指针向右找第一个比key大的数  
        while (left < right && a[left] <= a[key])  
            ++left;    //右指针向左扎找第一个比key的数  
        while (left < right && a[right] >= a[key])  
            --right;  
        if (a[left] != a[right]) //交换左右指针所指的值  
            swap(a[left],a[right]);    
    }  
    swap(a[left],a[key]);  //将key值放到正确位置上 
    return left;  
}

挖坑法

挖坑法的思想是类似于左右指针法的，思路是先将最右边的值保存下来，作为key值。这时候最右边的值被取出去，最右边就相当于有了一个坑，我们从左向右进行遍历，找到一个比key大的数就把它填到这个坑里，这时候就相当于坑在左边，我们有从右向左进行遍历找比key小的数，找到后再次填到坑里。依次类推，大致的思想和上面的解法其实是很相似的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Partition(int* a,int left,int right){   //挖坑法
    int i=left,j=right;
    int key = a[right];//将区间最右侧数据基准值  
    while (i < j){      
        while (i < j && a[left] <= key)  //左指针向右找比key大的数据  
            ++left;    
        a[j] = a[i];//用找到的数据填坑  
        while (i < j && a[right] >= key)   //右指针想左找比key小的数据  
            --right;    
        a[i] = a[j];//用找到的数据填坑   
    }  
    a[j] = key;//最后用key值填坑  
    return blank;  
}

前后指针法

前后指针法的思路就是有两个指针，一个为cur，另一个为prev。开始的时候让cur指向left，让prev指向left的前一个位置。让cur向后找比key小的值，找到之后就让prev++，如果此时prev与cur不相等就让prev与cur进行交换。如果找不到比key小的值就一直让cur向后走，直到走到区间的最右边就停止，当cur走到边界的时候就让cur与prev进行交换。不断缩小边界，相同的方法进行遍历子区间。

这种实现方式可以对单链表进行快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Partition(int *a, int low, int high){
    int key = a[high];//将输入数组的最后一个数作为主元，用它来对数组进行划分
    int i = low - 1;//i是最后一个小于主元的数的下标
    for (int j = low; j < high; j++){//遍历下标由low到high-1的数
        if (a[j] < key){//如果数小于主元的话就将i向前挪动一个位置，并且交换j和i所分别指向的数
            int temp;
            i++;
            swap(a[i],a[j]);
        }
    }
//经历上面的循环之后下标为从low到i（包括i）的数就均为小于x的数了，现在将主元和i+1位置上面的数进行交换
    swap(a[++i],a[high]);
    return i;
}

3.枢轴选取优化

三数取中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int GetMidIndex(int* a,int left,int right){    //三数取中法  
    int mid = left + ((right - left) >> 1);  
    if (a[left] < a[mid]){  
        if (a[mid] < a[right]){  
            return mid;  
        }else{  
            return (a[left] < a[right])? right:left;  
        }  
    }else{//a[left]>=a[mid]   
        if (a[mid] > a[right]){  
            return mid;  
        }else{  
            return (a[left] > a[right])? right:left;  
        } 
    }  
}

随机选取

在调用partition前随机选取元素与枢轴位置的元素交换。

4.区间三分

数学家们发现，虽然快速排序已经很快了，但是在一种情况下存在可以优化的余地：

【数组中存在大量重复数据】

因为，“左右指针”分别找“比参照物大的元素”和“比参照物小的元素”，所以“等于参照物的元素”就原封不动的放在原地，在下一级迭代排序中继续参与排序。

参考链接1

参考链接2

参考链接3给出了简洁的版本：

这里是和普通快速排序不一样的地方

这里维护几个索引

用i跟踪当前待比较的那一个元素

通过不断地递归将数组切分成三个部分

a[low…lt-1]：小于部分

a[lt…gt]：等于部分

a[gt+1, high]：大于部分

注意到partition部分有两个返回值，因此在c语言实现中不再把partition单独写成函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void QuickSort(int* a, int low, int high){
    if (lo < high){
        int lt = low, gt = high, i = lt + 1;
        int base = a[low];
        while (i <= gt){ //对三种情况的处理
           if (a[i] < base)
                swap(a[lt++], a[i++]);
           else if (a[i] > base)
                swap(a[gt--], a[i]);
           else
                i++;
        }
        QuickSort(a, low, lt - 1);
        QuickSort(a, gt + 1, high);
    }
}

5.并行化

从快速排序的基本思想可以得出以下结论：

通过一次排序分成2个待排序数组

通过二次排序分成4个待排序数组

……

通过n次排序分成2^n个待排序数组

假设CPU有N个Core(Intel CPU的核数通常是2的x次幂,AMD不一定)，那么log2N次排序后就可以进行并行化操作，将N个数组分别放到N个Core中进行计算，如下图所示

假设处理器核足够多的情况下，并行化的快排可以达到O(n)的时间复杂度

裆燃了，存在并行化之后更快的算法：【双调排序】，并行前O(nlog2n)，并行后O(log2n)

6.尾递归？

这段代码困扰我挺久的，原来它不是尾递归，只是通过修改快排的形式从而拉平递归树，期望减少栈深

注意题目中说到了simulate tail recursion，而不是真正的tail recursion，是怎么实现的呢？如果一颗树的度变大了，那么它的高度自然就变小了。所以说为了达到尾递归的效果，可以在递归过程中，让递归函数尽量多的调用自己。

其实QUICKSORT’和QUICKSORT做的partition都是一样的。

QUICKSORT’先做一个Partition，找到q，然后对左边的子序列排序，接着并不是对右边的子序列排序，而是先将子序列进行一次Partition。本质上是一样的。 两者有什么区别呢？那就是递归的调用顺序 QUICKSORT的调用树是一个二叉树。一个QUICKSORT仅调用两次自己。而QUICKSORT’可以调用多次自己，这样它的调用树就不是二叉了。

参考链接

1
2
3
4
5
6
7
8
9
void QuickSort(int *p,int len,int start,int last){
   if(NULL=p) return;
   int index;
   while(start<last){
   	 index=Partition(p,len,start,last);
	 QuickSort(p,len,start,index-1);
	 start=index+1; 
   }		
}

7.非递归实现

　　快速排序非递归化是怎么回事呢？快速排序相信大家都很熟悉，但是快速排序非递归化是怎么回事呢，下面就让小编带大家一起了解吧。

　　快速排序非递归化，其实就是自己手写一个栈来代替系统栈，大家可能会很惊讶快速排序怎么可以非递归化呢？但事实就是这样，小编也感到非常惊讶。

　　这就是关于快速排序非递归化的事情了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void QuickSortNotR(int* array,int left,int right){
	assert(array);
	stack<int> s;
	s.push(left);
	s.push(right); //后入的right，所以要先拿right
	while(!s.empty){ //栈不为空
		int right = s.top();
		s.pop();
		int left = s.top();
		s.pop();
		
		int index = Partition(array,left,right);
		if((index - 1) > left){       //左子序列
			s.push(left);
			s.push(index - 1);
		}
		if((index + 1) < right){      //右子序列
			s.push(index + 1);
			s.push(right);
		}
	}
}

8.Why Quick？

实际开发中，为什么快速排序要比堆排序性能好？

第一、堆排序访问数据的方式没有快速排序友好。

对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的。比如，堆排序中，最重要的一个操作就是数据的堆化。比如下面这个例子，对堆顶进行堆化，会依次访问数组下标是1，2，4，8的元素，而不像快速排序那样，局部顺序访问，所以，这样对CPU缓存是不友好的。

第二、对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。

我们在讲排序的时候，提过两个概念，有序度和逆序度。对于基于比较的排序算法来说，整个排序过程是由两个基本操作组成的，比较和交换。快速排序交换的次数不会比逆序度多。

但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对选择顺序，导致数据有序度降低。比如对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了。

9.std::sort

当我们划分的子区间很小的时候（一般情况下13为判断的标准），我们使用快速排序对于这些小区间进行排序的时候，如果我们还使用快速排序的话就会得不偿失。因为快速排序对子区间的划分就像二叉树一样，越到下面递归越深，那么还不如我们把这剩下的数取出来用其他的排序，这样的话也就提高快速排序的效率。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
#define GAP 13 
void QuickSort(int *a,int left,int right)  {//小区间优化   
    if (left < right){    
        if (right - left > GAP){    
             int div = Partition(a,left,right);    
             QuickSort(a,left,div-1);    
             QuickSort(a,div+1,right);    
        }else{    
             InsertSort(a+left,right-left+1);  //这里的InsertSort用的是直接插入排序  
        }    
    }    
}

这个视频可以看出快排在小区间优化前后的明显区别

打赏