什么是排序🍭
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
什么是稳定性🍭
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持 不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳 定的；否则称为不稳定的。
交换排序的基本思想🍭
交换排序是基于比较的排序算法，其主要思想是不断比较相邻两个元素的大小，将较小的元素不断交换到数组的前面，较大的元素不断交换到数组的后面，直到整个数组有序为止。
一、冒泡排序🍭
1、基本思想🍉
冒泡排序的基本思想是通过比较相邻的两个元素的大小，将较小的元素不断交换到数组的前面，较大的元素不断交换到数组的后面。具体地，排序过程如下：
- 比较相邻的两个元素，如果前一个元素比后一个元素大，则交换这两个元素的位置。
- 不断重复第一步，直到将最大的元素交换到数组的最后一个位置
- 重复上述操作，每次将待排序的数组长度减一，直到整个数组有序为止。
2、实现代码🍉
public static void bubbleSort(int[] arr) { int len = arr.length; for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
3、代码优化🍉
Ⅰ、 🧁冒泡排序的优化1
如果一次循环中没有发生交换，则说明数组已经有序，可以结束排序。
优化前：
import java.util.Arrays; public class Main { public static void bubbleSort(int[] arr) { int len = arr.length; for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } System.out.print("第 "+(i+1)+" 趟，第 "+(j+1)+" 次比较后的结果："); System.out.println(Arrays.toString(arr)); } } } public static void main(String[] args) { int[] arr={2,9,7,15,49,10}; System.out.println(Arrays.toString(arr)); bubbleSort(arr); } }
可以看到上方的代码打印，其实有不少循环过程未发生任何变化，且已排序完成，所以此时应该提前退出循环。
优化后：
public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { boolean flag = false; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag = true; } } if (!flag) { break; } } }
可以看到优化之后明显减少了排序的次数。
Ⅱ、🧁冒泡排序的优化2
记录每一次循环中最后一次交换的位置lastIndex，在下一次循环中，只需要比较到lastIndex的位置即可，因为lastIndex之后的元素已经有序。
public static void bubbleSort(int[] arr) { int n = arr.length; int lastIndex = 0; int k = n - 1; for (int i = 0; i < n - 1; i++) { boolean flag = false; for (int j = 0; j < k; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag = true; lastIndex = j; } } if (!flag) { break; } k = lastIndex; } }
4、优缺点🍉
冒泡排序的主要优点是代码简单易懂，实现方便，适用于小规模的数据排序。冒泡排序的主要缺点是时间复杂度较高，为 O(n²)，不适用于大规模数据的排序。
5、算法分析🍉
1、时间复杂度
在最坏情况下，即待排序的序列是逆序的情况下，冒泡排序需要比较和交换的次数最多。在这种情况下，冒泡排序的时间复杂度为O(n²)。在最好情况下，即待排序的序列已经有序的情况下，冒泡排序只需要进行一次遍历，时间复杂度为O(n)。
因此，冒泡排序的平均时间复杂度为O(n²)。虽然冒泡排序的时间复杂度较高，但对于小规模的数据排序，冒泡排序仍然是一种简单有效的排序算法。
2、空间复杂度
冒泡排序是一种原地排序算法，不需要额外的空间进行排序。因此，冒泡排序的空间复杂度为O(1)。
3、稳定性
冒泡排序是一种稳定的排序算法。由于冒泡排序只会交换相邻元素中大小关系不符合要求的元素，因此相同元素的相对位置不会发生变化，保证了冒泡排序的稳定性。
6、 应用场景🍉
- 教学和学习：冒泡排序是一种很好理解的排序算法，可以作为初学者学习排序算法的入门算法，帮助理解算法的基本思想。
- 小规模数组排序：对于小规模的待排序数组，冒泡排序的效率可能比较高，因为它的常数因子较小。
- 数据基本有序的排序：如果待排序数组中的元素已经基本有序，即每个元素与它前后的元素相差不大，那么冒泡排序的效率会比较高，因为它在对已排序的部分不会进行比较和交换。
总的来说，冒泡排序在实际应用中的使用场景较为有限，更多的是用于教学和算法实现方面。
二、快速排序🍭
快速排序是一种不稳定的排序算法，其基本原理是通过选取一个基准元素，将数组划分为两个子数组，分别对子数组进行排序，最终实现整个数组的有序排列。快速排序的时间复杂度为O(nlogn)，是一种高效的排序算法。
1、基本思想🍉
快速排序的基本思想是：选择一个基准元素，将数组划分为两个子数组，比基准元素小的元素放在左边，比基准元素大的元素放在右边，然后分别对左右子数组进行排序，最终实现整个数组的有序排列。具体地，排序过程如下：
- 选择一个基准元素；
- 将数组划分为两个子数组，比基准元素小的元素放在左边，比基准元素大的元素放在右边；
- 分别对左右子数组进行排序，重复上述操作；
- 直到整个数组有序为止。
2、代码实现（递归与非递归 三种方法实现）🍉
Ⅰ、🧁递归 hoare版本(左右指针法)
public static void quickSort(int[] arr, int left, int right) { if (left >= right) return; int i = left, j = right; int pivot = arr[left]; // 选择数组的第一个元素作为基准 while (i < j) { while (i < j && arr[j] >= pivot) j--; // 从右往左找到第一个小于pivot的数 while (i < j && arr[i] <= pivot) i++; // 从左往右找到第一个大于pivot的数 if (i < j) swap(arr, i, j); // 交换这两个数 } swap(arr, left, i); // 把基准放到它正确的位置上，此时i=j quickSort(arr, left, i - 1); // 递归处理左半部分 quickSort(arr, i + 1, right); // 递归处理右半部分 } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
网上一个经典的hoare版快排GIF（一趟快排）
Ⅱ、🧁 挖坑法
public static void quickSort(int[] arr, int left, int right) { if (left >= right) return; int i = left, j = right; int pivot = arr[left]; // 挖一个坑，选择数组的第一个元素作为基准 while (i < j) { while (i < j && arr[j] >= pivot) j--; // 从右往左找到第一个小于pivot的数 if (i < j) arr[i++] = arr[j]; // 把该数填到之前挖出来的坑中 while (i < j && arr[i] <= pivot) i++; // 从左往右找到第一个大于pivot的数 if (i < j) arr[j--] = arr[i]; // 把该数填到刚才挖出的坑中 } arr[i] = pivot; // 将最初挖出来的坑填回去，此时i=j quickSort(arr, left, i - 1); // 递归处理左半部分 quickSort(arr, i + 1, right); // 递归处理右半部分 }
Ⅲ、🧁前后指针法
第一种写法：
public static void quickSort(int[] arr, int start, int end) { if (start >= end) return; int pivot = arr[start]; // 选择数组的第一个元素作为基准 int i = start, j = end; while (i < j) { while (i < j && arr[j] >= pivot) j--; // 从右往左找到第一个小于pivot的数 while (i < j && arr[i] <= pivot) i++; // 从左往右找到第一个大于pivot的数 if (i < j) swap(arr, i, j); // 交换这两个数 } swap(arr, start, i); // 把基准放到它正确的位置上，此时i=j quickSort(arr, start, i - 1); // 排序左半部分 quickSort(arr, i + 1, end); // 排序右半部分 } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
第二种写法：
public static void quickSort(int[] arr, int start, int end) { if (start >= end) return; int pivot = arr[start]; // 选择数组的第一个元素作为基准 int i = start + 1, j = start + 1; // i和j都从start+1开始 while (j <= end) { if (arr[j] < pivot) { swap(arr, i, j); i++; } j++; } swap(arr, start, i - 1); // 把枢轴放到它正确的位置上 quickSort(arr, start, i - 2); // 排序左半部分 quickSort(arr, i, end); // 排序右半部分 } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
第一种写法中，i和j都从start开始，用两个while循环找到需要交换的数，并且是在i和j相遇时才交换。
第二种写法中，i和j都从start+1开始，只有当arr[j]<pivot时才交换，交换后把i向前移动一位，最终i停留的位置就是基准的正确位置。
Ⅳ、🧁 非递归
public static void quickSort(int[] arr) { Stack<Integer> stack = new Stack<>(); int left = 0, right = arr.length - 1; stack.push(left); stack.push(right); while (!stack.isEmpty()) { right = stack.pop(); left = stack.pop(); int pivot = partition(arr, left, right); // 将左子数组入栈 if (left < pivot - 1) { stack.push(left); stack.push(pivot - 1); } // 将右子数组入栈 if (right > pivot + 1) { stack.push(pivot + 1); stack.push(right); } } } public static int partition(int[] arr, int left, int right) { int pivot = arr[left]; int i = left, j = right; while (i < j) { while (i < j && arr[j] >= pivot) j--; if (i < j) arr[i++] = arr[j]; while (i < j && arr[i] <= pivot) i++; if (i < j) arr[j--] = arr[i]; } arr[i] = pivot; return i; }
使用一个Stack数据结构来模拟递归过程，实现非递归的快速排序。我们首先将数组的左边界和右边界入栈，然后从栈中取出左边界和右边界，进行划分数组的操作。划分完成后，将左子数组和右子数组的边界入栈，继续进行处理，直到栈为空。
非递归的快速排序算法的时间复杂度为O(nlogn)，空间复杂度为O(logn)，效率与递归版本的快速排序相当。
3、代码优化（三种优化）🍉
Ⅰ、
- 优化1：如果待排序数组的长度小于某个常数，可以使用插入排序来替代快速排序。因为对于小规模的数据，插入排序的效率要高于快速排序。这个常数的取值可以根据实际情况进行调整。
- 优化2：随机选择基准点，避免数组已经有序或近似有序的情况下时间复杂度退化。在实际应用中，数组的分布情况是不可预知的，如果固定选择第一个或最后一个元素作为基准点，那么在一些特殊情况下，快速排序的效率会变得非常低。因此，我们可以随机选择一个元素作为基准点，避免这种情况的发生。
public static void quickSort(int[] arr, int left, int right) { // 递归终止条件 if (left >= right) return; // 优化1：如果待排序数组的长度小于某个常数，可以使用插入排序 if (right - left + 1 <= 10) { insertionSort(arr, left, right); return; } int pivot = partition(arr, left, right); // 划分数组 quickSort(arr, left, pivot - 1); // 递归处理左子数组 quickSort(arr, pivot + 1, right); // 递归处理右子数组 } public static int partition(int[] arr, int left, int right) { // 优化2：随机选择基准点，避免数组已经有序或近似有序的情况下时间复杂度退化 int pivot = arr[left + new Random().nextInt(right - left + 1)]; int i = left, j = right; while (i < j) { while (i < j && arr[j] >= pivot) j--; if (i < j) arr[i++] = arr[j]; while (i < j && arr[i] <= pivot) i++; if (i < j) arr[j--] = arr[i]; } arr[i] = pivot; return i; } public static void insertionSort(int[] arr, int left, int right) { for (int i = left + 1; i <= right; i++) { int temp = arr[i]; int j = i - 1; while (j >= left && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } }
🧁 优化后的快速排序算法的时间复杂度为O(nlogn)，空间复杂度为O(logn)，效率比未优化的快速排序算法更高。
Ⅱ、优化三
使用三数取中法来选择基准元素。然后使用两个指针 i 和 j 分别从左和右开始扫描数组，寻找需要交换的元素，最后将数组分成了两部分进行递归排序。
public static void quicksort(int[] arr) { sort(arr, 0, arr.length-1); } private static void sort(int[] arr, int left, int right) { if (left >= right) return; // 选取枢轴元素 int mid = left + (right - left) / 2; if (arr[right] < arr[left]) swap(arr, left, right); if (arr[mid] < arr[left]) swap(arr, mid, left); if (arr[right] < arr[mid]) swap(arr, right, mid); int pivot = arr[mid]; int i = left, j = right; while (true) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i >= j) break; swap(arr, i, j); i++; j--; } sort(arr, left, i-1); sort(arr, i, right); } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
4、优缺点🍉
快速排序的主要优点是时间复杂度较低，为 O(nlogn)，适用于大规模数据的排序。快速排序的主要缺点是不稳定，可能会改变相同元素的相对位置。
5、算法分析🍉
1、时间复杂度
快速排序的时间复杂度为O(nlogn)，其中n为待排序数组的长度。最坏情况下，快速排序的时间复杂度为O(n^2)，但这种情况出现的概率很小，可以通过一些优化措施来避免。
2、空间复杂度
快速排序的空间复杂度取决于递归栈的深度，在最坏情况下，递归栈的深度为O(n)，因此快速排序的空间复杂度为O(n)。但是，在一些实现中，可以使用非递归的方式来实现快速排序，从而避免递归栈
3、稳定性
快速排序是一种不稳定的排序算法。因为在排序过程中，可能会交换相同元素的位置，从而导致相同元素的相对顺序被改变。例如，对于数组[3, 2, 2, 1]，如果选择第一个元素3作为基准元素，那么经过第一次划分后，数组变成了[1, 2, 2, 3]，其中两个2的相对顺序被改变了。
6、应用场景🍉
- 大规模数据排序：快速排序的时间复杂度为 O(nlogn)，在大规模数据排序时表现优秀。
- 数据重复性较少的排序：在排序的数据中，如果存在大量重复的元素，那么快速排序的效率会受到影响，因为这样会增加比较和交换的次数。
- 对数据随机性要求不高的排序：由于快速排序的分区过程是基于一个基准元素来完成的，因此如果待排序数据的分布比较随机，那么快速排序的效率会很高。
🧁总的来说，快速排序是一种高效的排序算法，在数据量较大、数据分布比较随机、重复性较少的场景中表现优秀，是一种很好的排序算法选择。
选择排序的基本思想🍭
将排序序列分为有序区和无序区，每一趟排序从无序区中选出最小的元素放在有序区的最后，从而扩大有序区，直到全部元素有序为止。
