【数据结构】排序

目录

1. 排序的分类

2. 常见的排序算法

2.1 直接插入排序

2.2 希尔排序（缩小增量排序）

2.3 选择排序

2.4 堆排序

2.5 冒泡排序

2.6 快速排序

2.7 归并排序

2.8 计数排序

2.9 桶排序

---

1. 排序的分类

内部排序：数据元素全部在内存中的排序

外部排序：数据元素太多而不能同时放在内存中，根据排序的过程而在内外存之间移动数据的结果

2. 常见的排序算法

2.1 直接插入排序

public class insertSort {/*** 插入排序* 时间复杂度：O(N^2)* 空间复杂度：O(1)* 稳定性：稳定* 数据越有序，直接插入排序越快* 最好情况下：数据本身就有序，时间复杂度为O(N)** @param arr*/public static void insertSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int tmp = arr[i];int j = i - 1;for (; j >= 0; j--) {if (arr[j] > tmp) arr[j + 1] = arr[j];else {arr[j + 1] = tmp;break;}}arr[j + 1] = tmp;}}public static void main(String[] args) {int[] arr = {10, 2, 5, 7};insertSort(arr);for (int x : arr) System.out.print(x + " ");//2 5 7 10 }
}

2.2 希尔排序（缩小增量排序）

基本思想：选定一个整数N，把待排序文件中所有记录分成多个组，所有距离为N的记录分在同一组，对每组记录进行排序，重复上述分组和排序工作，当N==1时，记录排好序。

    /*** 希尔排序——直接插入排序的一种优化* 时间复杂度：不好计算（gap不固定）* 空间复杂度：O(1)** @param arr*/public static void shellSort(int[] arr) {int gap = arr.length;while (gap > 1) {gap /= 2;shell(arr, gap);}}private static void shell(int[] arr, int gap) {for (int i = gap; i < arr.length; i++) {int tmp = arr[i];int j = i - gap;for (; j >= 0; j--) {if (arr[j + gap] > tmp) arr[j + gap] = arr[j];else {arr[j + gap] = tmp;break;}}arr[j + gap] = tmp;}}

希尔排序的特性：

1. 希尔排序是对直接插入排序的优化
2. 当gap>1时是预排序，目的是让数组更接近有序。当gap==1时，数组已经接近有序
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，因此希尔排序的时间复杂度不固定
4. 是不稳定的

2.3 选择排序

