算法>排序算法浅谈
参考资料
评价指标
- 稳定性：两个相同的关键字排序过后相对位置不发生变化
- 时间复杂度
- 空间复杂度
- 适用性：是否适用于链表
可视化工具
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
概览
| 算法>排序算法 | 稳定性 | 平均时间复杂度 | 平均 空间复杂度 | 备注 |
|---|---|---|---|---|
| 插入排序 | 稳定 | O(n^2) | O(1) | 基本有序时时间复杂度接近O(n) |
| 折半插入排序 | 稳定 | O(n^2) | O(1) | 查找插入位置是使用折半查找 |
| 希尔排序 | 不稳定 | O(n^1.3) | O(1) | 利用基本有序可以降低插入排序时间复杂度的思想，将数据分组进行插入排序 |
| 冒泡排序 | 稳定 | O(n^2) | O(1) | 基本有序时时间复杂度接近O(n)，如果一趟冒泡排序过程中没有发生交换，则说明序列已经有序 |
| 快速排序 | 不稳定 | O(nlogn) | O(logn) | 每次至少确定一个元素位置 |
| 选择排序 | 不稳定 | O(n^2) | O(1) | 每—趟在待排序元素中选取关键字最小的元素加入有序子序列；时间复杂度与初始状态无关 |
| 堆排序 | 不稳定 | O(nlogn) | O(1) | 将序列初始化为堆，然后不断取堆顶元素，并不断调整堆使其保持堆的性质 |
| 归并排序 | 稳定 | O(nlogn) | O(n) | 不断递归合并两个有序序列 |
| 基数排序 | 稳定 | O(d(n+r)) | O® | 拆分成多个位，并按位的权重从小到大进行分配与收集 |
插入排序
- 算法思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。
- 稳定性：稳定
- 时间复杂度：最好
O(n)，平均O(n^2)，最坏O(n^2) - 特点： 当数组的元素基本有序，那么插入排序的时间复杂度接近O(n)
- 适用性：适用链表
/*** 插入排序* 每次将第i个元素，一次与前i个元素比较，正确地插入到[0, i]的序列中* 时间复杂度 O(n²)** 插入排序有提前终止的可能，效率比选择排序高一点* 当数组的元素基本有序，那么插入排序的时间复杂度接近O(n)* @param arr 待排序数组*/public static void insertionSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int num = arr[i];int j;// 前面的元素是否比当前元素大for (j = i; j > 0 && num < arr[j-1]; j--) {arr[j] = arr[j - 1];}arr[j] = num;}}/*** 整理思路重写，更容易理解一点* @param nums 待排序数组*/ public static void insertSort(int[] nums) {for (int i = 1; i < nums.length; i ++) {// 将每个nums[i]插入到前面已经排序好的序列for (int j = i; j > 0; j--) {// 遇到比自己小的元素则跳出循环// 由于前面的子序列有序，前面的元素更小，当前已经找到给nums[i]的位置if (nums[j - 1] <= nums[j]) {break;}// 自定义函数，交换数组中两个下标的元素swap(nums, j - 1, j);}}}
折半插入排序
- 算法思想：对于插入排序，要将元素插入到前面的有序序列，由于前面的序列已经有序，那么在查找插入位置时可以使用二分查找算法，也就是折半插入排序
- 稳定性：稳定
- 时间复杂度：相比于插入排序只能较少元素比较次数，无法减少元素移动的次数，平均时间复杂度依旧是
O(n^2) - 特点： 当数组的元素基本有序，那么插入排序的时间复杂度接近O(n)
- 适用性：不适用链表
/*** 折半插入排序* @param nums 待排序数组*/ public static void binaryInsertSort(int[] nums) {for (int i = 1; i < nums.length; i ++) {// 将每个nums[i]插入到前面已经排序好的序列// 利用二分查找确定第一个比nums[i]大的元素所在位置int low = 0, high = i - 1, n = nums[i];while (low < high) {int mid = low + (high - low) / 2;if (nums[mid] <= n) {low = mid + 1;} else if (nums[mid] > n){high = mid;}}// 前面的子序列不存在比nums[i]更大的数，不需要进行元素移动if (nums[high] < n) {continue;}// 将 high ~ i - 1的元素往后移一位for (int j = i - 1; j >= high; j --) {nums[j + 1] = nums[j];}// 将nums[i]放到对应的位置nums[high] = n;} }
希尔排序
- 算法思想：先将待排序表分割成若干形如 L[i, i +d, i + 2d…, i + kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。(n/2, n/4, n/8, …, 1)
- 稳定性：不稳定
- 时间复杂度：最坏
O(n^2)，平均O(n^1.3) - 适用性：不适用链表
/** * 希尔排序 * @param nums 待排序数组 */ public static void shellSort(int[] nums) {// 增量变化为nums.length/2, nums.length/4, ...// 当增量为1时，就是插入算法>排序算法for (int d = nums.length / 2; d >= 1; d /= 2) {// 每个子序列的第一个元素的位置for (int begin = 0; begin < d; begin ++) {// 对子序列nums[begin], nums[begin + d], nums[begin + 2d], ... 进行插入排序for (int i = begin + d; i < nums.length; i += d) {for (int j = i; j >= d; j -= d) {if (nums[j - d] <= nums[j]) {break;}swap(nums, j - d, j);}}}} }
冒泡排序
- 算法思想：从后往前（(或从前往后)两两比较相邻元素的值，若为逆序〈（即A[i-1]>A[i])，则交换它们，直到序列比较完。称这样过程为“一趟”冒泡排序。
如果一趟冒泡排序过程中没有发生交换，则说明序列已经有序。 - 稳定性：稳定
- 时间复杂度：最好
O(n)，平均O(n^2) - 适用性：适用于链表
- 特点： 当数组的元素基本有序，那么冒泡排序的时间复杂度接近O(n)
/*** 冒泡排序* @param nums 待排序数组*/ public static void bubbleSort(int[] nums) {for (int i = 0; i < nums.length - 1; i++) {// 用于标记这一趟冒泡是否有发生元素交换int swapFlag = 0;// 每一趟将[0, nums.length - i)中最大的元素放到最后，也就是下标为nums.length - i - 1for (int j = 1; j < nums.length - i; j ++) {if (nums[j - 1] > nums[j]) {swap(nums, j - 1, j);swapFlag = 1;}}// 如果这一趟没有发生元素交换，则说明序列已经有序if (swapFlag == 0) {break;}} }
快速排序
- 算法思想∶在待排序表L[1…n]中任取一个元素pivot作为枢轴（或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和LIk+1…n]，使得L[1…k-1]中的所有元素小于pivot，L[k+1…n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。
- 时间复杂度：平均最好
O(nlogn)，最坏O(n^2)（取决于每个划分是否均衡） - 空间复杂度：最好
O(logn)，最坏O(n) - 适用性：不适用于链表
- 稳定性：不稳定
简单选择排序
- 算法思想：每—趟在待排序元素中选取关键字最小的元素加入有序子序列
- 时间复杂度：
O(n^2)，无优化空间 - 适用性：适用于链表
- 稳定性：不稳定
/*** 每进行一次外层循环找出第i小的元素* 选择排序，升序* 每次都从 [i, n) 中找出最小的元素* 时间复杂度 O(n²)* @param arr 待排序数组*/
public static void selectionSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}swap(arr, i, minIndex);}
}
堆排序
- 大根堆：以完全二叉树顺序存储的方式来看一个数组，每个非终端节点都大于它的左(2i)右(2i+1)节点，非终端节点的编号
i <= n/2 - 算法思想：每一趟将堆顶元素加入有序子序列(与待排序序列中的最后一个元素交换)，并将待排序序列再次调整为大根堆
- 时间复杂度：建堆
O(n)，整体O(nlogn) - 空间复杂度：O(1)
- 适用性：不适用于链表
- 稳定性：不稳定
归并排序
- 算法思想：每次将两个有序子序列合并，递归到每个子序列大小为1
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
- 适用性：适用于链表
- 稳定性：稳定
public static void mergeSort(int[] arr) {mergeSort(arr, 0, arr.length - 1);
}/*** 把当前要排序的数组分成两半，层层递归，直至剩余一个元素* 将两半排序好的数组进行合并
*/
private static void mergeSort(int[] arr, int l, int r) {if (l >= r) {return;}int mid = l + (r-l)/2;mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);merge(arr, l, mid, r);
}private static void merge(int[] arr, int l, int mid, int r) {int[] aux = new int[r-l+1];for (int i = l; i <= r; i++) {aux[i-l] = arr[i];}int left = l;int right = mid + 1;for (int i = l; i <=r; i++) {if (left > mid) {arr[i] = aux[right - l];right ++;} else if (right > r) {arr[i] = aux[left - l];left ++;} else if (aux[left -l] < aux[right - l]) {arr[i] = aux[left - l];left ++;} else {arr[i] = aux[right - l];right ++;}}
}
基数排序
- 算法思想：分别以个位，十位，百位等（关键字权重递增，百位对关键字的大小影响更大）进行排序和收集
- 空间复杂度：O®
- 时间复杂度：O(d(n+r))
- 稳定性：稳定
- 应用场景
- 数据元素的关键字可以方便地拆分为d组，且d较小
- 每组关键字的取值范围不大，即r较小
- 数据元素个数n较大
