快速排序（QuickSort）是对冒泡排序算法的一种改进。
快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，
前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，
直到将无序序列排列成有序序列。
排序流程
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
1、首先设定一个分界值，通过该分界值将数组分成左右两部分。
2、将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。（注：等于分界值的数据靠左靠右以实际编写的代码而异）
3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
图解：
代码实现
#include <stdio.h>
#include <stdlib.h>
void swap(int arr[], int low, int high)
{
int temp;
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
int Partition(int arr[], int low, int high)
{
int point;
point = arr[low];
while(low<high)
{
while(low<high && arr[high]>=point)
{
high--;
}
swap(arr, low, high);
while(low<high && arr[low]<=point)
{
low++;
}
swap(arr, low, high);
}
return low;
}
void QSort(int arr[], int low, int high)
{
int point;
if(low<high)
{
point = Partition(arr, low, high);
QSort(arr, low, point-1);
QSort(arr, point+1, high);
}
}
void QuickSort(int arr[], int len)
{
QSort(arr, 0, len-1);
}
int main(void)
{
int i;
int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
QuickSort(a, 10);
printf("排序后的结果是：");
for(i=0; i<10; i++)
{
printf("%d", a[i]);
if(i!=9)
{
printf(",");
}
}
printf("\n");
return 0;
}
快速排序的优化
- 优化选取基准点（三数取中法）
- 优化不必要的交换
- 优化小数组时的排序方案
- 优化递归操作
优化选取基准点
选取合适的基准点可以减少递归深度提高排序性能。
如本例第一轮选取的是元素5，5刚好是序列的中间值，画递归树时，第一层有左右子树。
假如选取的元素是9，那么可想而知，递归一轮后所有数据将会靠9的左边，右边则没有数据，这样并不能把序列分成左右两组数据，
从而导致递归深度增加，排序性能下降。如下图所示：
三数取中法
从数组中找取3个元素，然后取这3个元素的中间值，如：[8, 2, 6] 那么处于中间的元素就是6。
代码：
#include <stdio.h>
#include <stdlib.h>
void swap(int arr[], int low, int high)
{
int temp;
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
int Partition(int arr[], int low, int high)
{
int point;
// 优化1. 选取基准点（三数取中法）
int mid = low + (high - low) / 2;
if(arr[low] > arr[high])
{
swap(arr, low, high);
}
if(arr[mid] > arr[high])
{
swap(arr, mid, high);
}
if(arr[mid] > arr[low])
{
swap(arr, low, low);
}
point = arr[low];
while(low<high)
{
while(low<high && arr[high]>=point)
{
high--;
}
swap(arr, low, high);
while(low<high && arr[low]<=point)
{
low++;
}
swap(arr, low, high);
}
return low;
}
void QSort(int arr[], int low, int high)
{
int point;
if(low<high)
{
point = Partition(arr, low, high);
QSort(arr, low, point-1);
QSort(arr, point+1, high);
}
}
void QuickSort(int arr[], int len)
{
QSort(arr, 0, len-1);
}
int main(void)
{
int i;
int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
QuickSort(a, 10);
printf("排序后的结果是：");
for(i=0; i<10; i++)
{
printf("%d", a[i]);
if(i!=9)
{
printf(",");
}
}
printf("\n");
return 0;
}
优化不必要的交换
从前面的图例可以看出，选取的基准元素5在不停的和其它元素进行位置交换，优化方案是把位置交换改为直接赋值。
代码：
#include <stdio.h>
#include <stdlib.h>
void swap(int arr[], int low, int high)
{
int temp;
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
int Partition(int arr[], int low, int high)
{
int point;
// 优化1. 选取基准点（三数取中法）
int mid = low + (high - low) / 2;
if(arr[low] > arr[high])
{
swap(arr, low, high);
}
if(arr[mid] > arr[high])
{
swap(arr, mid, high);
}
if(arr[mid] > arr[low])
{
swap(arr, low, low);
}
point = arr[low];
while(low<high)
{
while(low<high && arr[high]>=point)
{
high--;
}
arr[low] = arr[high]; // 优化2. 改为直接赋值
while(low<high && arr[low]<=point)
{
low++;
}
arr[high] = arr[low]; // 优化2. 改为直接赋值
}
arr[low] = point; // 优化2. 改为直接赋值
return low;
}
void QSort(int arr[], int low, int high)
{
int point;
if(low<high)
{
point = Partition(arr, low, high);
QSort(arr, low, point-1);
QSort(arr, point+1, high);
}
}
void QuickSort(int arr[], int len)
{
QSort(arr, 0, len-1);
}
int main(void)
{
int i;
int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
QuickSort(a, 10);
printf("排序后的结果是：");
for(i=0; i<10; i++)
{
printf("%d", a[i]);
if(i!=9)
{
printf(",");
}
}
printf("\n");
return 0;
}
优化小数组时的排序方案
对于很小的数组(array.length <= 20)，快速排序不如插入排序（插入排序在排序算法中处理小数组时性能最好），因为快排是递归分解的，总会遇到小数组情况。
因此，当是小数组时，我们采用插入排序而不是快排。
上面说小于20的数组的小数组，其实5到20之内都可以，据说7为最佳。
代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX_LENGTH_INSERT_SORT 7 // 优化3. 小数组时的排序方案
// 优化3. 小数组时的排序方案
void ISort(int arr[], int n)
{
int i, j, temp;
for( i=1; i<n; i++ )
{
if( arr[i-1]>arr[i] )
{
temp = arr[i];
for( j=i-1; arr[j]>temp; j--)
{
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
}
}
void InsertSort(int arr[], int low, int high)
{
ISort(arr+low, high-low+1);
}
void swap(int arr[], int low, int high)
{
int temp;
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
int Partition(int arr[], int low, int high)
{
int point;
// 优化1. 选取基准点（三数取中法）
int mid = low + (high - low) / 2;
if(arr[low] > arr[high])
{
swap(arr, low, high);
}
if(arr[mid] > arr[high])
{
swap(arr, mid, high);
}
if(arr[mid] > arr[low])
{
swap(arr, low, low);
}
point = arr[low];
while(low<high)
{
while(low<high && arr[high]>=point)
{
high--;
}
arr[low] = arr[high]; // 优化2. 改为直接赋值
while(low<high && arr[low]<=point)
{
low++;
}
arr[high] = arr[low]; // 优化2. 改为直接赋值
}
arr[low] = point; // 优化2. 改为直接赋值
return low;
}
void QSort(int arr[], int low, int high)
{
int point;
if(high-low > MAX_LENGTH_INSERT_SORT)
{
point = Partition(arr, low, high);
QSort(arr, low, point-1);
QSort(arr, point+1, high);
}
else
{ // 优化3. 小数组时的排序方案
InsertSort(arr, low, high);
}
}
void QuickSort(int arr[], int len)
{
QSort(arr, 0, len-1);
}
int main(void)
{
int i;
int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
QuickSort(a, 10);
printf("排序后的结果是：");
for(i=0; i<10; i++)
{
printf("%d", a[i]);
if(i!=9)
{
printf(",");
}
}
printf("\n");
return 0;
}
优化递归操作
代码中的快速排序有2次递归函数操作，减少递归函数的调用就可以最大程度的提高其性能，这时可以使用尾递归。
什么是尾递归呢？如果一个函数中递归形式的调用出现在函数的末尾，我们称这个递归函数是尾递归的。
当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活跃记录而不是在栈中去创建—个新的。
编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。
通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。
因此，只要有可能我们就需要将递归函数写成尾递归的形式。
最终代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX_LENGTH_INSERT_SORT 7 // 优化3. 小数组时的排序方案
// 优化3. 小数组时的排序方案
void ISort(int arr[], int n)
{
int i, j, temp;
for( i=1; i<n; i++ )
{
if( arr[i-1]>arr[i] )
{
temp = arr[i];
for( j=i-1; arr[j]>temp; j--)
{
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
}
}
void InsertSort(int arr[], int low, int high)
{
ISort(arr+low, high-low+1);
}
void swap(int arr[], int low, int high)
{
int temp;
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
int Partition(int arr[], int low, int high)
{
int point;
// 优化1. 选取基准点（三数取中法）
int mid = low + (high - low) / 2;
if(arr[low] > arr[high])
{
swap(arr, low, high);
}
if(arr[mid] > arr[high])
{
swap(arr, mid, high);
}
if(arr[mid] > arr[low])
{
swap(arr, low, low);
}
point = arr[low];
while(low<high)
{
while(low<high && arr[high]>=point)
{
high--;
}
arr[low] = arr[high]; // 优化2. 改为直接赋值
while(low<high && arr[low]<=point)
{
low++;
}
arr[high] = arr[low]; // 优化2. 改为直接赋值
}
arr[low] = point; // 优化2. 改为直接赋值
return low;
}
void QSort(int arr[], int low, int high)
{
int point;
if(high-low > MAX_LENGTH_INSERT_SORT)
{
// 优化4. 优化递归操作
while(low<high)
{
point = Partition(arr, low, high);
if(point-low < high-point)
{
QSort(arr, low, point-1);
low = point + 1;
}
else
{
QSort(arr, point+1, high);
high = point -1;
}
}
}
else
{ // 优化3. 小数组时的排序方案
InsertSort(arr, low, high);
}
}
void QuickSort(int arr[], int len)
{
QSort(arr, 0, len-1);
}
int main(void)
{
int i;
int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
QuickSort(a, 10);
printf("排序后的结果是：");
for(i=0; i<10; i++)
{
printf("%d", a[i]);
if(i!=9)
{
printf(",");
}
}
printf("\n");
return 0;
}