经典排序算法总结

mac2025-11-26 12

Merge Sort和 Quick Sort的衍生问题：https://blog.csdn.net/qq_40794973/article/details/102879153 P1177 【模板】快速排序：https://blog.csdn.net/qq_40794973/article/details/102879417 912. 排序数组：https://leetcode-cn.com/problems/sort-an-array/

public class Student implements Comparable<Student> { // 分数 private Integer score; // 姓名 private String name; //可以通过自定义比较函数，让排序算法不存在稳定性的问题 @Override public int compareTo(Student otherStudent) { if (!score.equals(otherStudent.score)) {// 分数不等 if (score.compareTo(otherStudent.score) > 0) { return 1; } else if (score.compareTo(otherStudent.score) < 0) { return -1; } else { // score == otherStudent.score return 0; } } else {// 分数相等 if (name.compareTo(otherStudent.name) > 0) { return 1; } else if (name.compareTo(otherStudent.name) < 0) { return -1; } else { // name == otherStudent.name return 0; } } } }

冒泡排序（Bubble Sort）

https://www.jianshu.com/p/88759596c944

public static void bubbleSort(Comparable[] arr) { int n = arr.length; boolean swapped; do { swapped = false; for (int i = 1; i < n; i++) { // arr[i - 1] > arr[i] if (arr[i - 1].compareTo(arr[i]) > 0) { swap(arr, i - 1, i); swapped = true; } } // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置 // 所以下一次排序, 最后的元素可以不再考虑 n--; } while (swapped); } private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t; }

优化

public static void bubbleSort(Comparable[] arr) { int n = arr.length; int newn; // 使用newn进行优化（理论上，可以使用newn进行优化，但实际优化效果较差） do { newn = 0; for (int i = 1; i < n; i++) { if (arr[i - 1].compareTo(arr[i]) > 0) { swap(arr, i - 1, i); // 记录最后一次的交换位置，在此之后的元素在下一轮扫描中均不考虑 newn = i; } } n = newn; } while (newn > 0); } private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t; }

选择排序（Selection Sort）

缺点：两层循环每一层循环都需要完全的执行，所有在任何情况下都慢

//SelectionSort public static void selectionSort(Comparable[] arr) { int n = arr.length; for (int i = 0; i < n; i++) { // 寻找[i, n)区间里的最小值的索引 int minIndex = i; for (int j = i + 1; j < n; j++) { // 使用compareTo方法比较两个Comparable对象的大小 //arr[j] < arr[minIndex] if (arr[j].compareTo(arr[minIndex]) < 0) { minIndex = j; } } swap(arr, i, minIndex); } } private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t; }

优化：在每一轮中, 可以同时找到当前未处理元素的最大值和最小值

// 优化 // 在每一轮中, 可以同时找到当前未处理元素的最大值和最小值 public static void selectionSort(Comparable[] arr) { int left = 0, right = arr.length - 1; while (left < right) { int minIndex = left; int maxIndex = right; // 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex] if (arr[minIndex].compareTo(arr[maxIndex]) > 0) { swap(arr, minIndex, maxIndex); } for (int i = left + 1; i < right; i++) { if (arr[i].compareTo(arr[minIndex]) < 0) { minIndex = i; } else if (arr[i].compareTo(arr[maxIndex]) > 0) { maxIndex = i; } } swap(arr, left, minIndex); swap(arr, right, maxIndex); left++; right--; } } private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t; }

插入排序（Insertion Sort）

插入排序的第二层循环可以提前结束，当数据近乎有序的时候效率非常高

// 对整个arr数组使用InsertionSort排序 public static void insertionSort(Comparable[] arr) { int n = arr.length; for (int i = 0; i < n; i++) { // 寻找元素arr[i]合适的插入位置 Comparable e = arr[i]; int j = i;// j保存元素e应该插入的位置 for (; j > 0 && arr[j - 1].compareTo(e) > 0; j--) { arr[j] = arr[j - 1]; } arr[j] = e; } } // 对arr[l...r]的区间使用InsertionSort排序 public static void insertionSort(Comparable[] arr, int l, int r) { for (int i = l + 1; i <= r; i++) { Comparable e = arr[i]; int j = i; for (; j > l && arr[j - 1].compareTo(e) > 0; j--) { arr[j] = arr[j - 1]; } arr[j] = e; } }

希尔排序（Shell Sort）

public static void shellSort(Comparable[] arr) { int n = arr.length; // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093... int h = 1; while (h < n / 3) { h = 3 * h + 1; } while (h >= 1) { // h-sort the array for (int i = h; i < n; i++) { // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序 Comparable e = arr[i]; int j = i; for (; j >= h && e.compareTo(arr[j - h]) < 0; j -= h) { arr[j] = arr[j - h]; } arr[j] = e; } h /= 3; } }

归并排序（Merge Sort）

详细说明：https://blog.csdn.net/qq_40794973/article/details/102879166

System.arraycopy：https://blog.csdn.net/qq_40794973/article/details/102604490

递归实现

private static Comparable[] aux; // 将arr[l...mid]和arr[mid+1...r]两部分进行归并 private static void merge(Comparable[] arr, int l, int mid, int r) { System.arraycopy(arr, l, aux, l, r - l + 1);//arr[l...r]覆盖aux[l...r] // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1 int i = l, j = mid + 1; for (int k = l; k <= r; k++) { if (i > mid) { // 如果左半部分元素已经全部处理完毕 arr[k] = aux[j]; j++; } else if (j > r) { // 如果右半部分元素已经全部处理完毕 arr[k] = aux[i]; i++; } else if (aux[i].compareTo(aux[j]) < 0) { // 左半部分所指元素 < 右半部分所指元素 arr[k] = aux[i]; i++; } else { // 左半部分所指元素 >= 右半部分所指元素 arr[k] = aux[j]; j++; } } } // 递归使用归并排序,对arr[l...r]的范围进行排序 private static void mergeSort(Comparable[] arr, int l, int r) { // 优化2: 对于小规模数组, 使用插入排序 if (r - l <= 15) { InsertionSort.insertionSort(arr, l, r); return; } int mid = l + (r - l) / 2; mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); // 优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失（if判断也是需要时间的） if (arr[mid].compareTo(arr[mid + 1]) > 0) { merge(arr, l, mid, r); } } public static void mergeSort(Comparable[] arr) { int n = arr.length; aux = new Comparable[n]; mergeSort(arr, 0, n - 1); }

自底向上的归并排序

private static Comparable[] aux; // 将arr[l...mid]和arr[mid+1...r]两部分进行归并 private static void merge(Comparable[] arr, int l, int mid, int r) { System.arraycopy(arr, l, aux, l, r - l + 1);//arr[l...r]覆盖aux[l...r] // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1 int i = l, j = mid + 1; for (int k = l; k <= r; k++) { if (i > mid) { // 如果左半部分元素已经全部处理完毕 arr[k] = aux[j]; j++; } else if (j > r) { // 如果右半部分元素已经全部处理完毕 arr[k] = aux[i]; i++; } else if (aux[i].compareTo(aux[j]) < 0) { // 左半部分所指元素 < 右半部分所指元素 arr[k] = aux[i]; i++; } else { // 左半部分所指元素 >= 右半部分所指元素 arr[k] = aux[j]; j++; } } } public static void mergeSort(Comparable[] arr) { int n = arr.length; aux = new Comparable[n]; // Merge Sort Bottom Up 优化 // 对于小数组, 使用插入排序优化 for (int i = 0; i < n; i += 16) { InsertionSort.insertionSort(arr, i, Math.min(i + 15, n - 1)); } for (int sz = 16; sz < n; sz += sz) { for (int i = 0; i < n - sz; i += sz + sz) { // 对于arr[mid] <= arr[mid+1]的情况,不进行merge if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0) { merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1)); } } } } public class InsertionSort { // 对arr[l...r]的区间使用InsertionSort排序 public static void insertionSort(Comparable[] arr, int l, int r) { for (int i = l + 1; i <= r; i++) { Comparable e = arr[i]; int j = i; for (; j > l && arr[j - 1].compareTo(e) > 0; j--) { arr[j] = arr[j - 1]; } arr[j] = e; } } } Merge Sort是一个O(nlogn)复杂度的算法可以在1秒之内轻松处理100万数量级的数据注意：不要轻易尝试使用SelectionSort, InsertionSort或者BubbleSort处理100万级的数据否则，你就见识了O(n^2)的算法和O(nlogn)算法的本质差异 //Integer[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; //mergeSort(arr); //System.out.println(Arrays.toString(arr));

快速排序（Quick Sort）

详细说明：https://blog.csdn.net/qq_40794973/article/details/102879158

三路快排

// 递归使用快速排序,对arr[l...r]的范围进行排序 private static void quickSort(Comparable[] arr, int l, int r) { // 对于小规模数组, 使用插入排序 if (r - l <= 15) { InsertionSort.insertionSort(arr, l, r); return; } // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot swap(arr, l, (int) (Math.random() * (r - l + 1)) + l); Comparable v = arr[l]; int lt = l; // arr[l+1...lt] < v int gt = r + 1; // arr[gt...r] > v int i = l + 1; // arr[lt+1...i) == v while (i < gt) { if (arr[i].compareTo(v) < 0) { swap(arr, i, lt + 1); i++; lt++; } else if (arr[i].compareTo(v) > 0) { swap(arr, i, gt - 1); gt--; } else { // arr[i] == v i++; } } swap(arr, l, lt); quickSort(arr, l, lt - 1); quickSort(arr, gt, r); } public static void quickSort(Comparable[] arr) { int n = arr.length; quickSort(arr, 0, n - 1); } private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public class InsertionSort { // 对arr[l...r]的区间使用InsertionSort排序 public static void insertionSort(Comparable[] arr, int l, int r) { for (int i = l + 1; i <= r; i++) { Comparable e = arr[i]; int j = i; for (; j > l && arr[j - 1].compareTo(e) > 0; j--) { arr[j] = arr[j - 1]; } arr[j] = e; } } }

堆排序（Heap Sort）

堆排序：https://blog.csdn.net/qq_40794973/article/details/102880394

// 不使用一个额外的最大堆, 直接在原数组上进行原地的堆排序 public static void heapSort(Comparable[] arr) { int n = arr.length; // 注意，此时我们的堆是从0开始索引的 // 从(最后一个元素的索引-1)/2开始 // 最后一个元素的索引 = n-1 //Heapify for (int i = (n - 1 - 1) / 2; i >= 0; i--) { shiftDown(arr, n, i); } for (int i = n - 1; i > 0; i--) { swap(arr, 0, i); shiftDown(arr, i, 0); } } // 交换堆中索引为i和j的两个元素 private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t; } private static void shiftDown(Comparable[] arr, int n, int k) { Comparable e = arr[k]; while (2 * k + 1 < n) { int j = 2 * k + 1; if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) { j += 1; } if (e.compareTo(arr[j]) >= 0) { break; } arr[k] = arr[j]; k = j; } arr[k] = e; }

nlogn比n^2快多少

测试算法的正确性

/** * 判断arr数组是否有序 */ public static boolean isSorted(Comparable[] arr) { for (int i = 0; i < arr.length - 1; i++) { if (arr[i].compareTo(arr[i + 1]) > 0) { return false; } } return true; } public static void main(String[] args) { //数据大小 int arrLen = 1000; Integer[] arr = new Integer[arrLen]; Random random = new Random(); for (int i = 0; i < arr.length; i++) { arr[i] = random.nextInt(Integer.MAX_VALUE); } //计算开始 long startTime = System.currentTimeMillis(); sort(arr); //计算结束 long endTime = System.currentTimeMillis(); System.out.println("排序时间：" + (endTime - startTime) + "ms"); if (isSorted(arr)) { System.out.println("排序算法正确"); } else { System.out.println("排序算法不正确!!!"); } System.out.println(); System.out.println(Arrays.toString(arr)); }

算法思想

分治算法：归并排序，快速排序...贪心算法：最小生成树...动态规化：最短路径...

递归搜索：树形结构...

参考：https://www.cnblogs.com/guoyaohua/p/8600214.html

最新回复(0)