随机快速排序

快速排序是一个经典的算法，它是基于比较排序中最快的算法之一，时间复杂度是O(N * logN)的,时间复杂度证明可以用master公式证明。但经典的快速排序会存在最坏的情况，会使得快速排序的时间复杂度退化到O(N²)，这样快速排序也就失去了意义。因此我们为了避免出现最坏的情况，来引入随机一行为，每次的基准值是随机选取的   ，那么这样无论是什么数据都无法影响我们排序。那么随机快速排序的时间复杂度是O(N * logN)，因为用了随机就不能用最好和最坏的时间复杂度来估计了，而要按照数学期望来估计它的时间复杂度。那么具体的证明过程，在算法导论-7.4.2有详细的数学证明，感兴趣的可以去看。

代码实现

这个随机快速排序是用了荷兰国旗问题优化过的。

//快速排序的改进避免最坏情况 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define N 100

typedef int ELEMENT;

void quickSort(ELEMENT *a, int low, int high);
void swap(ELEMENT *a, int low, int high);//交换a[low]和a[high]的值 
int* partition(ELEMENT *a, int low, int high);//把a中low到high的数分类，小于的在左边，等于的在中间，大于的在右边

int main(int argc, char *argv[])
{
	int a[N];
	
	srand(time(NULL));
	
	for (int i = 0; i < N; i++) {
		a[i] = rand() % 100; 
	}

	for (int i = 0; i < N; i++) {
		printf("%d ", a[i]);
	}
	putchar('\n');
	
	quickSort(a, 0, N - 1);

	for (int i = 0; i < N; i++) {
		printf("%d ", a[i]);
	}
	putchar('\n');
	
	return 0;
}
void quickSort(ELEMENT *a, int low, int high)
{
	int *p = NULL;//存储等于基准值的左右边界 
	
	if ( low >= high) {//如果只有一个值不用排序就直接结束排序 
		return ;
	}
	
	swap(a, low + rand() % (high - low + 1), high);//随机从数组里面找一个数，和最后一个数做交换 
	p = partition(a, low, high);//p指向等于基准值区间左右边界 
	quickSort(a, low, p[0] - 1);//只排小于基准值的部分 
	quickSort(a, p[1] + 1, high);//只排大于基准值的部分
	free(p);//释放掉开辟的空间 
}
void swap(ELEMENT *a, int low, int high)
{
	ELEMENT t = 0;
	
	t = a[low];
	a[low] = a[high];
	a[high] = t;
}
int* partition(ELEMENT *a, int low, int high)
{
	int l = low - 1;//左边界从low的左边，因为是把最后一个当作基准值 
	int r = high;//右边界从high开始，因为基准值是最后一个 
	int i = low;//从头开始遍历 
	int key = a[high];//把基准值赋值 
	while(i < r) {//只要没有到右边界 
		if (a[i] < key) {//下标i的数小于基准值，放在左边界里面 
			swap(a, l + 1, i);//把左边界的前一个数和下标i的值交换 
			i++;//去下一个数 
			l++;//左边界扩张 
		}
		else  if ( a[i] > key){//下标i的数大于基准值，放在右边界里面 
			swap(a, r - 1, i);//把右边界的前一个数和下标i的值做交换
			r--;//右边界扩张，因为把一个没有访问的数移过来了，所有等下还要访问这个数看是在那个区间的，所以i不加1 
		}
		else {//标i的数等于基准值，放在左右边界之间 
			i++;//直接加1 
		}
	}
	swap(a, r, high);//把基准值和右边界交换位置 
	int *p = (int *)malloc(sizeof(int ) * 2);//存放等于区间的左右边界 
	p[0] = l + 1;//左边界就是l + 1 
	p[1] = r;//右边界刚刚交换了值，所以它的值一定是基准值 
	return p;//返回这个区间 
}

总结

在计算有随机行为算法的时间复杂度的时候，并且随机行为是算法中主要的部分时候，就不能用最坏的情况或者最好情况来计算时间复杂度因为不现实，而要用数学期望的时间复杂度。随机快速排序是一个经典的算法，也是必须要掌握的排序算法。快速排序用的还是分而治之的思想，因此分治法是很重要的。随机快速排序的时间复杂度是O(N * logN),额外空间复杂度是O(logN),假设每次都选在中间位置，那么最多递归logN层，所以额外空间复杂度是O(log N)。