前言
今天我们再来讲解两种排序算法，一个是我们熟悉的冒泡排序，另一个就是他的超级升级版本快速排序，他们本质上都是选择排序。
冒泡排序
原理讲解
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。
每一趟冒泡排序就是将最大的数或者最小的数冒到最后一个位置，第二趟就会就会将次大数放到倒数第二个位置，所以n个元素，我们需要n趟就可以将整个数组进行排序。
当然我们可以对方法进行改进，当走一趟排序之后，发现并没有交换元素，那就说明前一个数一定小于后一个数，那就说明整个数组就是有序的，所以就直接跳出。
冒泡排序动图
代码实现
void BubbleSort(int* a, int n){ int end = n; while (end > 0) { int exchage = 1; for (int i = 1; i a[i]) { swap(&a[i], &a[i - 1]); exchage = 0; } } end--; if (exchage==1) break; }}快速排序
首先，大家先来想想，为什么快速排序有这么一个简单粗暴的名字？
只能说明一个这个排序算法很牛，它很快。
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
递归实现
快速排序的主框架，通过partion单趟排序找到左右部分的分割点，每一趟排序都可以将分割点位置放入正确的值。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序void QuickSort(int array[], int left, int right){ if(right - left <= 1) return; // 按照基准值对array数组的 [left, right)区间中的元素进行划分 int div = partion(array, left, right); // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right) // 递归排[left, div) QuickSort(array, left, div); // 递归排[div+1, right) QuickSort(array, div+1, right);}快速排序的递归实现，我们有三种方法实现单趟排序，分别为：
1. hoare版本
hoare是作者提出的版本，有两种情况：
right为keyi，这时我们要让right先走，只有这样，最后相遇的值才会小于a[keyi]。
left为keyi，我们要让left先走，这样，最后相遇的值会大于a[keyi]。
int partion1(int* a, int left, int right){ int tmp = getMid(a, left, right); swap(&a[tmp], &a[right]); int keyi = right; while (left < right) { while (left < right && a[left] <= a[keyi]) left++; while (left = a[keyi]) right--; swap(&a[left], &a[right]); } swap(&a[keyi], &a[left]); return left;}2. 挖坑法
首先我们先令left或right为坑，并且保存a[povit]的值，如果left为坑，那么right先走，反之，left先走，当他们相遇时，即就是最后的坑位，将key填入坑位即可。
int partion2(int* a, int left, int right){ int tmp = getMid(a, left, right); swap(&a[tmp], &a[left]); int key = a[left]; int povit = left; while (left < right) { while (left = key) { right--; } a[povit] = a[right]; povit = right; while (left < right && a[left] <= key) { left++; } a[povit] = a[left]; povit = left; } a[povit] = key; return povit;}3. 前后指针版本
使用两个指针cur，prev，prev指向left，cur指向下一个元素，并且选择left作为key，cur向后走，当a[cur]
int partion3(int* a, int left, int right){ int tmp = getMid(a, left, right); swap(&a[tmp], &a[left]); int keyi = left; int prev = left; int cur = prev + 1; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { swap(&a[prev], &a[cur]); } cur++; } swap(&a[keyi], &a[prev]); return prev;}无论交换与否，cur每次都得向后走，所以在循环时，每次cur++，当需要交换时，我们令prev++，如果自加后的prev等于cur，就相当于本身交换，所以就不用交换了，最后一步将keyi与prev交换，将a[keyi]放在正确的位置上。
4.优化方法一：三数取中法
在前边的单趟排序中，我们发现函数第一条便调用了getmid函数，这时为了找出三个数的中间值，这样可以提高效率，避免了o(n^2)的情况出现。
int getMid(int* a, int left, int right){ int mid = left + (right - left) / 2; if (a[left] > a[right]) { if (a[left] a[mid]) { return right; } else { return mid; } } else { if (a[mid] > a[right]) { return right; } else if (a[mid] < a[left]) { return left; } else { return mid; } }}5.优化方法一：小区间优化
快排的递归类似于二叉树，当二叉树到最后几层时，数据量非常大，所以当到最后几层时，我们不去选择使用快速排序，而是选择插入排序。
//插入排序void InsertSort(int* a, int n){ //控制end的位置 for (int i = 0; i = 0) { if (x = right) return; if (right - left + 1 < 10) { InsertSort(a + left, right - left + 1); } else { int keyi = partion3(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }}非递归实现
当我们不去使用递归时，通常就是使用循环或者使用栈或队列来模拟实现，所以在这里我们使用栈的后入先出的特性来实现快速排序。
代码实现
当栈不为空时，就去拿end与begin，并且进行单次排序，将分割得到的左右区间的begin和end入栈，这里要注意我们应该先入右区间，再入左区间，根据先入后出，这样就可以先将左排好序，相当于用栈来模拟实现函数栈帧的过程。
void QuickSort2(int* a,int left,int right){ stack st; stackInit(&st); stackPush(&st, left); stackPush(&st, right); while (!stackEmpty(&st)) { int end = stackTop(&st); stackPop(&st); int begin = stackTop(&st); stackPop(&st); int keyi = partion3(a, begin, end); if (keyi + 1 < end) { stackPush(&st, keyi + 1); stackPush(&st, end); } if (begin < keyi - 1) { stackPush(&st, begin); stackPush(&st, keyi-1); } } stackDestroy(&st);}总结
今天讲解了冒泡排序和快速排序，当然快速排序是很重要的，我们必须掌握快排的三种单趟排序方法，来解决遇到的问题。