-
八大排序算法
介绍
排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。
排序分类
(1)内部排序:
指将需要处理的所有数据都加载到内部存储器(内存)中进行排序。
(2)外部排序法:
数据量过大，无法全部加载到内存中，需要借助外部存储(文件等)进行排序。
八大排序算法介绍
1、冒泡排序
冒泡排序(Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
优化:
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。演示冒泡过程的例子
原始数组：3，10，11，-1；从小到大排
第一轮排序
(1)3，10，11，-1 //如果前面的比后面的数字大的话，就交换
(2)3，10，11，-1
(3)3，10，-1，11
第二轮排序
(1)3，10，-1，11
(2)3，-1，10，11
第三轮排序
(1)-1，3，10，11
说明：
1、一共进行数组的大小-1次外循环(进行数组长度-1轮排序)
2、每一轮排序的次数(内循环)在逐渐的减少(每轮可以确定最大值或者最小值，取决于你想生序或降序)
3、如果我们发现在某轮排序中，没有发生一次交换，可以提前结束冒泡排序。这个就是优化
4、因为冒泡排序需要嵌套for循环，上面的外循环和内循环，指的是外面大的for循环(外循环)和嵌套在里面for循环(内循环)代码演示
public class BubbleSorting { public static void main(String[] args) { int arr[] = {3,9,-1,10,-2}; bubbleSort(arr); } public static void bubbleSort(int[] arr){ int temp = 0; //标记，如果某轮排序中，没有发生一次元素交换，即可提前结束冒泡排序 boolean flag= false; for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]){ flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第" + (i+1) + "轮排序结果"); System.out.println(Arrays.toString(arr)); if (flag){ //为真，证明交换过数据，需要重置后进行下一轮判断 flag = false; }else { //为假，证明在这轮排序中，没有交换过数据；结束循环 break; } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
运行结果
2、选择排序
基本介绍：选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
选择排序（select sorting)基本思想是：第一次从 arr[0]-arr[n-1]中选取最小值，与arr[0]交换，第二次从 arr[1]-arr[n-1]中选取最小值，与arr[1]交换,第三次从arr[2]-arr[n-1]中选取最小值，与amr[2]交换，…，第 i 次从arr[i-1]-arr[n-1]中选取最小值，与arr[i-1]交换，…，第n-1次从 arr[n-2]–arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
演示选择排序的过程
原始数组：101，34，119，1
第一轮排序：1，34，119，101
第二轮排序：1，34，119，101
第三轮排序：1，34，101，119
说明：
1、选择排序一共有数组长度 - 1 论排序
2、每一轮排序又是一个循环，思路如下：
2.1、先假定当前这个数是最小数min；
2.2、然后和后面的每个数进行比较，如果发现有比当前数更小的，就赋值给min确定最小数，并得到下标
2.3、当遍历到数组的最后时，得到本轮最小数以及下标；
2.4、进行交换代码演示
public class SelectSort { public static void main(String[] args) { int[] arr = {101, 34, 119, 1}; System.out.println("排序前：" + Arrays.toString(arr)); selectSort(arr); System.out.println("排序后：" + Arrays.toString(arr)); } public static void selectSort(int[] arr){ for (int i = 0; i < arr.length - 1; i++) { //最小值元素以及最小值下标 int min = arr[i]; int minIndex = i; for (int j = i + 1; j < arr.length; j++) { //如果想从大到小(降序)，把判断的大于号换成小于号即可 if (min > arr[j]){ //重置最小值以及最小值元素下标 min = arr[j]; minIndex = j; } } if(minIndex != i){ //最小值和遍历的首位元素交换位置 arr[minIndex] = arr[i]; arr[i] = min; } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
3、插入排序
基本介绍： 插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
插入排序(Insertion Sorting)的思想： 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
演示插入排序的过程
从小到大排序，代码演示也是；
代码演示
public class InsertSort { public static void main(String[] args) { int[] arr = {101, 34, 119, 1}; System.out.println("排序前：" + Arrays.toString(arr)); insertSort(arr); System.out.println("排序后：" + Arrays.toString(arr)); } public static void insertSort(int[] arr){ int insertVal = 0; int insertIndex = 0; for (int i = 1; i < arr.length; i++) { //定义待插入数 insertVal = arr[i]; //有序表中最大值，待插入元素的前一个元素下标 insertIndex = i - 1; // insertIndex >= 0 保证在给 insertVal 找插入位置时，不越界 // insertVal < arr[insertIndex]，从小到大排，所以待插入的元素比前一元素小的话，说明未找到插入位置 //想要从大到小排的话，改成insertVal > arr[insertIndex] while (insertIndex >= 0 && insertVal < arr[insertIndex]){ //需要将 arr[insertIndex] 元素后移，下标减一，寻找前一元素 arr[insertIndex + 1] = arr[insertIndex]; insertIndex --; } //当退出 while 循环时，说明插入位置找到了，insertIndex + 1是待插入元素需要插入的位置下标 arr[insertIndex + 1] = insertVal; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
4、希尔排序
基本介绍： 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的更高效版本，也称为缩小增量排序。
希尔排序的基本思想： 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
演示希尔排序的过程
原始数据：8、9、1、7、2、3、5、4、6、0
初始增量为gap = length / 2 = 5，分成五组[8,3],[9,5],[1,4],[7.6],[2,0]
对以上五组进行插入排序后会得到3、5、1、6、0、8、9、4、7、2顺序
再次缩小增量gap = 5 / 2 = 2，分成两组[3,1,0,9,7],[5,6,8,4,2]
对以上两组进行插入排序后会得到0、2、1、4、3、5、7、6、9、8顺序
再次缩小增量gap = 2 / 2 = 1，整个数组为一组[0,2,1,4,3,5,7,6,9,8]
对以上数组进行插入排序后会得到0、1、2、3、4、5、6、7、8、9顺序
经过上面的“宏观调控”，整个数组的有序化程度完美。此时，仅仅需要对以上数列简单微调，无需大量移动操作即可完成整个数组的排序。交换法的代码演示
public class ShellSort { public static void main(String[] args) { int[] arr = {8,9,1,7,2,3,5,4,6,0}; System.out.println("排序前：" + Arrays.toString(arr)); shellSort(arr); System.out.println("排序后：" + Arrays.toString(arr)); } //交换法 public static void shellSort(int[] arr){ int temp = 0; for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { for (int j = i - gap; j >= 0; j -= gap) { //从小到大排(升序)，如果前面比后面大，则交换；想从大到小排，换成<即可 if (arr[j] > arr[j + gap]){ temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
移位法的代码演示
public class ShellSort { public static void main(String[] args) { //测试80000个随机数组的排序速度 int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random() * 80000); } //运行前 LocalDateTime now = LocalDateTime.now(); System.out.println(now); shellSort(arr); //运行后 System.out.println(LocalDateTime.now()); } public static void shellSort(int[] arr){ //增量gap，逐步缩小增量，即分几个组进行排序 for (int gap = arr.length / 2; gap > 0; gap /= 2) { //从gap下标的元素，逐个对其所在的组进行插入排序 for (int i = gap; i < arr.length; i++) { //获取当前元素下标 和 元素值 int j = i; int temp = arr[j]; //从小到大；当j - gap不越界且 当前元素 小于 当前元素下标减去步长的元素值； //就后移(把前面的值赋值到后面)，因为temp保存了待插入(当前)元素的值 while (j - gap >= 0 && temp < arr[j - gap]){ arr[j] = arr[j - gap]; j -= gap; } //当退出while循环时，说明找到正确位置了 arr[j] = temp; } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
八万个随机数排序速度，别的代码也可以这样测试；
5、快速排序
快速排序（Quicksort)是对冒泡排序的一种改进。基本思想是： 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
演示快速排序的过程
代码演示
public class QuickSort { public static void main(String[] args) { int[] arr = {-9,-9,78,0,-23,-56,0,30}; System.out.println("排序前：" + Arrays.toString(arr)); quickSort(arr, 0, arr.length - 1); System.out.println("排序后：" + Arrays.toString(arr)); } public static void quickSort(int[] arr, int begin, int end){ if(begin < end) { int temp = arr[begin]; //将区间的第一个数作为基准数 int left = begin; //从左到右进行查找时的“指针”，指示当前左位置 int right = end; //从右到左进行查找时的“指针”，指示当前右位置 //不重复遍历；从小到大排序 while(left < right) { //当右边的数大于基准数时，略过，继续向左查找 //不满足条件时跳出循环，此时的right下标对应的元素是小于基准元素的 while (left < right && arr[right] > temp){ right --; } //将右边小于等于基准元素的数填入到左边相应位置 arr[left] = arr[right]; //当左边的数小于等于基准数时，略过，继续向右查找(因为是以第一个元素作为基准数，避免死循环) //不满足条件时跳出循环，此时的left下标对应的元素是大于基准元素的 while (left < right && arr[left] <= temp){ left ++; } //将左边大于基准元素的数填入左边相应位置 arr[right] = arr[left]; } //将基准元素填入相应位置 arr[left] = temp; //此时的left下标即为基准元素的位置 //对基准元素的左边子区间进行相似的快速排序 quickSort(arr,begin,left-1); //对基准元素的右边子区间进行相似的快速排序 quickSort(arr,left+1,end); }else { //如果区间只有一个数，则返回 return; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
6、归并排序
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer)策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
演示归并排序的过程
代码演示
public class MergeSort { public static void main(String[] args) { int[] arr = {8,4,5,7,1,3,6,2}; System.out.println("排序前：" + Arrays.toString(arr)); mergeSort(arr,0,arr.length - 1); System.out.println("排序后；" + Arrays.toString(arr)); } //分 + 合方法 public static void mergeSort(int[] arr,int left,int right){ if (left < right){ int mid = (right - left) / 2 + left; //向左递归分解 mergeSort(arr,left,mid); //向右递归分解 mergeSort(arr,mid + 1,right); merge(arr,left,mid,right); } } /** * 合并数组，从小到大排列； * @param arr 排序的原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 */ public static void merge(int[] arr,int left,int mid,int right){ //左边(s)、右边(r)有序序列的初始索引，初始化 int s = left,r = mid + 1; //指向temp数组的当前索引以及temp临时数组 int t = 0; int[] temp = new int[right - left + 1]; //1、先把两边的有序数据按照规则填充到 temp 数组，直到有一边处理完毕； while (s <= mid && r <= right){ //如果左边有序序列的元素 小于等于 右边元素，则填充到数组中； 反之，右边元素填充到数组 if (arr[s] <= arr[r]){ temp[t] = arr[s]; t += 1; s += 1; }else { temp[t] = arr[r]; t += 1; r += 1; } } //2、把一边有剩余的数据按顺序填充到 temp 数组中 //如果左边有序数组还有剩余，将其按顺序填充到 temp 数组中 while (s <= mid){ temp[t] = arr[s]; t += 1; s += 1; } //如果右边有序数组还有剩余，将其按顺序填充到 temp 数组中 while (r <= right){ temp[t] = arr[r]; t += 1; r += 1; } //3、将 temp 数组拷贝到 arr 数组中 //第一次合并的是下标0、1；第二次 2、3；第三次 0-3；第四次4、5；第五次6、7；第六次4-7；第七次0-7； for (int i = 0; i < temp.length; i++) { arr[left] = temp[i]; left ++; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
7、基数排序
基数排序(桶排序) 介绍：
1、基数排序（radix sort)属于“分配式排序”(distribution sort)，又称“桶子法”(bucket sort〉或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。
2、基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
3、基数排序(Radix Sort)是桶排序的扩展。
4、基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的基本思想： 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序的过程
将数组{53,3,542,748,14,214}使用基数排序，进行升序排序
第一轮取出个位数：按照个位上的数放到0-9号中桶里
第二轮取出十位数：按照十位上的数放到0-9号中桶里，如果是个位数，则放到0号桶中
第三轮取出百位数：按照百位上的数放到0-9号中桶里，如果是个位数或十位数，则放到0号桶中
代码演示
public class RadixSort { public static void main(String[] args) { int[] arr = {53,3,542,748,14,214}; System.out.println("排序前：" +Arrays.toString(arr)); radixSort(arr); System.out.println("排序后：" + Arrays.toString(arr)); } public static void radixSort(int[] arr){ //得到数组中最大值 int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max){ max = arr[i]; } } //得到最大数是几位数，+""将int转String获取长度 int maxLength = (max + "").length(); //定义一个二维数组，表示十个桶(包含10个一维数组)，一个桶代表一个一维数组； //为防止溢出，每个桶的大小都为arr.length(存放数据)；空间换时间 int[][] bucket = new int[10][arr.length]; //定义一个一维数组记录桶中的数据个数，bucketElementCounts[0] 记录的就是 bucket[0] 桶中数据个数 int[] bucketElementCounts = new int[10]; //需要循环多少次，以最大数是几位数为界限 for (int i = 0; i < maxLength; i++) { //10的 i 次方，方便下面求余 int n = (int) Math.pow(10, i); //针对每个元素的对应位进行排序，第一轮个位，第二轮十位，第三轮百位...... for (int j = 0; j < arr.length; j++) { //取出每个元素对应位的值 int element = arr[j] / n % 10; //数组元素放入到对应的桶中，参数：个位对应的桶；个位对应桶中的元素个数 bucket[element][bucketElementCounts[element]] = arr[j]; //桶中元素个数 + 1 bucketElementCounts[element] ++; } //数组中元素下标(一维数组的下标依次取出数据，放入到arr原数组) int index = 0; //遍历每个桶，并将桶中数据放入原数组 for (int k = 0; k < 10; k++) { if (bucketElementCounts[k] != 0){ //桶中有数据，再将该桶k中所以数据放入到原数组中 for (int j = 0; j < bucketElementCounts[k]; j++) { arr[index] = bucket[k][j]; index ++; } } //遍历完当前桶k 中的数据，就重置为0； bucketElementCounts[k] = 0; } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
基数排序说明
1、基数排序是对传统桶排序的扩展，速度很快.
2、基数排序是经典的空间换时间的方式，占用内存很大，当对海量数据排序时，容易造成OutOfMemoryError .
3、基数排序时稳定的。[假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[li]=ri]，且r[i]在r[]之前，而在排序后的序列中，rli]仍在r[i]之前，则称这种排序算法是稳定的;否则称为不稳定的]
4、有负数的数组，不建议基数排序，比较麻烦
8、堆排序
基本介绍：
1、堆排序是利用堆数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
2、堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，注意︰没有要求结点的左孩子的值和右孩子的值的大小关系。
3、每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
4、大顶堆举例说明：
5、小顶堆举例说明：
堆排序的基本思想：1、将待排序序列先构造成一个大顶堆
2、此时，整个序列的最大值就是堆顶的根节点。
3、将其与末尾元素进行交换，此时末尾就为最大值。
4、然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序的升序序列了.演示堆排序的过程
要求：给你一个数组{4，6，8，5，9}，使用堆排序，将数组生序
将数组构建成大顶堆（一般升序采用大顶堆，降序采用小顶堆）
1、给定无序序列列结构如下：
2、此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
3、找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
4、这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
5、将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素，如此反复进行交换、重建、交换
将堆顶元素8 和 末尾元素5 进行交换，得到第二大元素8
总结一下基本思路，可能上面看完演示过程也会懵
1、将无序序列构建成一个堆，根据生序(大顶堆)、降序(小顶堆)构建
2、构建完成后，将堆顶元素与末尾元素进行交换，将最大元素放到数组末端
3、重现调整结构，使其满足堆定义，然后继续交换堆顶元素和末尾元素，反复进行调整+交换；直到整个序列有序
4、当它的左子结点为末尾元素时：2n+1 = length-1 ==> n = length/2-1； 当它的右子结点为末尾元素时：2n+2 = length-1 ==> n = length/2-(3/2)；在计算机中3/2是等于1的,所以从arr.length/2-1代码演示
public class HeapSort { public static void main(String[] args) { //要求将数组进行升序排列 int[] arr = {4,6,8,5,9,16,-1,20,15,13,12,60,50}; System.out.println("排序前：" + Arrays.toString(arr)); heapSort(arr); System.out.println("排序后：" + Arrays.toString(arr)); } public static void heapSort(int[] arr) { //将无序序列构建成一个堆，根据升序/降序需求选择大顶堆/小顶堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr,i,arr.length); } //将 堆顶元素和末尾元素交换，将最大元素 交换到 数组末端；调整结构，满足堆的定义，反复执行交换 + 调整 for (int j = arr.length - 1; j > 0; j--) { int temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; // 从堆顶元素开始找到左右子节点中较大的数，和堆顶元素比较，如果比堆顶元素大，就替换元素； // 如果没有堆顶元素大，正好符合大顶堆的要求；下面写 break 就是这个原因 adjustHeap(arr,0,j); } } /** * 将一个以 i 为非叶子节点的子树，调整成一个大顶堆；并非整棵树 * 例：int arr[] = {4,6,8,5,9} ---> i = 1 => adjustHeap()方法 => 得到{4,9,8,5,6 } * @param arr 待调整数字组 * @param i 表示非叶子节点在数组中的索引 * @param length 对多少个元素继续调整，length是逐渐减少 */ public static void adjustHeap(int[] arr,int i,int length){ //取出当前元素值，保存在临时变量 int temp = arr[i]; //k = i * 2 + 1，k 是 i节点 的子节点 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { //i 的左子节点 小于 右子节点；k 指向右子节点 if (k + 1 < length && arr[k] < arr[k + 1]){ k ++; } //如果子节点 大于 父节点，把较大的值赋给当前节点，让 i 指向与其换位的子节点 if (arr[k] > temp){ arr[i] = arr[k]; i = k; }else { //已经是以 i 为顶点的大顶堆了，并不是整棵树奥 break; } } //for循环结束之后，再把保存的临时变量值赋值给 交换后的节点即可；相当于arr[k] = temp arr[i] = temp; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
排序算法的时间、空间复杂度介绍表
相关术语解释：稳定:如果a原本在b前面，而a=b，排序之后a仍然在b的前面;
不稳定:如果a原本在b的前面，而a-b，排序之后a可能会出现在b的后面;
内排序:所有排序操作都在内存中完成;
外排序:由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行;
时间复杂度:一个算法执行所耗费的时间。
空间复杂度:运行完一个程序所需内存的大小。
n:数据规模
k:“桶”的个数
In-place:不占用额外内存
Out-place:占用额外内存 -
相关阅读:
基于SSM的地方文创特产在线商城【数据库设计、源码、开题报告】
DOM知识点总结
在线Web页面测试工具-WebPageTest
CST初级教程 二
【无标题】
Jenkins部署失败：JDK ‘jdk1.8.0_381‘ not supported to run Maven projects
卷积神经网络的基本操作,卷积神经网络百度百科
高级深入--day32
如何基于智能识别技术构建工地智能化管理体系？
LibreCAD使用记录
- 原文地址：https://blog.csdn.net/weixin_46426906/article/details/127775255
