1.比较排序：
1）.插入排序（直接插入排序、希尔排序）
2）.选择排序（选择排序、堆排序）
3）.交换排序（冒泡排序、快速排序）
4）.归并排序（归并排序）
2.非比较排序：
1）.计数排序
2）.基数排序（LSD、MSD）
那么我将会给出以上所有排序的思想及代码实现！（假设所有排序都以升序为例）
一、直接插入排序（测试用例：2、5、4、9、3、6、8、7、1、0）
1）、主要思想
2）、主要代码实现
void InsertSort(int *a, size_t n) //插入排序 { assert(a); for (size_t i = 0; i < n - 1; ++i) { int end = i; int tmp = a[end + 1]; while (end >= 0) { if (tmp < a[end]) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = tmp; } }二、希尔排序
该排序是在直接插入排序的基础上，进行了优化，基本思想一致。
只不过是进行了分组
1）、主要思想
同一颜色表示同一组，然后对每组分别进行直接插入排序（缩小间距继续进行重复操作（gap = gap / 3 + 1））
2）、主要代码
void ShellSort(int* a, size_t n) //希尔排序（是对插入排序的优化） { assert(a); int gap = n; while (gap > 1) { gap = gap / 3 + 1; for (size_t i = gap; i < n; ++i) { int end = i - gap; int tmp = a[end + gap]; while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }三、选择排序
1）、主要思想
每次选出一个最大的和最后一个元素交换，这样最后一个元素就已经放好了，然后将这个排好的数的位置忽略（将排好的这个数的位置不看做是数组里边的），重复进行上述操作
2）、主要代码
void SelectSort(int* a, size_t n) //选择排序 { assert(a); for (size_t i = 0; i < n; ++i) { size_t minIndex = i; for (size_t j = i + 1; j < n; ++j) { if (a[minIndex] > a[j]) minIndex = j; } swap(a[i], a[minIndex]); } } 3）、优化 每次找出一个最小的和最大的，分别和数组的第一个元素、最后一个元素交换，然后忽略这两个位置，进行重复操作。 注意：有可能最大的数在开始位置、最小数在最后的位置，这样交换的时候会出错。 void SelectSortOptimize(int* a, size_t n) //对选择排序的优化 { assert(a); for (size_t i = 0; i < n; ++i) { size_t minIndex = i; size_t maxIndex = i; for (size_t j = i + 1; j < n-i; ++j) { if (a[minIndex] > a[j]) minIndex = j; if (a[maxIndex] < a[j]) maxIndex = j; } swap(a[i], a[minIndex]); if (a[maxIndex] == a[i]) { maxIndex = minIndex; } swap(a[n-1-i], a[maxIndex]); } } 四、堆排序 1）、主要思想 利用堆的原理，其堆顶的元素总是最大的（大堆），因此每次可以取到最大的这个元素，和最后一个元素交换，这样最后一个元素就排好了（此处和选择排序相似），不过交换后堆的结构有可能被破坏，因此需要重新调堆。 2）、主要代码 void AdjustDown(int* a, int n, int rootIndex)//向下调整算法 { int parent = rootIndex; int child = parent * 2 + 1; //左孩子 while (child < n) { if (child + 1 < n && a[child] < a[child + 1]) //找左右孩子中最大的那一个的下标 ++child; if (a[child] > a[parent]) { swap(a[child], a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int* a, size_t n)//堆排序 { assert(a); for (int i = (n - 1 - 1) / 2; i >= 0; --i) // 建堆（从倒数最后一个叶子节点的父亲开始依次向下调整） { AdjustDown(a, n, i); } for (size_t i = n-1; i > 0; --i) { swap(a[0], a[i]); AdjustDown(a, i, 0); } }
五、冒泡排序
1）、较为简单、不做详解
2）、主要代码
void BubbleSort(int* a, size_t n) { assert(a); for(int i=0;i<n-1;++i) { for(int j=0;j<n-1-i;++j) { if(a[j]>a[j+1]) { swap(a[j],a[j+1]); } } } }六、快速排序
快速排序是一个较快、但是较为复杂的一个排序。
主要有：左右指针法、前后指针法、挖坑法
优化：三数取中法、小区间优化法
1）、左右指针法（单趟排序）
int SinglePassSort(int *a, int left, int right) //单趟的快速排序（左右指针法） { assert(a); size_t key = right; while (left < right) { while (left < right && a[left] <= a[key]) //9876543210 { ++left; } while (left < right && a[right] >= a[key]) { --right; } swap(a[left], a[right]); } swap(a[left], a[key]); return left; } 2）、挖坑法（类似于左右指针法） int SinglePassSortTwo(int* a, int left, int right)//单趟的快速排序（挖坑法） { assert(a); int tmp = a[right]; //刚开始吧坑挖在最右边 while (left < right) { while (left < right && a[left] <= tmp) { ++left; } a[right] = a[left]; while (left < right && a[right] >= tmp) { --right; } a[left] = a[right]; } a[left] = tmp; return left; } 3）、前后指针法
int SinglePassSortThree(int* a, int left, int right)//单趟的快速排序（前后指针法） { assert(a); int key = right; int cur = left; int prev = cur - 1; while (cur < right) { if (a[cur] <= a[key] && ++prev < cur) swap(a[prev], a[cur]); ++cur; } swap(a[++prev], a[key]); return prev; }
4）、总的排序（以前后指针法为例）（递归思想）
其类似于一个二叉树的先序
void QuickSort(int*a, int left, int right)//快速排序 O（N*LgN） { assert(a); if (left < right) { int div = SinglePassSortThree(a, left, right); QuickSort(a, left, div - 1); //以div为中心左边区间 QuickSort(a, div + 1, right); //以div为中心右边区间 } }4）三数取中法优化
取数组中第一个，最后一个，最中间的一个这三个数中的中间值，作为参考值
int GetMidOfThree(int* a, int left, int right) // 快排的优化（三数取中法） { int mid = left + ((right - left) >> 1); if (a[mid] < a[right]) { if (a[left] < a[mid]) return mid; else if (a[right]>a[left]) return left; else return right; } else // mid>right { if (a[left] > a[mid]) return mid; else if (a[left] > a[right]) return left; else return right; } } int SinglePassSortThree(int* a, int left, int right)//单趟的快速排序（前后指针法） { assert(a); int mid = GetMidOfThree(a, left, right); //利用三数取中法来优化 swap(a[mid], a[right]);//使参考值位于最后一个位置 int key = right; int cur = left; int prev = cur - 1; while (cur < right) { if (a[cur] <= a[key] && ++prev < cur) swap(a[prev], a[cur]); ++cur; } swap(a[++prev], a[key]); return prev; }
5）、小区间优化
由于递归压栈开销比较大，当数据量很大的时候，递归的深度就会很深，而深度越深，每次排序的数据越少，数据越少，使用快排的开销就越大。
那么，对于深度较深的这些小区间，可以采用直接插入排序来进行排序。
选择直接插入排序的原因：对接近于有序的一组数进行排序的时候，效率很高，而每次单趟的快速排序完成后，其都渐渐的接近有序
void QuickSort(int*a, int left, int right)//快速排序 O（N*LgN） { assert(a); if (left < right) { if (right - left + 1 < 20) //利用小区间优化，减少递归压栈 { InsertSort(a + left, right - left + 1); } else { int div = SinglePassSortThree(a, left, right); QuickSort(a, left, div - 1); //以div为中心左边区间 QuickSort(a, div + 1, right); //以div为中心右边区间 } } }
6）、非递归实现快速排序
#include <stack> void QuickSortNonR(int* a, size_t n) //快速排序的非递归 { assert(a); int left = 0; int right = n - 1; stack<int> s; s.push(right); s.push(left); while (!s.empty()) //栈不为空就循环 { left = s.top(); s.pop(); right = s.top(); s.pop(); int div = SinglePassSortThree(a,left,right); //左右指针法 if (div - 1 > left) { s.push(div - 1); s.push(left); } if (right > div + 1) { s.push(right); s.push(div+1); } } }七、归并排序
1）、主要思想
其类似于快速排序的递归思想，并且又类似于两个有序单链表的合并。
2）、主要代码
void Merger(int* a, int left, int mid, int right, vector<int> v) //对两个区间进行归并（此处类似于两个有序单链表的合并） { int begin1 = left; int end1 = mid; int begin2 = mid+1; int end2 = right; int index = begin1; while (begin1 <= end1 && begin2 <= end2) { if(a[begin1] < a[begin2]) { v[index++] = a[begin1++]; } else { v[index++] = a[begin2++]; } } while (begin1 <= end1) { v[index++] = a[begin1++]; } while (begin2 <= end2) { v[index++] = a[begin2++]; } for (int i = left; i <= right; ++i) { a[i] = v[i]; } } void _MergerSort(int* a, int left,int right, vector<int> v) { if (left >= right) return; size_t mid = left + ((right - left) >> 1); _MergerSort(a, left, mid, v); _MergerSort(a, mid+1, right, v); Merger(a, left, mid, right, v); } void MergerSort(int* a, size_t n) { vector<int> v; v.resize(n); _MergerSort(a,0,n-1,v); } 八、基数排序（LSD） 1）、主要思想 对所有的数取个位，并且全部放在一个桶中，其大小为多少，就放在桶中的对应的下标的位置中，依次类推继续取十位、百位、直到所有的位全部取完 2）、主要代码 int GetMaxBit(int* a, size_t n) //获取这组数中最大的数的位数 { int base = 10; int count = 1; for (size_t i = 0; i < n; ++i) { while (a[i] >= base) { count++; base *= 10; } } return count; } void LSDSort(int* a, size_t n) // { int maxBit = GetMaxBit(a, n); int base = 1; vector<vector<int>> v; v.resize(10); for (int i = 0; i < maxBit; ++i)//循环最大的位数次 { for (size_t j = 0; j < n; ++j) { int bit = (a[j] / base) % 10; v[bit].push_back(a[j]); } int index = 0; for (size_t j = 0; j < v.size(); ++j) { for (size_t z = 0; z < v[j].size(); ++z) { a[index++] = v[j][z]; } v[j].clear(); } base *= 10; } }
所有排序之间的比较：
注意：1.其中稳定性的意思是：如果一组数中有两个相同的数，在完成排序后，如果这两个数的位置没有进行调换，则稳定，反之，不稳定。
2.直接插入排序最好的情况是：排升序接近升序，排降序接近降序
