本文共 6076 字，大约阅读时间需要 20 分钟。
特点：stable sort、In-place sort
最优复杂度：当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度。 最差复杂度：当输入数组为倒序时，复杂度为O(n^2) 插入排序比较适合用于“少量元素的数组”。其实插入排序的复杂度和逆序对的个数一样，当数组倒序时，逆序对的个数为n(n-1)/2，因此插入排序复杂度为O(n^2)。
void InsertSort(vector & res){ int temp; for (int i = 1; i < res.size(); i++){ temp = res[i]; int j = i - 1; while (j >= 0 && temp < res[j]){ res[j + 1] = res[j]; --j; } res[j + 1] = temp; }} void ShellSort(vector & res){ int size = res.size(); int separate = size / 2; while (separate > 0){ for (int i = separate; i < size; i++){ int temp = res[i]; int j = i - separate; while (j >= 0 && temp < res[j]){ res[j + separate] = res[j]; j -= separate; } res[j + separate] = temp; } separate /= 2; }} 特点：stable sort、In-place sort
思想：通过两两交换，像水中的泡泡一样，小的先冒出来，大的后冒出来。 最坏运行时间：O(n^2) 最佳运行时间：O(n^2)（当然，也可以进行改进使得最佳运行时间为O(n)）//冒泡排序，每次让最大的数沉下去void BubbleSort(vector &res){ for (int i = 0; i < res.size(); i++){ for (int j = 0; j < res.size() - i - 1; j++){ if (res[j] > res[j + 1])swap(res[j], res[j + 1]); } }}//设置一个flag，若在一次循环中无交换则不进行下一次循环//最佳运行时间O(N)void BubbleSort_optimize(vector &res){ bool flag = true; for (int i = 0; i < res.size() && flag; i++){ flag = false; for (int j = 0; j < res.size() - i - 1; j++){ if (res[j] > res[j + 1])swap(res[j], res[j + 1]), flag = true; } }} 冒泡排序和插入排序哪个更快？
一般的人回答：“差不多吧，因为渐近时间都是O(n^2)”。
但事实上不是这样的，插入排序的速度直接是逆序对的个数，而冒泡排序中执行“交换”的次数是逆序对的个数，因此冒泡排序执行的时间至少是逆序对的个数，因此插入排序至少比冒泡排序块。特性：In-place sort，unstable sort。
思想：每次找一个最小值。 最好情况时间：O(n^2)。 最坏情况时间：O(n^2)。void SelectSort(vector &res){ for (int i = 0; i < res.size() - 1; i++){ int temp = i; for (int j = i + 1; j < res.size(); j++){ if (res[j] < res[temp]){ temp = j; } } if (temp != i)swap(res[i], res[temp]); }} 特点：stable sort、Out-place sort
思想：运用分治法思想解决排序问题。 最坏情况运行时间：O(nlgn) 最佳运行时间：O(nlgn)分治法介绍：
分治法就是将原问题分解为多个独立的子问题，且这些子问题的形式和原问题相似，只是规模上减少了，求解完子问题后合并结果构成原问题的解。 分治法通常有3步： 1）Divide（分解子问题的步骤）； 2）Conquer（递归解决子问题的步骤）； 3）Combine（子问题解求出来后合并成原问题解的步骤）； 假设Divide需要f(n)时间，Conquer分解为b个子问题，且子问题大小为a，Combine需要g(n)时间，则递归式为： T(n)=bT(n/a)+f(n)+g(n) ——>T(n) = 2T(n/2) + O(n)void merge(vector &res, int first, int mid, int last, vector temp){ int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n){ if (res[i] < res[j])temp[k++] = res[i++]; else temp[k++] = res[j++]; } while (i <= m)temp[k++] = res[i++]; while (j <= n)temp[k++] = res[j++]; for (i = 0; i < k; i++)res[first + i] = temp[i];}void mergeSort(vector & res, int first, int last, vector temp){ if (first < last){ int mid = first + (last - first) / 2; mergeSort(res, first, mid, temp); mergeSort(res, mid + 1, last, temp); merge(res, first, mid, last, temp); }}bool MergeSort(vector & res){ vector temp(res.size()); mergeSort(res, 0, res.size() - 1, temp); return true;} 归并排序的缺点是什么？
它是out-place sort，因此相比块排，需要额外的空间；为什么归并总比块排慢？
虽然渐进复杂度一样，但是归并排序的系数比块排大；对于归并排序有什么改进？
就是在数组长度为K时，用插入排序，因为插入排序适合对小数组排序，此时复杂度为O(nk+nlg(n/k))，当k = lg(n)时，复杂度为O(nlgn)；特性：unstable sort、In-place sort。
最坏运行时间：当输入数组已排序时，时间为O(n^2)，当然可以通过随机化来改进（shuffle array 或者 randomized select pivot）,使得期望运行时间为O(nlgn)。 最佳运行时间：O(nlgn)int Partition(vector & res, int low, int high){ int PivotKey = res[low]; while (low < high){ while (low < high && res[high] > PivotKey)high--; res[low] = res[high]; while (low < high && res[low] <= PivotKey)low++; res[high] = res[low]; } res[low] = PivotKey; return low;}void qSort(vector &res, int low, int high){ int pivot; int mid = low + (high - low) / 2; if (res[low] > res[high])swap(res[low], res[high]); if (res[mid] > res[high])swap(res[mid], res[high]); if (res[mid] > res[low])swap(res[mid], res[low]); if (low < high){ pivot = Partition(res, low, high); qSort(res, low, pivot - 1); qSort(res, pivot + 1, high); }}void QuickSort(vector &res){ qSort(res, 0, res.size() - 1);} 特性：unstable sort、In-place sort。
最优时间：O(nlgn) 最差时间：O(nlgn)typedef int ElementType;void AdjustDown(ElementType res[], int i, int len){ ElementType temp = res[i]; for (int largest = 2 * i + 1; largest < len; largest = 2 * largest + 1){ if (largest != len - 1 && res[largest] > res[largest + 1]){ // > 换成 <,则为大顶堆 ++largest; } if (temp > res[largest]){ // < 换成 >,则为大顶堆 res[i] = res[largest]; i = largest; } else break; } res[i] = temp;}void BuildMaxHeap(ElementType res[], int len){ for (int i = len / 2 - 1; i >= 0; i--){ AdjustDown(res, i, len); }}void HeapSort(ElementType res[], int n){ BuildMaxHeap(res, n); for (int i = n - 1; i > 0; i--){ //交换方法，避免数值越界 res[0] = res[0] ^ res[i]; res[i] = res[0] ^ res[i]; res[0] = res[0] ^ res[i]; AdjustDown(res, 0, i); }} 特性：stable sort、Out-place sort。
最坏情况运行时间：O((n+k)d) 最好情况运行时间：O((n+k)d)const int RAD_IX = 10; //最高位为10位int GetNumInPos(int num, int pos){ int temp = pow(10, pos - 1); return (num / temp) % 10;}void RadixSort(vector & res){ for (int pos = 1; pos <= RAD_IX; pos++){ vector > radixArrary(RAD_IX, vector ()); //按照第pos位，将对应元素存储在指定的数组内 for (int i = 0; i < res.size(); i++){ int num = GetNumInPos(res[i], pos); radixArrary[num].push_back(res[i]); } //将桶中元素按照pos位重新存储在数组内 for (int i = 0, j = 0; i < RAD_IX; i++){ for (auto x : radixArrary[i]){ res[j++] = x; } } }} 转载地址：http://cxxei.baihongyu.com/