基本思想：每次从待排序数据元素中选出最小（或最大）元素，与起始数据进行交换，直到全部数据元素排完

    /*** 选择排序* 时间复杂度：O(N^2)* 空间复杂度：O(1)* 稳定性：不稳定** @param arr*/public static void selectSort(int[] arr) {for (int i = 0; i < arr.length; i++) {int minindex = arr[i];for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minindex]) {minindex = j;}}swap(arr, i, minindex);}}/*** 对于上个选择排序进行优化（两端同时排序）* @param arr*/public static void selectSort2(int[] arr) {int left = 0, right = arr.length - 1;while (left < right) {int minindex = left, maxindex = right;for (int i = left + 1; i <= right; i++) {if (arr[i] > arr[maxindex]) maxindex = i;if (arr[i] < arr[minindex]) minindex = i;}swap(arr, left, minindex);if (maxindex == left) maxindex = minindex;// 最大值正好是left下标，此时把最大值换到了 minindex 的位置swap(arr, right, maxindex);left++;right--;}}

 直接选择排序特性总结：

1. 好理解，但效率不高，很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

2.4 堆排序

    /*** 时间复杂度：O(N*logN)* 空间复杂度：O(1)* 稳定性：不稳定** @param arr*/public static void heapSort(int[] arr) {createHeap(arr);int end = arr.length - 1;while (end > 0) {swap(arr, 0, end);siftDown(arr, 0, end);end--;}}private static void createHeap(int[] arr) {for (int parent = (arr.length - 1) / 2; parent >= 0; parent--) {siftDown(arr, parent, arr.length);}}/*** @param arr* @param parent 每棵子树调整的根节点* @param length 每棵子树调整的结束节点*/private static void siftDown(int[] arr, int parent, int length) {int child = 2 * parent + 1;while (child < length) {if (child + 1 < length && arr[child] < arr[child + 1]) child++;if (arr[child] > arr[parent]) {swap(arr, parent, child);parent = child;child = 2 * parent + 1;} else {break;}}}

2.5 冒泡排序

    /*** 冒泡排序* 时间复杂度：O(N^2)（讨论的是不优化的情况下，即没有boolean元素和-i操作）* 空间复杂度：O(1)* 稳定性：稳定** @param arr*/public static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {boolean flg = false;for (int j = 0; j < arr.length - i; j++) {if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);flg = true;}if (!flg) break;//已经有序}}

2.6 快速排序

是一种基于二叉树结构的交换排序方法

基本思想：任取待排序序列中某元素作为基准值，以该元素为基准，将待排序序列分成两个子序列，左子序列元素均小于基准值，右子序列元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应的位置上为止

1. Hoare法

    /*** 快速排序* 时间复杂度：* 最差情况：O(N^2)（当待排序序列已经从小到大排好序时）* 最好情况：O(N*logN)* 空间复杂度：* 最坏情况：O(N)* 最好情况：O(logN)* 稳定性：不稳定** @param arr*/public static void quickSort(int[] arr) {quick(arr, 0, arr.length - 1);}private static void quick(int[] arr, int start, int end) {if (start >= end) return;int pivot = partition(arr, start, end);quick(arr, start, pivot - 1);quick(arr, pivot + 1, end);}private static int partition(int[] arr, int left, int right) {int tmp = arr[left];int tmpLeft = left;while (left < right) {while (left < right && arr[right] >= tmp) right--;while (left < right && arr[left] <= tmp) left++;swap(arr, left, right);}swap(arr, left, tmpLeft);return left;}

2. 挖坑法

    /*** 挖坑法* 优先考虑（常考）** @param arr* @param left* @param right* @return*/private static int partitionHole(int[] arr, int left, int right) {int tmp = arr[left];while (left < right) {while (left < right && arr[right] > tmp) right--;arr[left] = arr[right];while (left < right && arr[left] <= tmp) left++;arr[right] = arr[left];}arr[left] = tmp;return left;}

3. 前后指针法

    /*** 前后指针法** @param arr* @param left* @param right* @return*/private static int partition(int[] arr, int left, int right) {int prev = left;int cur = left + 1;while (cur <= right) {if (arr[cur] < arr[left] && arr[++prev] != arr[cur]) swap(arr, cur, prev);cur++;}swap(arr, prev, left);return prev;}

2.7 归并排序

基本思想：采用分治法，将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

递归代码：

    public static void mergeSort(int[] arr) {mergeSortTmp(arr, 0, arr.length - 1);} /*** 归并排序* 时间复杂度：O(N*logN)* 空间复杂度：O(N)* 稳定性：稳定** @param arr* @param left* @param right*/private static void mergeSortTmp(int[] arr, int left, int right) {if (left >= right) return;int mid = (left + right) / 2;mergeSortTmp(arr, left, mid);mergeSortTmp(arr, mid + 1, right);// 已全部分解完毕// 开始合并：merge(arr, left, mid, right);}private static void merge(int[] arr, int left, int mid, int right) {int[] tmp = new int[right - left + 1];int k = 0, s1 = left, s2 = mid + 1;while (s1 <= mid && s2 <= right) {if (arr[s1] <= arr[s2]) tmp[k++] = arr[s1++];else tmp[k++] = arr[s2++];}while (s1 <= mid) tmp[k++] = arr[s1++];while (s2 <= right) tmp[k++] = arr[s2++];// 此时tmp数组有序for (int i = 0; i < k; i++) {arr[i + left] = tmp[i];}}

外部排序：排序过程需要在磁盘等外部存储进行的排序

前提：内存只有1G，需要排序的数据有100G

因为内存中无法把所有数据都存下，需要外部排序。归并排序是最常用的外部排序

非递归代码：

    private static void mergeSortNor(int[] arr) {int gap = 1;while (gap < arr.length) {for (int i = 0; i < arr.length; i = i + gap * 2) {int left = i;int mid = left + gap - 1;if (mid >= arr.length) mid = arr.length - 1;int right = mid + gap;if (right >= arr.length) right = arr.length - 1;merge(arr, left, mid, right);}gap *= 2;}}

2.8 计数排序

计数排序又称鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：

1. 统计相同元素出现次数
2. 根据统计结果将序列回收到原来的序列中

2.9 桶排序

桶排序是一种基于分布的排序算法，它将元素分散到几个桶中，然后对每个桶分别排序，最后合并所有桶中的元素。桶排序适用于均匀分布的输入，能够在平均情况下达到线性时间复杂度。