快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
时间复杂度是O(n)

算法实现

我们首先需要确立一个主元，这个主元需要我们来选择，然后比这个主元小的数分为一堆，比主元大的数分为一堆，然后递归分，排序。其中pivot是数组选出来的一个主元，
算法的伪代码如下:

void quick_sort(int *a, int n)
{     if ( N < 2 )return; pivot = 从a中选一个主元;将 S = { a \ pivot } 分成2个独立子集: a1 = { b | b <= pivot } 和 a2 = { b | b >= pivot }; a = quick_sort(a1,n1){pivot}quick_sort(a2,n2);
}

关于选主元这个问题，我们不能选太小的，也不能选太大的。
像如果数组正好是升序，我们选第一个元素为主元，那么我们筛选就很麻烦。最坏的情况下时间复杂度就可能是O(n^2)。
所以我们需要找到合适的主元。
其实有个方法就是找数组头、中、尾的元素，分别判断大小，找出中位数。
代码实现如下

int median(int* a, int left, int right)
{int center = left + (right - left) / 2;  //防止溢出if (a[left] > a[center])swap(a[left], a[center]);if (a[left] > a[right])swap(a[left], a[right]);if (a[center] > a[right])swap(a[center], a[right]);swap(a[center], a[right - 1]);//我们把主元放到数组右端return a[right - 1];//返回主元
}

我们再来看一下快速排序的代码

void Quick_sort(int* a, int left, int right){int pivot = 0;int cutoff = 2;//定义一个数值,快速排序适合于元素数量大的排序，如果小于cutoff，我们就用冒泡排序，否则用快速排序int low = 0;int high = 0;if (cutoff <= right - left)	{pivot = median(a, left, right);//找出主元low = left;high = right - 1;while (1)		{while (a[++low] < pivot);//进行循环while (a[--high] > pivot);if (low < high){swap(a[low], a[high]);//在允许范围}else{break;//结束循环}}swap(a[low], a[right - 1]);Quick_sort(a, left, low - 1);//递归到左边快速排序Quick_sort(a, low + 1, right);//递归到右边快速排序}else{bubble_sort(a + left, right - left + 1);//冒泡排序}
}

我们来看一下总代码

#include<stdio.h>
void bubble_sort(int* a,int n);
void Quick_sort(int* a, int n);
void Quick_sort(int* a, int left, int right);
int median(int* a, int left, int right);
void swap(int &a, int &b);int main(){int i;int a[10] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };printf("原始数组顺序为:\n");for (i = 0; i < 10; i++)printf("%2d",a[i]);printf("\n");Quick_sort(a, 10);printf("排序之后的数组顺序为\n");for (i = 0; i < 10; i++)printf("%2d",a[i]);return 0;
}void bubble_sort(int* a,int n){int flag = 0;int tmp = 0;for (int p = n - 1; p; p--){flag = 0;for (int i = 0; i < p; i++){if (a[i] > a[i + 1]){tmp = a[i];a[i] = a[i + 1];a[i + 1] = tmp;flag = 1; }if (flag == 0){break;}}  } 
}  void Quick_sort(int* a, int n){Quick_sort(a, 0, n - 1);
}void Quick_sort(int* a, int left, int right){int pivot = 0;int cutoff = 2;int low = 0;int high = 0;if (cutoff <= right - left)	{pivot = median(a, left, right);low = left;high = right - 1;while (1)		{while (a[++low] < pivot);while (a[--high] > pivot);if (low < high){swap(a[low], a[high]);}else{break;}}swap(a[low], a[right - 1]);Quick_sort(a, left, low - 1);Quick_sort(a, low + 1, right);}else{bubble_sort(a + left, right - left + 1);}
}int median(int* a, int left, int right){int center = left + (right - left) / 2;  if (a[left] > a[center]){swap(a[left], a[center]);}if (a[left] > a[right]){swap(a[left], a[right]);}if (a[center] > a[right]){swap(a[center], a[right]);}swap(a[center], a[right - 1]);return a[right - 1];
}void swap(int &a, int &b){int tmp = a;a = b;b = tmp;
}