快速排序 | 诗与远方

快速排序的基本思想
快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序的三个步骤
1.选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）；
2.分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大；
3.递归地对两个序列进行快速排序，直到序列为空或者只有一个元素；
选择基准元的方式
对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列。
1.固定基准元：如果输入序列是随机的，处理时间是可以接受的。如果数组已经有序时，此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一，此时为最坏情况，快速排序沦为冒泡排序，时间复杂度为Θ(n^2)。而且，输入的数据是有序或部分有序的情况是相当常见的。因此，使用第一个元素作为基准元是非常糟糕的，应该立即放弃这种想法。
2.随机基准元：这是一种相对安全的策略。由于基准元的位置是随机的，那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时，仍然是最坏情况，时间复杂度是O(n^2）。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n）。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn）的期望时间复杂度。
3.三数取中:引入的原因：虽然随机选取基准时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中选取基准。
分析：最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为基准元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准元。显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约5%的比较次数。


 #include<stdio.h> 


//交换子表的记录，使枢轴记录到位，并返回枢轴所在的位置  
int Partition(int array[], int low, int high){  
  
    /*三数中值分割法*/  
    int m = low + (high - low) / 2;//数组中间元素的下标  
    if (array[low]>array[high])   //保证左端较小  
        swap(array, low, high);  
    if (array[m] > array[high])   //保证中间较小  
        swap(array, high, m);  
    if (array[m] > array[low])  
        swap(array, m, low);      //保证左端最小  
    //此时array[low]已经为整个序列左中右三个关键字的中间值  
    int pivotkey = array[low];  
  
    /*固定基准元 
     int pivotkey = array[low]; 
     */  
  
    /*随机基准元 
    int randomIndex = rand() % (high - low) + low;//取数组中随机下标 
    swap(array, randomIndex, low);                //与第一个数交换 
    int pivotkey = array[low]; 
    */  
  
    int i = low, j = high;  
    while(i<j) //从表的两端交替向中间扫描,当没有相遇  
    {  
        while (array[j] >= pivotkey&&i<j){  
            j--;  
        }  
        while (array[i] <= pivotkey&&i<j){  
            i++;  
        }  
        if (i<j)  
        {  
            swap(array, i, j);  
        }     
    }  
    //最终将基准数归位  
    swap(array, low, i);  
    return i;              //返回枢轴所在的位置  
}  
void QSort(int array[], int low, int high)
{  
    int pivot;  
    if (low<high)  
    {  
        pivot = Partition(array, low, high);//算出枢轴值  
        QSort(array, low, pivot - 1);       //对低子表递归排序  
        QSort(array, pivot + 1, high);      //对高子表递归排序  
    }  
}  
void swap(int array[], int i, int j)
{
	//0∧0=0,0∧1=1,1∧1=0
    //i,j为需要交换数值的数组下标
    if(i == j)
     return;//下标相同直接返回
    array[i] = array[i]^array[j];
    array[j] = array[i]^array[j];
    array[i] = array[i]^array[j];
}
//对array做快速排序  
int main(){ 
	int array[] = {9, 2, 4, 3, 5, 1, 0, 7, 8, 6};
	int i; 
	int n = sizeof(array)/sizeof(int);
    QSort(array, 0, n - 1); 
	for( i = 0; i < n; i++) 
       printf("%d", array[i]);
    return 0;
}

快速排序的优化
对于很小的数组（N<=20）,快速排序不如插入排序好。不仅如此，因为快速排序是递归的，所以这样的情况经常发生。通常的解决办法是对于小的数组不递归的使用快速排序，而代之以诸如插入排序这样的对小数组有效的排序算法。使用这种策略实际上可以节省大约15%的（相对于自始至终使用快速排序时）的运行时间。一种好的截止范围是N=10，虽然在5到20之间任一截止范围都有可能产生类似的结果。
下面是代码：

 void QSort(int array[], int low, int high){
	int pivot;
	if (high-low+1>=10)
	{	
		pivot = Partition(array, low, high);//算出枢轴值
		QSort(array, low, pivot - 1);       //对低子表递归排序
		QSort(array, pivot + 1, high);      //对高子表递归排序
	}
	else{
		InsertSort(array+low, high-low+1); //插入排序
	}		
}

插入排序代码：

void InsertSort(int array[], int n){
int j;
for (int i = 1; i < n;++i)
{
	int key = array[i];
	for (j = i; j>0 && array[j - 1] > key;j--)
	{
		array[j] = array[j - 1];
	}
	array[j] = key;
}
}

当待排序序列的长度分割到一定大小后，使用插入排序

if (high - low + 1 < 10)
{
	InsertSort(arr,low,high);
	return;
}//else时，正常执行快排

对递归使用尾递归

如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。

http://www.ruanyifeng.com/blog/2015/04/tail-call.html

关于一个尾递归形象的比喻

function story() { 从前有座山，山上有座庙，庙里有个老和尚，一天老和尚对小和尚讲故事：story() // 尾递归，进入下一个函数不再需要上一个函数的环境了，得出结果以后直接返回。}
function story() { 从前有座山，山上有座庙，庙里有个老和尚，一天老和尚对小和尚讲故事：story()，小和尚听了，找了块豆腐撞死了 // 非尾递归，下一个函数结束以后此函数还有后续，所以必须保存本身的环境以供处理返回值。}
https://www.zhihu.com/question/20761771