常见排序的总结
插入排序
基本思想
每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的合适位置上去，直到元素全部插完为止
直接插入排序
代码实现
1//插入排序
2void InsertSort(int *arr, int n)
3{
4 int index = 0;
5 assert(arr);
6 for(index = 1; index < n; index++)
7 {
8 //将当前数据往前插入
9 int end = index-1;
10 int temp = arr[index];
11 while(end >= 0 && temp < arr[end])
12 {
13 arr[end+1] = arr[end];
14 --end;
15 }
16 arr[end+1] = temp;
17 }
18}
下图只是演示到将16排序到前面的过程
直接插入排序的优化
1//插入排序
2void InsertSort_OP(int *arr, int n)
3{
4 int index = 0;
5 for (index = 1; index < n; index++)
6 {
7 int temp = arr[index];
8 //通过二分查找 找出待插入元素的位置
9 int left = 0;
10 int right = index - 1;
11
12 while (left <= right)
13 {
14 int mid = left + ((right - left) >> 1);
15 if (temp >= arr[mid])
16 left = mid + 1;
17 else
18 right = mid - 1;
19 }
20
21 //将当前数据往前插入
22 int end = index - 1;
23 //搬移元素
24 while (end >= left)
25 {
26 arr[end + 1] = arr[end];
27 --end;
28 }
29 arr[left] = temp;
30 }
31}
由于之前的序列都是有序的，这样的话就不用一个一个进行比较，只要先用二分查找找到插入的位置，这样的话本来需要搬运元素只需要搬运一次就行，很多元素不需要比较一次就搬运一次，这样会提高效率！
总结
元素集合越接近有序，直接插入排序算法的时间效率越高！ 最优情况下：时间效率为$O(n)$ 最差情况下：时间复杂度为$O(n^2)$ 空间复杂度：$O(1)$，它是一种稳定的排序算法
希尔排序
又称缩小增量排序，是对直接插入排序的优化
很容易看出，经过这样的分组之后，许多比较大的数字都放在了后面，小数字都放在了前面，只要gap不断减小，分组不断变小，最后直到gap减到1的时候就和直接插入排序没什么区别了！
代码实现
1void ShellSort(int* arr,int len)
2{
3 int gap = len;
4 assert(arr);
5 while(gap>1)
6 {
7 gap = gap/3+1;
8 int cur = 0;
9 for(cur = gap;cur<len;++cur)
10 {
11 int end = cur-gap;
12 int tmp = arr[cur];
13 while(end>=0 && tmp<arr[end])
14 {
15 arr[end+gap] = arr[end];
16 end -= gap;
17 }
18 arr[end+gap] = tmp;
19 }
20 }
21}
总结
希尔排序是一种不稳定的排序，时间复杂度：$N^{1.25} 到 1.6N^{1.25}$
选择排序
基本思想
假设要排升序，每一趟选择一个最大的数字与最后的元素交换，这里所说的最后一个元素是会逐步向前调整的！
代码实现
1//选择排序
2void SelectSort(int *arr, int n)
3{
4 int index = 0;
5 assert(arr);
6 for (index = 0; index < n; index++)
7 {
8 int maxPos = 0;
9 int i = 1;
10 //找最大元素的位置
11 for (i = 1; i < n-index; i++)
12 {
13 if (arr[i] > arr[maxPos])
14 maxPos = i;
15 }
16 if (maxPos != (n - index - 1))
17 Swap(&arr[maxPos], &arr[n-index-1]);
18 }
19}
基本选择排序的优化
优化为每趟寻找最大值的同时找到最小值
1//选择排序的优化
2void SelectSort_OP(int *arr, int n)
3{
4 int begin = 0;
5 int end = n-1;
6
7 assert(arr);
8 while(begin < end)
9 {
10 int minindex = begin;
11 int maxindex = begin;
12 //分别找到最大和最小的下标
13 int i = 0;
14 for(i = begin;i <= end; ++i)
15 {
16 if(arr[i]>arr[maxindex])
17 {
18 maxindex = i;
19 }
20 if(arr[i]<arr[minindex])
21 {
22 minindex = i;
23 }
24 }
25 //把最小的放在前面，最大的放在后面
26 Swap(&arr[begin], &arr[minindex]);
27 if(begin == maxindex)//修正
28 maxindex = minindex;
29 Swap(&arr[end], &arr[maxindex]);
30 ++begin;
31 --end;
32 }
33}
只不过这种优化的方式需要注意一点（见下图），如果最小的元素恰好是最大的元素需要插入的位置，此时就需要将minPos设置为原来max的位置，因为最小值已经和maxPos位置的值交换了！
总结
时间复杂度：$n^2$ 空间复杂度：$O(1)$ 这是一种不稳定的排序
堆排序
堆排序有两个关键点
- 根据数组去建堆
- 交换首尾元素向下调整
代码实现
1void HeapAdjust(int *arr,int root,int len)
2{
3 //child是左孩子的下标
4 int child = root*2+1;
5 assert(arr);
6 while(child<len)
7 {
8 // 比较左孩子和右孩子,child指向大的孩子
9 if(child+1<len && arr[child+1]>arr[child])
10 {
11 child++;
12 }
13 // 1.若大的孩子节点大于根节点,则不再需要调整,跳出循环
14 // 2.否则,交换孩子节点和根节点,将根节点继续往下调整
15 if (arr[child] > arr[root])
16 {
17 Swap(&arr[child], &arr[root]);
18 root = child;
19 child = child * 2 + 1;
20 }
21 else
22 return;
23 }
24}
25//堆排序
26void HeapSort(int *arr, int len)
27{
28 int i = (len - 2)>>1;
29 assert(arr);
30 //建堆
31 for( ; i>=0; i--)
32 HeapAdjust(arr, i, len);
33 //排序
34 for(i = len-1;i > 0; i--)
35 {
36 Swap(&arr[i], &arr[0]);
37 HeapAdjust(arr, 0, i);
38 }
39}
总结
堆排序的时间复杂度：$N/2 *{log N}$其实就是$logN$ 空间复杂度：$O(1)$ 稳定性：不稳定
交换排序
冒泡排序
冒泡排序的思想非常简单，如下图，两两比较，每趟排序总可以把最大的放在最后面或者最小的值放在最后面，只需要进行（假设元素个数为n）n-1趟冒泡，便可以排序完成！
代码实现
1// 冒泡排序及其优化
2void BubbleSort(int* arr, int len)
3{
4 int index = 0;
5 int end = 0;
6 assert(arr);
7 for(end = len-1;end>0;end--)
8 {
9 int flag = 0;
10 for(index=0;index<end;index++)
11 {
12 if(arr[index]>arr[index+1])
13 {
14 Swap(&arr[index], &arr[index+1]);
15 flag = 1;
16 }
17 }
18 if(flag == 0)
19 break;
20 }
21}
总结
冒泡排序最好情况时间复杂度$O(n)$，冒泡排序最坏情况下时间复杂度 $O(1)$ 冒泡排序空间复杂度$O(1)$ 冒泡排序是一种稳定的排序算法
快速排序
基本思想
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
这样的话左边都是比基准值小的，在右边的都是比基准值大的，根据分治的思想，可以再把左边的序列选出一个基准值，在右边的序列也选择一个基准值，左边的排好了，右边的排好了，整个序列也就排好了！
代码实现_hoare版本
1//快速排序
2int PartSort(int *a, int left, int right)
3{
4 int key = a[right];
5 int begin = left;
6 int end = right - 1;
7 while (begin < end)
8 {
9 //找比基准值大的
10 while ((begin < end) && (a[begin] <= key))
11 begin++;
12 //找比基准值小的
13 while ((begin < end) && (a[end] >= key))
14 end--;
15 if (begin<end)
16 Swap(&a[begin], &a[end]);
17 }
18 //最后别忘记把基准值和相遇点交换
19 if (begin != right - 1)
20 Swap(&a[begin], &a[right-1]);
21 return begin;
22}
23void QuickSort(int *a, int left, int right)
24{
25 assert(a);
26 if (left >= right)
27 return;
28 int div = PartSort(a, left, right);
29 QuickSort(a, left, div);
30 QuickSort(a, div + 1, right);
31}
前后指针法
这个方式其实不难理解，就是每次将key值移动到中间，在key左边的值都是比key小的值，key右边的值都是比key大的值，这样做分组的的话通过递归就可以完成排序！
1int PartSort3(int *array, int left, int right)
2{
3 int key = array[right - 1];
4 int cur = left;
5 int pre = cur - 1;
6 while (cur < right)//说明区间的元素还没有遍历完成
7 {
8 if ((array[cur] < key) && (++pre != cur))
9 Swap(&array[cur], &array[pre]);
10 ++cur;
11
12 }
13 if (++pre != right)
14 Swap(&array[pre], &array[right-1]);
15 return pre;
16}
17void QuickSort3(int *a, int left, int right)
18{
19 assert(a);
20 if (left >= right)
21 return;
22 int div = PartSort3(a, left, right);
23 QuickSort(a, left, div - 1);
24 QuickSort(a, div + 1, right);
25}