目录
什么是排序🍭
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
什么是稳定性🍭
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持 不变，即在原序列中，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)，在大规模数据排序时表现优秀。
-
数据重复性较少的排序：在排序的数据中，如果存在大量重复的元素，那么快速排序的效率会受到影响，因为这样会增加比较和交换的次数。
-
对数据随机性要求不高的排序：由于快速排序的分区过程是基于一个基准元素来完成的，因此如果待排序数据的分布比较随机，那么快速排序的效率会很高。
🧁总的来说，快速排序是一种高效的排序算法，在数据量较大、数据分布比较随机、重复性较少的场景中表现优秀，是一种很好的排序算法选择。
选择排序的基本思想🍭
将排序序列分为有序区和无序区，每一趟排序从无序区中选出最小的元素放在有序区的最后，从而扩大有序区，直到全部元素有序为止。
一、直接选择排序🍭
1、基本思想🍉
第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，….，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…..，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
可以通过看下面GIF来简单了解直接选择排序的过程：
2、代码实现🍉
import java.util.Arrays;
public class Main {
public static void selectSort(int[] arr){
//防止arr数组为空或者arr只有一个数，不用进行排序
if (arr == null || arr.length < 2) {
return;
}
/*每次要进行比较的两个数，的前面那个数的下标*/
for (int i = 0; i < arr.length - 1; i++) {
//min变量保存该趟比较过程中，最小元素所对应的索引，
//先假设前面的元素为最小元素
int min = i;
/*每趟比较，将前面的元素与其后的元素逐个比较*/
for (int j = i + 1; j < arr.length; j++) {
//如果后面的元素小，将后面元素的索引极为最小值的索引
if(arr[j] < arr[min]) {
min = j;
}
}
//然后交换此次查找到的最小值和原始的最小值
swap(arr, i, min);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr={9, 8, 6, 29, 10, 7, 37, 48};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
}
3、代码优化🍉
选择排序的优化引入的二分的思想，前面是找到最小的值往前面放，现在在一趟循环中同时找到最大最小值，将最小值放入头，最大值放入尾。
import java.util.Arrays;
public class Main {
public static void SelectSort(int[] arr){
// find the max and min num in an iteration
int n = arr.length;
for(int i = 0;i<n;i++){
int min = i;
int max = n-1;
for(int j = i;j<n;j++){
if (arr[j]<arr[min]){
min = j;
}
if (arr[j]>arr[max]){
max = j;
}
}
swap(arr,i,min);
// 防止i的位置为最大值，然后被最小值换了，所以检查一下
if (max == i){
max = min;
}
swap(arr,n-1,max);
n = n-1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr={9, 8, 6, 29, 10, 7, 37, 48};
SelectSort(arr);
System.out.println(Arrays.toString(arr));
}
}
4、优缺点🍉
优点：
1. 实现简单，易于理解和编写。
2. 内存占用小，不需要额外的存储空间。
3. 适用于小规模的数据排序。
缺点：
1. 时间复杂度较高，平均时间复杂度为O(n^2)，在数据规模较大时效率低下。
2. 排序过程中不稳定，可能导致相同元素的相对位置发生变化。
3. 交换次数较多，对于大量的数据交换次数会增加，导致效率下降。
4. 不适用于链式结构，因为链式结构不支持随机访问。
5、算法分析🍉
1、时间复杂度
在插入排序中，当待排序序列是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较n- 1次，时间复杂度为O(n)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(n^2)。平均来说，array[1…j-1]中的一半元素小于array[j]，一半元素大于array[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，是O(n^2)。
2、空间复杂度
不需要额外的空间进行排序。因此空间复杂度为O(1)。
3、稳定性：
不稳定，因为排序序列为（5，5，1）,第一趟排序之后（1，5，5），这可以很清楚的看到两个5的相对位置发生了变化。
6、适应场景🍉
1. 数据规模较小，不超过几千个元素。
2. 数据分布比较均匀，不存在大量相同的元素。
3. 内存空间有限，不能使用其他高级排序算法。
4. 数据元素之间的比较操作比较简单，可以快速进行比较。
5. 对于稳定性要求不高的场合，不需要保持相同元素的相对位置不变。
二、堆排序 🍭
1、堆🍉
堆一般指的是二叉堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。堆总是满足下列性质：
堆中某个结点的值总是不大于或不小于其父结点的值；（即k ᵢ <=k₂ᵢ 且kᵢ<=k₂ᵢ₊₁为小根堆，kᵢ>k₂ᵢ且kᵢ>=k₂ᵢ₊₁为大根堆）
堆总是一棵完全二叉树。
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
可以看下面小根堆建立的GIF简单了解堆排序的的过程
2、基本思想🍉
堆排序是简单选择排序的改进，利用二叉树代替简单选择方法来找最大或者最小值，属于一种树形选择排序方法。
利用大根堆(小根堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大值(最小值)变得简单。
- 将待排序的序列构造成一个大根堆，此时序列的最大值为根节点
- 依次将根节点与待排序序列的最后一个元素交换
- 再维护从根节点到该元素的前一个节点为大根堆，如此往复，最终得到一个递增序列
3、堆的存储方式🍉
从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节
点，就会导致空间利用率比较低。
将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：
- 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i – 1)/2
- 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
- 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
4、堆的shift up和shift down🍉
Ⅰ、shift up：向一个最大堆中添加元素🍓
如下面向堆中加入一个新元素52，这时需要重新调整为大根堆，52比它的父节点28大，需要交换，然后和28的父节点（41）比较，还是更大也需要交换。
Ⅱ、shift down：从一个最大堆中取出一个元素只能取出最大优先级的元素，也就是根节点🍓
如果上面那个堆的62变成了12，这时候为了维持大根堆，只能将12这个节点进行shift down操作以维持大根堆
5、堆的插入与删除🍉
Ⅰ、插入🍓
堆的插入总共需要两个步骤：
- 先将元素放入到底层空间中(注意：空间不够时需要扩容)
- 将最后新插入的节点向上调整，直到满足堆的性质
其实这就是shift up操作
Ⅱ、删除🍓
注意：堆的删除一定删除的是堆顶元素（因为二叉堆不支持查找元素位置，因此删除一个你完全不知道内容的元素毫无意义）。具体如下：
1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整（小根堆为例）
调整之后
6、建堆的时间复杂度🍉
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
第1层，2^0个节点，需要向下移动h-1层
第2层，2^1个节点，需要向下移动h-2层
第3层，2^2个节点，需要向下移动h-3层
第4层，2^3个节点，需要向下移动h-4层……………………
第h-1层，h-2个节点，需要向下移动1层
7、代码（建大根堆小根堆，入队出队）🍉
import java.util.Arrays;
public class Main {
public static int[] elem;
public static int usedSize;//当前堆当中的有效的元素的数据个数
/**
* 建堆:【大根堆】
* 时间复杂度：O(n)
*/
public static void createHeap() {
for (int parent = (usedSize-1-1) / 2; parent >= 0 ; parent--) {
shiftDown(parent,usedSize);
}
}
/**
* 实现 向下调整
* @param parent 每棵子树的根节点的下标
* @param len 每棵子树的结束位置
*/
private static void shiftDown(int parent, int len) {
int child = 2 * parent + 1;
//最起码是有左孩子
while (child < len) {
//判断 左孩子 和 右孩子 谁最大,前提是 必须有 右孩子
if(child+1 < len && elem[child] < elem[child+1]) {
child++;//此时 保存了最大值的下标
}
if(elem[child] > elem[parent]) {
swap(elem,child,parent);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
/**
* 入队
* @param x
*/
public void offer(int x) {
if(isFull()) {
elem = Arrays.copyOf(elem,elem.length*2);
}
this.elem[usedSize] = x;
usedSize++;
shiftUp(usedSize-1);
}
/**
* 实现 向上调整
* @param child 需要向上调整的子树的下标
*/
private void shiftUp(int child) {
int parent = (child-1) / 2;
while (child > 0) {
if(elem[child] > elem[parent]) {
swap(elem,child,parent);
child = parent;
parent = (child-1) / 2;
}else {
break;
}
}
}
public boolean isFull() {
return usedSize == elem.length;
}
/**
* 出队
*/
public int poll() {
if(isEmpty()) {
return -1;
}
int old = elem[0];
swap(elem,0,usedSize-1);
usedSize--;
shiftDown(0,usedSize);
return old;
}
/*
判断是否为空
*/
public boolean isEmpty() {
return usedSize == 0;
}
/**
*建立小根堆
*/
public static void heapSort() {
int end = usedSize - 1;
while (end > 0) {
swap(elem,0,end);
shiftDown(0,end);
end--;
}
}
public static void main(String[] args) {
elem = new int[]{5,4,10,16,1,8,9,48,18,17};
usedSize = elem.length;
createHeap();//建立小根堆，先建立大根堆，然后将最大值放入堆尾，建立小根堆
heapSort();
System.out.println(Arrays.toString(elem));
//[1, 4, 5, 8, 9, 10, 16, 17, 18, 48]
createHeap();//建立大根堆
System.out.println(Arrays.toString(elem));
//[48, 18, 16, 17, 9, 10, 5, 1, 8, 4]
}
}8、总结🍉
- 堆排序使用堆来选数，相比直接选择排序效率就高了很多。堆排序中每一趟都有元素归位了
- 时间复杂度：最好/最环/平均时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 适用场景：元素较多的情况，因为建初始堆的所需的比较次数比较多，反之堆排序不适合元素较少的时候
插入排序
一、直接插入排序
1、 基本思想🍉
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
步骤：每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。可以看下面动画展示：
2、代码实现🍉
public class Main {
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48
insertionSort(arr);
}
}
3、代码优化🍉
Ⅰ、🧁插入排序优化（二分）
将待排序的元素与有序部分的元素比较时，不再挨个比较，而是用二分折中的方式进行比较，去寻找到arr[i]的位置，加快了比较效率
public class Main {
public static void insertionSort(int[] arr) {
int j,left,mid,right,temp;
for(int i = 1;i<arr.length;i++){
left = 0;
right = i-1;
temp = arr[i];
/*找到合适的插入位置right+1，如果中间位置元素
*比要插入元素大，则查找区域向低半区移动，否则向高半区移动
*/
while(left <= right){
mid = (left+right)/2;
if(arr[mid]>temp){
right = mid-1;
}else{
left = mid+1;
}
}
/*right+1后的元素后移*/
for(j = i-1;j >= right+1;j--)
{
arr[j+1] = arr[j];
}
/*将元素插入到指定位置*/
arr[j+1] = temp;
}
}
public static void main(String[] args) {
int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48
insertionSort(arr);
}
}
Ⅱ、🧁插入排序优化
在直接插入排序中，每次插入都需要将待插入元素与已排序序列中的元素逐一比较，如果待插入元素比已排序序列中的元素小，就需要将已排序序列中的元素后移。这个过程可以使用赋值的方式来代替元素的移动，从而提高排序的效率。
public static void insertSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}4、优缺点🍉
在数据已经有序或基本有序的情况下，排序效率较高，甚至可以达到O(n)的时间复杂度。 但是在数据规模较大的情况下，排序效率较低，时间复杂度为O(n^2)；而且 对于逆序的数据，每次插入都需要将已排序序列中的所有元素后移一位，因此排序效率非常低；
5、总结🍉
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：最环情况：O(N²)。最好情况：O（N）
3. 空间复杂度：O(1)
4. 稳定性：稳定
5. 适用场景：待排序序列的元素个数不多时，且元素基本偏向有序。
二、希尔排序🍭
1、基本思路🍉
希尔排序法又称缩小增量法，该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序法的基本思想是：首先取一个整数n（小于序列元素总数）作为间隔，把待排序数字中所有数分成几个组，所有间隔相同的数分在同一组内，并对每一组内的数进行排序。缩小间隔n，重复上述分组和排序的工作。当达到n=1 时，所有记录统一在一组内排好序。
其实从上面的希尔排序的思想中也能看出希尔排序的实现步骤：
- 选n，划分逻辑分组，组内进行直接插入排序。
- 不断缩小n，继续组内进行插入排序。
- 直到n=1，在包含所有元素的序列内进行直接插入排序。
其中缩小间隔gap 的取法有多种。最初 Shell 提出取 gap =n/2，gop =gap/2，直到 gap =1。后来 Knuth 提出取 gap =gap/3 +1。还有人提出都为好有人提 gap 互质为好。无论哪一种主张都没有得到证明。
2、代码实现🍉
public class Main {
public static void shellSort(int[] arr){
/*初始化划分增量*/
int n = arr.length;
int temp;
/*每次减小增量，直到n = 1*/
while (n > 1){
/*增量的取法之一：除2向下取整*/
n = n/2;
/*对每个按gap划分后的逻辑分组，进行直接插入排序*/
for (int i = n; i < arr.length; ++i) {
if (arr[i-n] > arr[i]) {
temp = arr[i];
int j = i-n;
while (j >= 0 && arr[j] > temp) {
arr[j+n] = arr[j];
j -= n;
}
arr[j+n] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48
shellSort(arr);
}
}
3、代码优化🍉
Ⅰ、🧁希尔排序优化（二分）
由于希尔排序是基于插入排序的，所以在插入排序中也可运用直接插入排序中的优化方式，所有也可以以二分折中的方式来优化希尔排序。
public class Main {
public static void shellSort(int[] arr) {
int j, left, mid, right, temp;
int n = arr.length;
while (n > 1) {
n /= 2;
for (int i = n; i < arr.length; i++) {
left = 0;
right = i - 1;
temp = arr[i];
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] > temp) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (j = i - n; j >= right + 1; j-=n) {
arr[j + n] = arr[j];
}
arr[j + n] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {1, 8, 6, 29, 10, 14, 37, 48};//排序结果为1,6,8,10,14,29,37,48
shellSort(arr);
}
}
Ⅱ、🧁
我们首先计算出初始的间隔值gap，然后在每次循环中，将gap逐步减小，直到变为1。在每次循环中，对于每个间隔为gap的子序列，我们采用插入排序的方式进行排序。
public static void shellSort(int[] arr) {
int n = arr.length;
int h = 1;
// 计算间隔值
while (h < n / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
// 对每个子序列进行插入排序
for (int i = h; i < n; i++) {
for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
swap(arr, j, j - h);
}
}
// 缩小间隔值
h /= 3;
}
}
// 交换数组中两个元素的位置
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
- 计算间隔值时，只需要计算一次，并使用while循环找到最大的合适值。
- 使用插入排序对每个子序列进行排序，因为插入排序对于小数组来说效率更高。
- 在插入排序中，使用间隔值h来代替常规的1。
4、优缺点🍉
🧁优点：
- 希尔排序的时间复杂度较低。在大多数情况下，其时间复杂度为O(n^1.3)，尤其适用于中等大小的数组。
- 希尔排序不像其他排序算法需要大量的额外空间，因此可以在内存有限的情况下使用。
- 希尔排序是一种稳定的排序算法，即相同元素在排序前和排序后的位置不会发生改变。
🧁缺点：
- 希尔排序的实现较为复杂。它涉及到多个子序列和间隔值的计算，这增加了程序的代码量和阅读难度。
- 希尔排序由于具有不确定性，因此很难预测其排序时间。在某些情况下，其时间复杂度可能会退化到O(n^2)或更高，导致性能下降。
- 希尔排序的间隔值选择对于排序时间的影响非常大。如果选择错误的间隔值，可能会导致排序时间变得非常长。
综上所述，希尔排序是一种高效的排序算法，但实现较为复杂，且对于间隔值选择敏感。在某些情况下，可能存在性能问题。因此，在实际应用中，需要根据具体情况来选择是否使用希尔排序。
5、总结🍉
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。时间复杂度：平均情况：(nlogn)~ o(n²) 。最好情况：o(n¹˙³)。最环情况： o(n²) 。
- 空间复杂度：0(1)
- 稳定性：不稳定
- 适用场景：待排序序列元素较少时。
计数排序🍭
1、基本思想🍉
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用，是一种非基于比较的排序算法。操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
2、代码实现🍉
步骤：
- 找到数组中的最大值和最小值。
- 创建一个大小为(max-min+1)的桶，用于统计元素出现的次数。
- 遍历原数组，统计每个元素出现的次数，把它们放到对应的桶中。
- 对桶进行顺序求和，bucket[i]存放的就是原数组中小于等于i的元素个数。
- 从后往前遍历原数组，根据桶中统计的元素个数，将每个元素放到正确的位置上。
- 把排好序的元素复制回原数组。
public static void countingSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
// 找到数组中的最大值和最小值
int max = arr[0], min = arr[0];
for (int i = 1; i < arr.length; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
int bucketSize = max - min + 1; // 桶的大小
int[] bucket = new int[bucketSize]; // 创建桶
// 统计每个元素出现的次数
for (int i = 0; i < arr.length; i++) {
bucket[arr[i] - min]++;
}
//System.out.println(Arrays.toString(bucket));//[1, 1, 0, 0, 1, 0, 1, 0, 2]
// 对桶进行顺序求和，bucket[i]存放的就是原数组中小于等于i的元素个数
for (int i = 1; i < bucketSize; i++) {
bucket[i] += bucket[i - 1];
}
//System.out.println(Arrays.toString(bucket));//[1, 2, 2, 2, 3, 3, 4, 4, 6]
int[] temp = new int[arr.length]; // 创建临时数组
// 从后往前遍历原数组，根据桶中统计的元素个数，将每个元素放到正确的位置上
for (int i = arr.length - 1; i >= 0; i--) {
temp[--bucket[arr[i] - min]] = arr[i];
}
//System.out.println(Arrays.toString(temp));[1, 2, 5, 7, 9, 9]
// 把排好序的元素复制回原数组
for (int i = 0; i < arr.length; i++) {
arr[i] = temp[i];
}
}3、优缺点🍉
计数排序的主要优点是时间复杂度第，稳定性好，适用于范围小的整数数据。计数排序的主要缺点是需要额外的存储空间（当数据范围大时，这一缺点将会无限放大），无法处理浮点型数据排序等其他类型的数据。
4、算法分析🍉
下面n是待排序数组的长度，k是桶的大小
1、时间复杂度：O(n+k)。
因为不需要比较操作，只需要遍历一次原数组，并对桶进行顺序求和和遍历，所以它的时间复杂度是O(n+k)。由于k通常比n要小，因此计数排序的时间复杂度可以看作是线性的。
2、空间复杂度：O(n+k)。
计数排序需要创建一个足够大的桶来存储每个元素出现的次数，因此空间复杂度与桶的大小有关。如果待排序数组中的最大值和最小值之间差距很大，那么桶的数量会增加，导致空间复杂度变高。另外，由于计数排序不需要比较操作，因此它不需要额外的存储空间来存储比较结果，所以只需要考虑桶的大小对空间复杂度的影响。
3、稳定性：计数排序是一种稳定的排序算法。
因为它在统计每个元素出现次数时，使用了桶来存储每个元素的出现次数。当有多个元素值相同时，它们会被放到同一个桶里，并按照原始输入的顺序存储在桶中。在遍历桶时，我们按照桶内元素统计的顺序，将每个元素放到正确的位置上，从而保证了排序的稳定性。
5、应用场景🍉
适用于范围小的整数数据。（原因优缺点处已写）
归并排序🍭
1945年，约翰·冯·诺依曼（John von Neumann）发明了归并排序。归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。
1、基本思路🍉
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
动画展示：
2、代码实现🍉
Ⅰ、🧁递归写法
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}Ⅱ、🧁迭代写法
public static void mergeSort(int[] arr) {
int n = arr.length;
int[] temp = new int[n];
for (int gap = 1; gap < n; gap *= 2) {
for (int i = 0; i < n - gap; i += gap * 2) {
int left = i;
int mid = i + gap - 1;
int right = Math.min(i + 2 * gap - 1, n - 1);
merge(arr, left, mid, right, temp);
}
}
}
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int p = 0; p < k; p++) {
arr[left + p] = temp[p];
}
}迭代实现方式相对于递归实现方式，可以减少递归调用的开销，从而提高排序的效率。在迭代实现方式中，我们首先定义一个临时数组temp，然后将原始数组按照一定的间隔值gap分成若干个子数组，对每个子数组进行排序，并将排好序的子数组合并成一个有序数组。在合并的过程中，我们同样需要借助一个临时数组来存储排好序的元素。
3、代码优化🍉
Ⅰ、🧁对于短数组使用插入排序
虽然归并排序在大型数组上的表现很好，但它在小型数组上会变得较慢。对于长度小于或等于某个阈值的子数组，插入排序比归并排序要快得多。所以我们可以在代码中添加一个判断条件，在数组长度小于某个值时使用插入排序。
public static void mergeSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
if (r - l <= 15) {
insertSort(arr, l, r);
return;
}
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void insertSort(int[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
int temp = arr[i];
int j = i - 1;
for (; j >= l && arr[j] > temp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
总结🍉
1. 归并的缺点在于需要O(N)的空间复杂度，但是其速度仅次于快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
5.适用场景：待排序序列中元素较多，并且要求较快的排序速度时。
🧁归并排序解决海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了。
八大排序总结
1、初始数据集的排列顺序对算法的性能无影响的有:
- 堆排序
- 归并排序
- 选择排序
2、每一次排序之后都能确定至少一个元素位置的排序方法包括：
- 选择排序：每次将最大的数放到最后。所以最大的数排一次序后位置就确定了。
- 冒泡排序：同选择排序。每一次排序最大的值位置确定。
- 快排：每一次排序pivot的位置确定。
- 堆排序：每一次排序时，都是将堆顶的元素和最后一个节点互换，然后调整堆，再将堆大小减1。所以每一次排序堆顶元素确定。
3、不能至少确定一个元素的位置的方法包括：
- 插入排序：不到最后一步求的都是相对位置。
- shell排序：对简单插入排序的改进。不到最后一步，是无法确定每个元素位置的。
- 归并排序：局部有序，并不能确定任一元素在全局的位置。
- 基数排序，计数排序：利用桶排序的思路，不是基于比较的排序，也无法在一次排序中确定某个元素的位置。因为每一次排序都是整体处理。
4、请简单介绍一下冒泡排序的原理和实现方式：
冒泡排序的基本原理是依次比较相邻的元素，如果顺序不对则交换，每一轮都会确定一个数的位置。实现方式可以使用双重循环遍历数组，外层控制轮数，内层控制比较和交换。
5、请介绍快速排序的实现方式以及时间复杂度
快速排序采用分治法，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以分别对这两部分记录继续进行快速排序，以达到整个序列有序。实现方式类似冒泡排序，也是基于双重循环递归实现的，但是需要选取一个pivot来进行划分。时间复杂度为 O(n log n)。
6、请介绍堆排序的原理和实现方式。
堆排序的基本原理是将待排序元素构建成堆，逐步将堆顶元素和堆底元素交换，然后重新调整堆，重复此过程直至所有元素排序完毕。实现过程中需要先构建堆，然后依次将堆顶元素取出并调整堆。时间复杂度为 O(n log n)。
7、插入排序和选择排序的区别是什么？
插入排序和选择排序都属于简单排序算法，区别在于插入排序是将待排序元素插入到已排序数列中的合适位置，而选择排序则是在待排序元素中选择最小（或最大）的元素放到已排序的数列末尾。另外，插入排序比选择排序更适用于基本有序序列的排序。
8、请介绍归并排序的实现方式以及时间复杂度。
归并排序采用分治法，将待排序序列不断拆分为两个子序列，直至每个子序列只有一个元素，然后将两个有序子序列合并成一个有序序列。实现方式可以使用递归实现，也可以使用迭代实现。时间复杂度为 O(n log n)。
文章出处登录后可见！
