一.8种排序方式总览分析（带图）
1.按方式分类（比较排序）
*计数排序：非比较排序
二.8种排序方式详细解析
1.计数排序
注意：计数排序适合范围集中，且范围不大的整型数组排序。不适合范围分散或者非整型的排序，如：字符串、浮点数 等
步骤：
1.找到原数组最大的值，记作range
2.设置一个计数数组，遍历一遍原数组O(n)，统计每个数据出现的次数。
3.遍历一遍计数数组O(range)
计数排序分为：相对映射型和非相对映射型(相对位置）
图示意：
2.冒泡排序
遍历有序区间的各个数，从其开始到结尾的区间内轮转交换，不断缩小区间。
原理：不断把大/小的数移到后面
注意点：为提高效率，当发现一次循环中没有数对交换，即可中止循环。
void BubbleSort(int*a,int n) { int i = 0,j=0; for (j = 0; j<n; j++) { bool exchange = false; for (i = 0; i < n-j; i++) { if (a[i + 1] < a[i]) { Swap(&a[i + 1], &a[i]); exchange = true; } } //加入判断环节，提前终止，提高效率 if (exchange == false) { break; } } }
3.选择排序
遍历有序区间的各个数，找出其之后的最大/最小数并与该数之后的数进行替换。
代码的设计思路是设置left，right下标从数组两端向中间遍历，依次筛选出最大值和最小值mini，maxi，并分别与left，riight进行交换。
注意点：在交换过程中，left所处的位置可能正好被maxi标记，接下来下一步maxi与right的交换则会出错，right无法与正确的maxi交换。
解决方法：如果left和maxi重叠，交换后要修正
void SelectSort(int* a, int n) { int left = 0; int right = n; while (left < right) { int mini = left, maxi = right; for (int i =left+1; i <= right; i++) { if (a[i] > a[maxi]) { maxi = i;//移动下标 } if (a[i] < a[mini]) { mini = i; } } Swap(&a[left], &a[mini]); if (left == maxi) { maxi = mini; } Swap(&a[right], &a[maxi]); left++; right--; } }
4.插入排序
遍历有序区间的各个数，把其视作临时变量tmp，分别于它前面的数进行对比，
其进一步优化即为“希尔排序”
注意点：此算法中，当tmp比第一个数大/小时，end会到-1的位置。所以采用图中标记用法。
//升序 void InsertSort(int* a, int n)//a 数组 n 个数 { int i = 0; for (i = 1; i < n; i++) { int end = i - 1; int tmp = i; while (end >= 0) { if (a[tmp] < a[end]) { //整体后移 a[end + 1] = a[end]; --end; } else { break; } } //填空 a[end + 1] = a[tmp]; } }
5.希尔排序
其可以理解为在插入排序的基础上进行预排序（分组插排）
注意点：图示辅助理解循环：
void ShellSort(int* a, int n) { //gap==1 插入排序 //gap>1预先排序 int gap=n; //升序 while(gap>1) { gap = gap / 2; //gap=gap/3+1 确保gap的跳跃到最后为1， int i = 0; for (i = 0; i < n-gap; i++) { int end = i; int tmp = i+gap; while (end >= 0) { if (a[tmp] < a[end]) { //整体后移 a[end + gap] = a[end]; end -= gap; } else { break; } } //填空 a[end + gap] = a[tmp]; } } }
6.堆排序
详情可见博主关于堆排详解：
7.快速排序（递归和非递归写法）
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中的所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
注意点：当快速排序接近二分(二叉树）的递归模式时，效率最高。因此引入“三数取中”优化代码：
int GetMidNumi(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else // a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } }
1.三种排序方式
1.交换法
1.左边做key，右边先走——保证相遇位置比key小
ps：【右边先走找比key小的数，则其停止位置一定小于等于key】
2.由于左右相遇的位置一定比key小，把左边与相遇位置替换
图示：
代码：
2.挖坑法
1.先将左边第一个数据放在临时变量key中，原地形成一个坑位
2.右边先动，找小于key的数，放到坑位中，并且原地新生成一个坑位
3.当左右相遇时，将key填入最后一个坑位中
3.前后指针法（玩区间）
1.左边第一个数设为key，prev(延迟指针），cur（实时指针）
2.cur开始向右移动，找到比key小的值prev和cur同时移动
3.找到比key大的值只移动cur——保证prev和cur中间隔着一段比key大的区间
4.找到比key小的值时，交换prev下一个位置（比key大的区间）和cur位置的值——比key大的值翻到区间右边，把比key小的值翻到区间左边。
图示：
