目录
1. 概念
1.1 排序
排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。平时的上下文中,如果提到排序,通常指的是排升序(非降序)。
通常意义上的排序,都是指的原地排序(in place sort)。
1.2 稳定性(重要)
两个相等的数据,如果经过排序后,排序算法能保证其相对位置不发生变化,则我们称该算法是具备稳定性的排序算法。
(简单来说,就是一串数字有两个相同数据,若排序后两个数据的前后位置关系未发生改变就稳定,如果前后位置关系改变,则不稳定)
1.3 应用
例如:2022.2 TOP 12编程语言
编辑
2. 七大基于比较的排序-总览
编辑
2.1 内部排序 & 外部排序
a.内部排序(在内存中)
此处的七大排序都是内部排序,其中直接插入排序、冒泡排序、归并排序都是稳定排序。
b.外部排序(依赖硬盘)
有桶排序、基数排序、计数排序,时间复杂度都为O(n),且对数据要求很高,须在特定场合使用。
3. 七大排序
编辑
0: 交换三连
(之后每个排序代码都需要调用此代码)
(排序时交换两数位置要用到,因排序多次用到交换,所有我们单独写个方法,直接调用即可)
//交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
1. 冒泡排序
1.1概念
在无序区间,通过相邻数的比较,将最大的数冒泡到无序区间的最后,持续这个过程,直到数组整体有序。(从前到后两两比较交换,大数放后,每层都是将较大数放在在最后位置)
1.2 实现
//1.冒泡排序 public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { boolean isSorted = false; for (int j = 0; j < arr.length - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); //当 isSorted 为 true 时说明当前存在交换 isSorted = true; } } // 当 isSorted 不为 true 时说明当前层不存在交换,数据已经有序,结束循环即可 // 减少时间复杂度 if (!isSorted) { break; } } } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
1.3 性能分析
编辑
2. 选择排序
a. 单向选项排序
每一次从无序区间选出最大(或最小)的一个元素,存放在无序区间的最后(或最前),直到全部待排序的数据元素排完 。
//2.1单向选择排序 public static void selectionSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int min = i; for (int j = i + 1; j < arr.length; j++) { //遍历当前层剩下的元素,找到最小数的索引 if (arr[min] > arr[j]) { min = j; } } //将最小数放在当前 i 的位置 swap(arr, min, i); } } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
编辑
b. 双向选项排序
每一次从无序区间选出最小 + 最大的元素,存放在无序区间的最前和最后,直到全部待排序的数据元素排完 。
//2.2双向选择排序 public static void selectionSortOP(int[] arr) { int low = 0; int high = arr.length - 1; // low = high,无序区间只剩下一个元素,数组已经有序 while (low <= high) { int min = low; int max = low; ////遍历当前层剩下的元素,分别找到最小数和最大数的索引 for (int i = low + 1; i <= high; i++) { if (arr[min] > arr[i]) { min = i; } if (arr[max] < arr[i]) { max = i; } } swap(arr, min, low); if (max == low) { // 最大值在上一步swap已经被换到min这个位置 max = min; } swap(arr, max, high); low += 1; high -= 1; } } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
3. 直接插入排序
a. 直接插入排序
整个区间被分为 有序区间 和 无序区间,每次选择无序区间的第一个元素,在有序区间合适位置插入。
// 3.1直接插入排序 // 每次从无序区间中拿第一个值插入到已经排序区间的合适位置,直到整个数组有序 public static void insertionSort(int[] arr) { // 已排序区间[0,i) // 待排序区间[i...n] for (int i = 1; i < arr.length; i++) { // 待排序区间的第一个元素arr[i] // 从待排序区间的第一个元素向前看,找到合适的插入位置 for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) { swap(arr, j, j - 1); } } } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
编辑
b. 折半插入排序
在有序区间选择数据应该插入的位置时,因为区间的有序性,可以利用折半查找的思想。
// 3.2直接插入排序(已排序区间两端插入,插入时使用二分法) public static void insertionSortBS(int[] arr) { // 有序区间[0..i) // 无序区间[i...n] for (int i = 1; i < arr.length; i++) { int val = arr[i]; int left = 0; int right = i; //在有序区间,二分法找到 value 的位置 while (left < right) { int mid = left + ((right - left) >> 1); if (val < arr[mid]) { right = mid; } else { // 当val >= arr[mid] left = mid + 1; } } // 搬移left..i的元素 for (int j = i; j > left; j--) { arr[j] = arr[j - 1]; } // left就是val插入的位置 arr[left] = val; } }
4.希尔排序
4.1 概念
希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有 距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时, 所有记录在统一组内排好序。
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
编辑
4.2 实现
//4.希尔排序 public static void shellSort(int[] arr) { int gap = (arr.length - 1) >> 2; while (gap > 0) { // 按照gap分组进行插入排序 insertionSortByGap(arr, gap); gap = gap >> 1; } } // 类似于直接插入排序 private static void insertionSortByGap(int[] arr, int gap) { for (int i = gap; i < arr.length; i++) { for (int j = i; j - gap >= 0 && arr[j] < arr[j - gap]; j -= gap) { swap(arr, j, j - gap); } } } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
4.3 性能分析
编辑
5. 堆排序
5.1 概念
详见可看此处文章:《Java 堆 & 优先级队列》
基本原理也是选择排序,只是不在使用遍历的方式查找无序区间的最大的数,而是通过堆来选择无序区间的最大的数。
注意: 排升序要建大堆;排降序要建小堆。
编辑
5.2 实现
//5.堆排序 public static void heapSort(int[] arr) { // 1.先将arr进行heapify调整为最大堆 // 从最后一个非叶子节点开始进行siftDown操作 for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) { siftDown(arr, i, arr.length); } // 此时arr为最大堆 for (int i = arr.length - 1; i > 0; i--) { // arr[0] 堆顶元素,就是当前堆的最大值 swap(arr, 0, i); siftDown(arr, 0, i); } } private static void siftDown(int[] arr, int i, int length) { while (2 * i + 1 < length) { int j = (i << 1) + 1; if (j + 1 < length && arr[j + 1] > arr[j]) { j = j + 1; } // j就是左右子树的最大值 if (arr[i] > arr[j]) { // 下沉结束 break; } else { swap(arr, i, j); i = j; } } } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
5.3 性能分析
编辑
6.归并排序
a. 归并排序
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
编辑
实现:
//6.归并排序 public static void mergeSort(int[] arr) { mergeSortInternal(arr, 0, arr.length - 1); } //在arr[l...r]进行归并排序,整个arr经过函数后就是一个已经有序的数组 private static void mergeSortInternal(int[] arr, int l, int r) { if (r - l <= 0) { return; } int mid = l + ((r - l) >> 1); // 将原数组拆分为左右两个小区间,分别递归进行归并排序 // 走完这个函数之后 arr[l..mid]已经有序 mergeSortInternal(arr, l, mid); // 走完这个函数之后 arr[mid + 1..r]已经有序 mergeSortInternal(arr, mid + 1, r); // 1.只有左右两个子区间还有先后顺序不同时才merge if (arr[mid] > arr[mid + 1]) { merge(arr, l, mid, r); } } //在arr[l..r]使用插入排序 private static void insertionSort(int[] arr, int l, int r) { for (int i = l + 1; i <= r; i++) { for (int j = i; j > l && arr[j] < arr[j - 1]; j--) { swap(arr, j, j - 1); } } } //合并两个子数组arr[l..mid] 和 arr[mid + 1...r] private static void merge(int[] arr, int l, int mid, int r) { // 先创建一个新的临时数组aux int[] aux = new int[r - l + 1]; // 将arr元素值拷贝到aux上 for (int i = 0; i < aux.length; i++) { aux[i] = arr[i + l]; } // i就是左侧小数组的开始索引 int i = l; // j就是右侧小数组的开始索引 int j = mid + 1; // k表示当前正在合并的原数组的索引下标 for (int k = l; k <= r; k++) { if (i > mid) { // 左侧区间已经被处理完毕,只需要将右侧区间的值拷贝原数组即可 arr[k] = aux[j - l]; j++; } else if (j > r) { // 右侧区间已经被处理完毕,只需要将左侧区间的值拷贝到原数组即可 arr[k] = aux[i - l]; i++; } else if (aux[i - l] <= aux[j - l]) { // 此时左侧区间的元素值较小,相等元素放在左区间,保证稳定性 arr[k] = aux[i - l]; i++; } else { // 右侧区间的元素值较小 arr[k] = aux[j - l]; j++; } } } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
编辑
b. 归并排序迭代写法
//6.2归并排序的迭代写法 public static void mergeSortNonRecursion(int[] arr) { // 最外层循环表示每次合并的子数组的元素个数 for (int sz = 1; sz <= arr.length; sz += sz) { // 内层循环的变量i表示每次合并的开始索引 // i + sz 就是右区间的开始索引,i + sz < arr.length说明还存在右区间 for (int i = 0; i + sz < arr.length; i += sz + sz) { merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, arr.length - 1)); } } } //合并两个子数组arr[l..mid] 和 arr[mid + 1...r] private static void merge(int[] arr, int l, int mid, int r) { // 先创建一个新的临时数组aux int[] aux = new int[r - l + 1]; // 将arr元素值拷贝到aux上 for (int i = 0; i < aux.length; i++) { aux[i] = arr[i + l]; } // i就是左侧小数组的开始索引 int i = l; // j就是右侧小数组的开始索引 int j = mid + 1; // k表示当前正在合并的原数组的索引下标 for (int k = l; k <= r; k++) { if (i > mid) { // 左侧区间已经被处理完毕,只需要将右侧区间的值拷贝原数组即可 arr[k] = aux[j - l]; j++; } else if (j > r) { // 右侧区间已经被处理完毕,只需要将左侧区间的值拷贝到原数组即可 arr[k] = aux[i - l]; i++; } else if (aux[i - l] <= aux[j - l]) { // 此时左侧区间的元素值较小,相等元素放在左区间,保证稳定性 arr[k] = aux[i - l]; i++; } else { // 右侧区间的元素值较小 arr[k] = aux[j - l]; j++; } } }
7.快速排序
a.一路快排(前后遍历)
1. 从待排序区间选择一个数,作为基准值(pivot);
2. Partition: 遍历整个待排序区间,将比基准值小的(可以包含相等的)放到基准值的左边,将比基准值大的(可以包含相等的)放到基准值的右边;
3. 采用分治思想,对左右两个小区间按照同样的方式处理,直到小区间的长度 == 1,代表已经有序,或者小区间的长度 == 0,代表没有数据。
编辑
// 取随机数 private static final ThreadLocalRandom random = ThreadLocalRandom.current(); //7.0快速排序 public static void quickSort(int[] arr) { quickSortInternal(arr, 0, arr.length - 1); } private static void quickSortInternal(int[] arr, int l, int r) { if (r - l <= 0) { return; } // 先获取分区点 // 所谓的分区点就是经过分区函数后,某个元素落在了最终的位置 // 分区点左侧全都是小于该元素的区间,分区点右侧全都是 >= 该元素的区间 int p = partition(arr, l, r); // 重复在左区间和右区间上重复上述流程 quickSortInternal(arr, l, p - 1); quickSortInternal(arr, p + 1, r); } private static int partition(int[] arr, int l, int r) { // 随机在当前数组中选一个数 int randomIndex = random.nextInt(l, r); swap(arr, l, randomIndex); int v = arr[l]; // arr[l + 1..j] < v // arr[j + 1..i) >= v // i表示当前正在扫描的元素 int j = l; for (int i = l + 1; i <= r; i++) { if (arr[i] < v) { swap(arr, j + 1, i); j++; } } // 将基准值和最后一个 < v的元素交换,基准值就落在了最终位置 swap(arr, l, j); return j; } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
编辑
b. 二路快排
编辑
//7.2快速排序 public static void quickSort2(int[] arr) { quickSortInternal2(arr, 0, arr.length - 1); } private static void quickSortInternal2(int[] arr, int l, int r) { if (r - l <= 0) { return; } int p = partition2(arr, l, r); quickSortInternal2(arr, l, p - 1); quickSortInternal2(arr, p + 1, r); } private static int partition2(int[] arr, int l, int r) { int randomIndex = random.nextInt(l, r); swap(arr, l, randomIndex); int v = arr[l]; // arr[l + 1..i) <= v // [l + 1..l + 1) = 0 int i = l + 1; // arr(j..r] >= v // (r...r] = 0 int j = r; while (true) { // i从前向后扫描,碰到第一个 >= v的元素停止 while (i <= j && arr[i] < v) { i++; } // j从后向前扫描,碰到第一个 <= v的元素停止 while (i <= j && arr[j] > v) { j--; } if (i >= j) { break; } swap(arr, i, j); i++; j--; } // j落在最后一个 <= v的元素身上 swap(arr, l, j); return j; } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
c. 三路快排
编辑
//7.3 三路快排 public static void quickSort3(int[] arr) { quickSortInternal3(arr, 0, arr.length - 1); } private static void quickSortInternal3(int[] arr, int l, int r) { if (r - l <= 0) { return; } int randomIndex = random.nextInt(l, r); swap(arr, l, randomIndex); int v = arr[l]; // arr[l + 1..lt] < v // lt是指向最后一个<v的元素 int lt = l; // arr[lt + 1..i) == v // i - 1是最后一个 = v的元素 int i = lt + 1; // arr[gt..r] > v // gt是第一个 > v的元素 int gt = r + 1; // i从前向后扫描和gt重合时,所有元素就处理完毕 while (i < gt) { if (arr[i] < v) { // arr[l + 1..lt] < v // arr[lt + 1..i) == v swap(arr, i, lt + 1); i++; lt++; } else if (arr[i] > v) { // 交换到gt - 1 swap(arr, i, gt - 1); gt--; // 此处i不++,交换来的gt - 1还没有处理 } else { // 此时arr[i] = v i++; } } // lt落在最后一个 < v的索引处 swap(arr, l, lt); // arr[l..lt - 1] < v quickSortInternal3(arr, l, lt - 1); // arr[gt..r] > v quickSortInternal3(arr, gt, r); } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
d. 非递归快排
//借助栈来实现非递归分治快排 public static void quickSortNonRecursion(int[] arr) { Deque<Integer> stack = new ArrayDeque<>(); // 栈中保存当前集合的开始位置和终止位置 int l = 0; int r = arr.length - 1; stack.push(r); stack.push(l); while (!stack.isEmpty()) { // 栈不为空时,说明子区间还没有处理完毕 int left = stack.pop(); int right = stack.pop(); if (left >= right) { // 区间只有一个元素 continue; } int p = partition(arr, left, right); // 依次将右区间的开始和结束位置入栈 stack.push(right); stack.push(p + 1); // 再将左侧区间的开始和结束位置入栈 stack.push(p - 1); stack.push(left); } } private static int partition(int[] arr, int l, int r) { // 随机在当前数组中选一个数 int randomIndex = random.nextInt(l, r); swap(arr, l, randomIndex); int v = arr[l]; // arr[l + 1..j] < v // arr[j + 1..i) >= v // i表示当前正在扫描的元素 int j = l; for (int i = l + 1; i <= r; i++) { if (arr[i] < v) { swap(arr, j + 1, i); j++; } } // 将基准值和最后一个 < v的元素交换,基准值就落在了最终位置 swap(arr, l, j); return j; } //交换三连 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
e. 挖坑法
基本思路和Hoare 法一致,只是不再进行交换,而是进行赋值(填坑+挖坑)
//7.5 挖坑法 public static void quickSortDigPit(int[] arr) { quickSortDigPitInternal(arr, 0, arr.length - 1); } private static int quickSortDigPitInternal(int[] array, int left, int right) { int i = left; int j = right; int pivot = array[left]; while (i < j) { while (i < j && array[j] >= pivot) { j--; } array[i] = array[j]; while (i < j && array[i] <= pivot) { i++; } array[j] = array[i]; } array[i] = pivot; return i; }