1 交换排序
1.1 冒泡排序
基本思想：
- 所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动（升序）。
- 冒泡排序的图解：
- 冒泡排序的特性总结：
- 1. 冒泡排序是一种非常容易理解的排序
- 2. 时间复杂度：O(N^2)
- 3. 空间复杂度：O(1)
- 4. 稳定性：稳定 （可以控制相同数据的相对位置不发生改变）
- 具体代码：
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void BubbleSort(int* a, int sz) { int i = 0; int j = 0; int flag=0; for (i = 0; i < sz - 1; i++) { for (j = 0; j < sz - 1 - i; j++) { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); flag=1; } } if(0==flag) { break; } } }
冒泡排序比较简单，写起来也很容易，这里就不再多说了。
1.2 快速排序（重点）
基本思想：
快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列， 左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值 ，然后最左右子序列重复该过程，直到所 有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见方式有：
a 挖坑法
b 前后指针法
c 左右指针法(Hoare法)
1.2.1 挖坑法
基本思想：
首先寻找一个坑位（一般选最左边或者中间或者最右边）假设我这里选最左边为坑位，然后用一个关键值key保存坑位值；再从最右边找到小于key的值，找到后就将坑位的值改为找到后的值，然后将找到位置的下标作为新的坑位；再从左边去找到大于坑位的值，找到后同样将坑位的值改为找到后的值，然后将找到位置的下标作为新的坑位；直至相遇。最后将相遇点的值改为key. 这样就完成了将key排到了正确位置。然后分治，用递归将左边与右边分别排，直至所有元素都排到了正确位置。
具体代码实现：
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void QuickSort(int* a, int left, int right) { if (left >= right) { return; } int begin = left; int end = right; int pivot = begin; int key = a[pivot]; while (begin < end) { //右边找小 放在左边 while (begin < end && a[end] >= key) { end--; } a[pivot] = a[end]; pivot = end; //左边找大 放在右边 while (begin < end && a[begin] <= key) { begin++; } a[pivot] = a[begin]; pivot = begin; } a[pivot] = key; QuickSort(a, left, pivot - 1); QuickSort(a, pivot+1, right); }
注意事项：
- 进行key值单趟排序也可以单独分装一个PartSort函数来实现（通过返回值来确定已经排序好的key值），这里我就不分装了，后面前后指针与左右指针采用的是分装过的。
- 右边找小和左边找大时要加上=，否则可能会造成死循环。
优化版本：
优化版本主要从两点优化：
1 实现快排的3中方法比较高效的原因就是用了二叉树的思想先排出较靠近中间值的元素，但是上面的方法并不能保证我们选择的key是较为靠近中间值，所以我们用一个3数取中的方法来处理。
2 由于排最后的几个元素用快排的效率较低，所以我们用直接插入来排（小区间优化）
具体代码：
//3数取中 int GetMidIndex(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[right] > a[mid]) return mid; else if (a[right] < a[left]) return left; else return right; } else { if (a[right] > a[left]) return left; else if (a[right] < a[mid]) return mid; else return right; } } void QuickSort(int* a, int left, int right) { if (left >= right) { return; } int index = GetMidIndex(a, left, right); Swap(&a[left], &a[index]); int start = left; int end = right; int pivot = start; int key = a[pivot]; while (start < end) { while (start < end && a[end] <= key) { end--; } a[pivot] = a[end]; pivot = end; while (start < end && a[start] >= key) { start++; } a[pivot] = a[start]; pivot = start; } a[pivot] = key; //小区间优化 if (pivot - 1 - left < 10) { InsertSort(a+left, pivot - 1 - left + 1); } else { QuickSort(a, left, pivot - 1); } if (right - (pivot + 1) < 10) { InsertSort(a+pivot+1, right - (pivot + 1) + 1); } else { QuickSort(a, pivot + 1, right); } }
1.2.2 前后指针法：
基本思想：
目的都是与挖坑法一样，就是将选出的数排到正确的位置，先保存最左边元素；然后定义left为prev,下一位为cur,从cur开始向后找小，找到后就将++prev的值与cur交换，直至找到right，最后再将prev与保存的关键值交换直到cur访问到最后一个元素。最后别忘了将保存的下标值与下标为prev的元素交换。
具体代码实现：
int PartSort2(int* a, int left, int right) { int keyi = left; int prev = left; int cur = left + 1;; while (cur <= right) { while (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[keyi], &a[prev]); return prev; } void QuickSort2(int* a, int begin, int end) { if (begin >= end) { return; } int keyi = PartSort2(a, begin, end); QuickSort2(a, begin, keyi - 1); QuickSort2(a, keyi + 1, end); }
1.2.3 左右指针法
基本思想：
先保存最左边的值，从右边找比保存值小的元素，从左边找到比保存值大的元素，然后交换，直至相遇，再交换相遇点与保存值，将相遇点的下标返回。
具体代码实现：
int PartSort3(int* a, int left, int right) { int keyi = left; while (left < right) { while (left < right && a[right] >= a[keyi]) { right--; } while (left < right && a[left] <= a[keyi]) { left++; } if (left < right) { Swap(&a[left], &a[right]); } } int meeti = left; Swap(&a[keyi], &a[right]); return meeti; } void QuickSort3(int* a, int begin, int end) { if (begin >= end) { return; } int keyi = PartSort2(a, begin, end); QuickSort3(a, begin, keyi-1); QuickSort3(a, keyi + 1, end); }
