# 常见排序算法 参考极客时间《数据结构与算法之美》专栏整理 ## 常见排序算法对比 | 排序算法 | 时间复杂度 | 是否基于比较 | | ---------------- | ---------- | :----------- | | 冒泡、插入、选择 | O(n^2) | 是 | | 快排、归并 | O(nlogn) | 是 | | 桶、技术、基数 | O(n) | 否 | ## 排序算法的分析 ### 排序算法的执行效率 * 最好情况、最坏情况、平均时间复杂度 * 时间复杂度的系数、常数、低阶 在数据量n很大的时候我们会忽略系数、常数、低阶，但如果针对数据量情况较小（10、100、1000这种量级），就需要把系数、常数、低阶考虑进来 * 比较次数和交换（或移动）次数 基于比较的排序算法的执行过程中，会涉及到元素的交换或移动。所以分析排序算法的执行效率的时候，也应该把比较次数和交换（或移动）次数考虑进去 ### 排序算法的内存消耗 针对排序算法的空间复杂度，引入一个新的概念，**原地排序**（Sorted in place）。原地排序算法，就是特指空间复杂度是O(1)的排序算法。 ### 排序算法的稳定性 **稳定性**指的是如果待排序中存在值相等的元素，经过排序后，相等元素之间原有的顺序不变。例如，一批订单数据，先按时间从最近往前开始进行排序，然后再按照金额从高到低排序。在保证排序算法稳定性的情况下最后结果金额能从高到低的同时下，相同金额的订单能从最近开始往后排，显然这样的排序结果更具有意义。 ## 冒泡排序算法 `// 冒泡排序，a 表示数组，n 表示数组大小 public void bubbleSort(int[] a, int n) { if (n <= 1) return; for (int i = 0; i < n; ++i) { // 提前退出冒泡循环的标志位 boolean flag = false; for (int j = 0; j < n - i - 1; ++j) { if (a[j] > a[j+1]) { // 交换 int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; flag = true; // 表示有数据交换 } } if (!flag) break; // 没有数据交换，提前退出 } }` ## 插入排序算法 `// 插入排序，a 表示数组，n 表示数组大小 public void insertionSort(int[] a, int n) { if (n <= 1) return; for (int i = 1; i < n; ++i) { int value = a[i]; int j = i - 1; // 查找插入的位置 for (; j >= 0; --j) { if (a[j] > value) { a[j+1] = a[j]; // 数据移动 } else { break; } } a[j+1] = value; // 插入数据 } }` ## 选择排序算法