排序算法：冒泡排序，插入排序，选择排序，归并排序，快速排序

涉及排序算法列表

排序算法：冒泡排序，插入排序，选择排序，归并排序，快速排序

算法分析评价涉及层面

冒泡排序，插入排序，选择排序代码

* 1.最好情况、最坏情况、平均情况时间复杂度 * 2.原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。 * 3.稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。 * * @author gaoge * @since 2022/11/29 17:07 */ public class Sort { /** * 冒泡排序 *

* 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。 * 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。 * 冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。 * 最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。 * 而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。 * 平均情况下的时间复杂度就是 O(n2) * * @param a 数组 * @param n 数组大小 */ public static void bubbleSort(int[] a, int n) { 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 temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; flag = true; } } if (!flag) { break; } } } /** * 插入排序 *

* 首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。 * 初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素， * 在已排序区间中找到合适的插入位置将其插入， * 并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。 * 插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。 * 在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面， * 这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。 * 最好是时间复杂度为 O(n)，最坏情况时间复杂度为 O(n2)，平均时间复杂度为 O(n2)。 * * @param a 数组 * @param n 数组大小 */ public static void insertionSort(int[] a, int n) { if (n = 0; --j) { if (a[j] > value) { // 数据移动 a[j + 1] = a[j]; } else { break; } } // 插入数据 a[j + 1] = value; } } /** * 选择排序 *

* 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 * 但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。 * 选择排序是一种不稳定的排序算法。比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话， * 第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。 * 正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。 * 首先，选择排序空间复杂度为 O(1)，是一种原地排序算法。 * 选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。 * * @param a 数组 * @param n 数组大小 */ public static void selectionSort(int[] a, int n) { for (int i = 0; i < n; i++) { int value = a[i]; int min = value; int num = i; for (int j = i; j < n; j++) { if (a[j] < min) { min = a[j]; num = j; } } a[i] = min; a[num] = value; } } /** * 生成20个随机数组 * * @return 随机数组 * @author gaoge * @since 2022/11/29 17:07 */ public static int[] randomArray() throws NoSuchAlgorithmException { int[] arr = new int[10]; Random rand = SecureRandom.getInstanceStrong(); for (int i = 0; i < arr.length; i++) { //生成随机数100以内； arr[i] = rand.nextInt(100); } return arr; } /** * 测试排序算法 * * @param args * @throws NoSuchAlgorithmException */ public static void main(String[] args) throws NoSuchAlgorithmException { int[] ints; String start = "原始数组："; String end = "排序数组："; //冒泡排序 System.out.println("冒泡排序"); ints = randomArray(); System.out.println(start + Arrays.toString(ints)); bubbleSort(ints, ints.length); System.out.println(end + Arrays.toString(ints)); //插入排序 System.out.println("插入排序"); ints = randomArray(); System.out.println(start + Arrays.toString(ints)); insertionSort(ints, ints.length); System.out.println(end + Arrays.toString(ints)); //选择排序 System.out.println("选择排序"); ints = randomArray(); System.out.println(start + Arrays.toString(ints)); selectionSort(ints, ints.length); System.out.println(end + Arrays.toString(ints)); } } 时间复杂度O(nlogn)算法：归并排序、快速排序

归并排序代码

* 归并排序的核心思想:如果要排序一个数组，我们先把数组从中间分成前后两部分， * 然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了 * 我们申请一个临时数组 tmp，大小与 A[p...r]相同。我们用两个游标 i 和 j， * 分别指向 A[p...q]和 A[q+1...r]的第一个元素。 * 比较这两个元素 A[i]和 A[j]，如果 A[i]= r) { return; } // 取p到r之间的中间位置q,防止（p+r）的和超过int类型最大值 int q = p + (r - p) / 2; // 分治递归,光看第一层 mergeSortInternally(a, p, q); mergeSortInternally(a, q + 1, r); // 将A[p...q]和A[q+1...r]合并为A[p...r] merge(a, p, q, r); } private static void merge(int[] a, int p, int q, int r) { int i = p; int j = q + 1; int k = 0; // 申请一个大小跟a[p...r]一样的临时数组 int[] tmp = new int[r - p + 1]; while (i