当前位置: 首页 > news >正文

【数据结构】七种排序方法,一篇文章掌握

文章目录

  • 前言
  • 1. 直接插入排序
    • 1.1 画图演示
    • 1.2 直接插入排序详细步骤
    • 1.3 时间复杂度,空间复杂度分析
  • 2. 希尔排序
    • 2.1 具体步骤描述
    • 2.2 代码详解
    • 2.3时间复杂度,空间复杂度分析
  • 3. 选择排序
    • 3.1 画图讲解
    • 3.2 代码讲解
    • 3.3 时间复杂度,空间复杂度分析
  • 4. 快速排序
    • 4.1 画图演示
    • 4.2 代码详解
    • 4.3 时间复杂度,空间复杂度分析
    • 4.5 快速排序的优化--挖坑法
      • 4.5.1 画图详解
      • 4.5.2 代码详解
  • 5. 冒泡排序
    • 5.1 排序讲解
    • 5.2 代码演示
    • 5.3 时间复杂度,空间复杂度分析
  • 6. 归并排序
    • 6.1 排序原理讲解
    • 6.2 代码详解
    • 6.3 时间复杂度,空间复杂度分析
  • 7. 堆排序
    • 7.1 排序原理
    • 7.2 画图讲解
    • 7.3 代码详解
    • 7.4 时间复杂度,空间复杂度分析.
  • 总结


前言

这篇文章是集合排序的知识,十分详细,可作为复习资料。我们需要掌握的排序方法有七种,分别是堆排序,快速排序,冒泡排序,选择排序,希尔排序,直接插入排序,归并排序。下面我们分别讲述这些排序的原理和应用。大家一定要对照着里面的图进行学习,不难的,我们开始啦!


1. 直接插入排序

1.1 画图演示

原数组,我们来具体说明怎么排序这个数组吧~
在这里插入图片描述

如下图,先排第二个元素1,定义循环变量(i=1),定义tmp等于arr[i],前面的3大于tmp,把3向后挪,==arr[j+1] = arr[j] ,j- -,==之后发现前面没有元素了(j < 0),退出循环,元素1就排好了
在这里插入图片描述
之后i++,排第三个元素4,前面的元素比它小,即(arr[j] <tmp)符合条件,退出循环,4排好了
在这里插入图片描述

i++,排第四个元素5,5同样,前面的4比它小,已经是有序的了
在这里插入图片描述
之后,i++,排第五个元素2,如下图,前面元素5,arr[j] > tmp, 把5往后挪(arr[j+1] = arr[j])
之后j-- ,再看4,4也是比2大,把4向后挪
直到当(j = 0)时,arr[j]是1,1比2小,就把2放在1的后面,也就是arr[j+1] = tmp

在这里插入图片描述

最后的9,0 一样的操作,不做赘述。最后排好的数组
在这里插入图片描述

1.2 直接插入排序详细步骤

  1. 排序一个数组,从数组第二个元素开始,与前面的元素比较。
  2. 先用变量tmp把这个元素存起来,如果前面的元素比它大,就把前面的元素向后挪,直到前面的元素比它小或者前面已经没有元素的时候,就把元素放在这个位置,这个元素就排完了。
  3. 为每个元素找到自己正确的位置,直到排完最后一个元素,数组就有序了。
  4. 举例。如下图,排序如下数组。

在这里插入图片描述
先排第二个元素1,先用变量tmp把元素1存起来,与前面的元素比较,发现1比3小,将3向后挪一位,用arr[j+1] = arr[j]来实现向后挪的动作.

因为从第二个元素到最后一个元素的每个元素都得找合适的位置,所以外层循环开始条件是第二个元素(i = 1),结束条件是最后一个元素(i < arr.length)。

那什么时候算是排好一个元素呢,就是前面元素比它小,或者前面已经没有元素了。所以内层循环的初始条件是从i的前一个元素开始比较(j = i - 1),结束条件是发现前面已经没有元素了(j >= 0).当(arr[j] < tmp)就代表找到对应的位置可以跳出循环了。把存好的tmp放到arr[j]后面的位置上。

public static void insertSort(int[] arr){for(int i = 1; i < arr.length; i++){int tmp = arr[i];int j = i - 1;//注意这里因为跳出内层循环时要使用j的位置,所以要把j定义在外循环中。for(; j >= 0; j--){if(arr[j] > tmp){//前面元素大,把元素向后挪arr[j+1] = arr[j];}else{//前面的元素比tmp小,意味着找到正确位置,跳出循环break;}//把arr[j]后面的位置给tmp.如果j = -1,//说明tmp就是前面的最小的元素,那就把arr[0]给tmp}arr[j+1] = tmp;}}

1.3 时间复杂度,空间复杂度分析

下面的链接,是具体介绍怎么计算时间复杂度和空间复杂度的.
https://editor.csdn.net/md/?articleId=126723532
直接插入排序适合数组趋于有序的时候,数组有序,直接插入排序时间复杂度能达到O(1).在==数组逆序的时候,时间复杂度达到最高,==为(n-1)+(n-2)+(n-3)+…+1,等差数列求和.
直接插入排序未占用额外空间.
时间复杂度:O(N^2)
空间复杂度: O(1)

2. 希尔排序

希尔排序是直接插入排序的优化,是怎么优化的呢?我们在直接插入排序中说过,当数据趋于有序时,是非常适合直接插入排序的.

2.1 具体步骤描述

这个方法需要画图辅助,才能清楚描述
排序如下数组

在这里插入图片描述

将数组分组排序,先定义gap = arr.length/2, 将所有相隔gap的数组元素进行排序,如图
arr[4]与arr[0]比较,arr[0]>arr[4],交换位置,把较小的换到前面,arr[5]arr[1]比较,arr[1]>arr[5],交换位置,以此类推,直到最后一个元素.
在这里插入图片描述
执行交换位置之后得到下图
在这里插入图片描述
令gap = gap/2,之后,令所有间隔为2的元素进行比较.把较小的往前换.如下图
在这里插入图片描述
执行完交换操作之后得到下图
在这里插入图片描述
之后再gap = gap/1, gap = 1,这时,排序就成了直接插入排序,由于数据已经趋于有序,所以排序的速度非常快.由于整个排序的过程,数据一直是逐渐趋于有序,所以==整个过程,排序速度是越来越快的.==最后得到如下数组
在这里插入图片描述

2.2 代码详解

如下代码,希尔排序的代码和直接插入的代码极其相似,就是在直接插入排序排序代码的基础上改动了几个地方.
i从gap处开始,依次与arr[i-gap]比较大小把较小值换到前面.,之后i++,直到i = arr.lengrh-1.

public static void shellSort(int[] arr){int gap = arr.length;while(gap >= 1){for(int i = gap; i < arr.length; i++){int tmp = arr[i];int j = i - gap;for(; j >= 0; j-= gap){   //注意这里,是j -= gap, 不是j--if(arr[j] > tmp){//注意这里是j+gaparr[j+gap] = arr[j];}else{break;}}arr[j+gap] = tmp;}gap /= 2;}}

2.3时间复杂度,空间复杂度分析

时间复杂度: O(n^2)
空间复杂度: O(1)
大家可能会有疑惑,为什么时间复杂度都是O(n^2)却把希尔排序称作直接插入排序的优化呢?
因为希尔排序,是逐渐把数组变得有序,每次排序的速度是越来越快的.
我们实操一下,获取语句执行时间的代码是

long start = System.currentTimeMillIs();{执行语句};long end = System.currentTimeMillIs();System.out.println("执行语句的执行时间为"+(end - start));

下图是,排序同一个数组,数组元素设为100000个逆序数据时,直接插入排序和希尔排序执行时间的差别,可以看出,希尔排序是比直接插入排序优秀的.
在这里插入图片描述
当是100000个趋于有序的数据时,两方法时间,直接插入排序更适合.所以,直接插入排序非常适合趋于有序的数组
在这里插入图片描述

3. 选择排序

选择排序,简单易懂.是从已有的数据中,选出最小的依次往后放,放完整个数组,数组就是有序的了.这个排序可以进行优化.我们这里直接介绍优化后的选择排序.优化呢,也很简单,就是==挑最小的和最大的,把最小的放前面,把最大的放后面.==两头抓,更快点.

3.1 画图讲解

如下图,找到数组最小值和最大值,最小值==min与arr[0]交换,最大值max与arr[length-1]==交换,
在这里插入图片描述
之后再从未排序数据中找出最大值最小值,再分别与前后元素交换,如下图
在这里插入图片描述
以此类推,在未排好序的数组中找出最小值,与前面元素交换,找出最大值,与后面元素交换
后续操作如下
在这里插入图片描述

3.2 代码讲解

用left,right控制排序进度,left起始值为0,right起始值为arr.length-1,每次排好一组数,left++,right–当left >= right排序结束.
注意一个易错点,当maxIndex == left时,前面经过swap(arr,minIndex,left);后,arr[left]的值已经被换到minIndex位置.
可以参考下图,maxIndex 等于 left时,经过swap(arr,minIndex,left);后5已经被换到了minIndex位置,所以要maxIndex = minIndex;来调整maxIndex的位置
在这里插入图片描述

public static void selectSort(int[] arr){long start = System.currentTimeMillis();int left = 0;int right = arr.length-1;while(left < right){int minIndex = left;int maxIndex = right;for(int i = left; i <= right; i++){if(arr[i] < arr[minIndex]){minIndex = i;}else if(arr[i] > arr[maxIndex]){maxIndex = i;}}swap(arr,minIndex,left);if(maxIndex == left){maxIndex = minIndex;}swap(arr,maxIndex,right);left++;right--;}long end = System.currentTimeMillis();System.out.println("选择排序时间为"+(end - start));}public static void swap(int[] arr, int a, int b){int tmp = arr[a];arr[a] = arr[b];arr[b] = tmp;}

3.3 时间复杂度,空间复杂度分析

时间复杂度: O(n^2)
空间复杂度: O(1)
100000个逆序数据,三种方法时间比较
在这里插入图片描述

4. 快速排序

快速排序,顾名思义,速度快.

4.1 画图演示

基本实现方法是,先以首元素arr[0]为基准,先从末尾向前找比arr[0]小的元素right,再从arr[1]开始,找到比arr[0]大的元素left,令left下标元素与right下标元素交换.

如下图,先从右向左找到比arr[0]小的元素1,再从左向右找比arr[0]大的元素5,令1和5交换
在这里插入图片描述

之后,right继续向左找到小于arr[0]的元素0,left向右找大于arr[0]的元素8,0和8交换在这里插入图片描述
以此类推,直到left与right相遇,循环结束,交换arr[0]和相遇的元素值,第一次排序就正式结束了.
在这里插入图片描述
观察上图,我们会发现,基准4的左边元素都比他小,4右边的元素都比他大.所以,我们只需对4左右的元素分成两组,分别排序后,数组就是有序的.

由于排序过程都是一样的,所以分别对基准左右元素排序的操作,我们用递归实现.
不同的是,左边的元素,从arr[0]开始到基准前的元素结束.
右边的元素从基准后的元素开始,到数组末尾结束.

用同样的方法对左边元素进行排序,把2当做新排序的基准,排2的左小组,再以0为基准,排0的右小组
在这里插入图片描述

对右边元素进行排序,把7当做新排序的基准,排7的左小组5和6, 7的右小组8,再以5为基准,排5的右小组6
在这里插入图片描述

4.2 代码详解

先进行第一次排序.
用(left < right)控制循环结束条件,先在右侧找到小于基准的,再在左侧找到大于基准的,交换数值后,继续循环.
需要注意的点
由于最后要交换arr[left]和left与right相遇处的值,所以,事先要定义一个index记录下来left的位置,int index = left;

 public static int partition(int[] arr, int left, int right){int tmp = arr[left];int index = left;while(left < right){while(right > left && arr[right] >= tmp){right--;}while(right > left && arr[left] <= tmp){left++;}swap(arr, left, right);}swap(arr,index, left);return left;}

由于,还要分别排序基准的左小组和右小组,更换基准,所以,我们会用到递归.那递归体和递归结束的条件怎么找呢.
我们先考虑怎么写这个递归,每次都要分别排序基准的左小组和右小组,每次分组的开始和结束位置都不同,如下图.左小组的开始位置没动,结束位置变成相遇处-1,右小组的开始位置变成相遇处+1,结束位置没变.
在这里插入图片描述
如下代码,用pivot记录上次相遇的坐标,那么左小组的排序就是开始位置与上次排序的结束位置相同,结束位置变成pivot-1,quick(arr, start, pivot-1);右小组的排序是开始位置是pivot+1,结束位置与上次排序的结束位置相同

 	public static void quick(int[] arr, int start, int end){int pivot = partition(arr, start, end);quick(arr, start, pivot-1);quick(arr, pivot+1, end);}

那怎么找递归的结束条件呢,我们来看什么情况下,递归会结束.如下图,当左小组只剩一个元素时,end = pivot -1,end < start,这时,只有一个元素,无需排序,就可以结束递归了.
在这里插入图片描述
右小组只剩一个元素时,start = pivot + 1,此时,start>end,递归结束
在这里插入图片描述
综上,递归结束的条件是==(start > end)==
所以,递归结束语句为

if(start > end){return;
}

快速排序完整代码如下

public static void quick(int[] arr, int start, int end){if(start >= end){return;}int pivot = partition(arr, start, end);quick(arr, start, pivot-1);quick(arr, pivot+1, end);}public static int partition(int[] arr, int left, int right){int tmp = arr[left];int index = left;while(left < right){while(right > left && arr[right] >= tmp){right--;}while(right > left && arr[left] <= tmp){left++;}swap(arr, left, right);}swap(arr,index, left);return left;}

4.3 时间复杂度,空间复杂度分析

由于使用了递归会占据内存的栈区,所以快速排序的空间复杂度是O(logN),是递归的次数
时间复杂度是O(n^2)
要注意一种特殊情况,当要排序的数组是逆序时,或者顺序的时候,例如9876543,我们看到,递归的次数变成了n,空间复杂度达到了O(n).所以,我们得出,当数组趋向有序的时候,不适合使用快速排序.
在这里插入图片描述

4.5 快速排序的优化–挖坑法

4.5.1 画图详解

为了解决快速排序不适合有序序列的问题,我们设计挖坑法对快速排序进行优化.
挖坑法的实现原理与快速排序类似,也不难.
如图,排序如下数组
在这里插入图片描述
还是,先以arr[0]为基准,先定义tmp存储基准的值,把arr[0]挖走,如图
在这里插入图片描述
先定义right为arr[length-1],从right位置向前找,找小于tmp的元素1,把1挖出来,填到arr[0]位置,如下图
在这里插入图片描述
再定义left为0,从left向右找大于基准的,找到了6,把6挖出来,填到右面的坑里
在这里插入图片描述
之后,再right往左找小于基准的,挖走,放到左边的坑里.left往右找大于基准的放到右边的坑里.
在这里插入图片描述
直到right,left相遇,把tmp放在left,right相遇的位置,
这时,我们发现,tmp左边元素的值都小于它,tmp右边元素的值都大于它.之后,再和快速排序一样,分别以相同的步骤递归tmp的左小组和右小组,递归条件不变.

4.5.2 代码详解

递归的初始和终止条件与快速方法一致.
不同的地方是,找到比基准小的right,找到比基准大的left,快速排序是要进行交换.而挖坑法是直接赋值

		while(right > left && arr[right] >= tmp){right--;}//找到right,把right挖走,放到left坑里arr[left] = arr[right];while(right > left && arr[left] <= tmp){left++;}把找到的left挖走,放到right坑里arr[right] = arr[left];}

完整代码如下

public static int[] quickSort02(int[] arr){quick02(arr,0,arr.length-1);return arr;}public static void quick02(int[] arr, int start, int end){if(start > end){return;}int pivot = partition02(arr, start, end);quick02(arr, start, pivot-1);quick02(arr, pivot+1, end);}public static int partition02(int[] arr, int left, int right){int tmp = arr[left];while(left < right){while(right > left && arr[right] >= tmp){right--;}arr[left] = arr[right];while(right > left && arr[left] <= tmp){left++;}arr[right] = arr[left];}arr[left] = tmp;return left;}

5. 冒泡排序

5.1 排序讲解

冒泡排序,是我们刚接触C语言时,就会学到的排序,我们需要牢记的是,两次循环的循环条件.假如要排十个数,外层9次循环就可以,内层第一次循环是9次,第二次循环是8次,所以内层循环控制条件是==(j < arr.length -1 - i)==

5.2 代码演示

public static void bubbleSort(int[] array){for(int i = 0; i < array.length-1; i++){for(int j = 0; j < array.length -1 - i; j++){if(array[j] > array[j+1]){swap(array,j,j+1);}}}}

5.3 时间复杂度,空间复杂度分析

时间复杂度:O(N^2)
空间复杂度:O(1)

6. 归并排序

6.1 排序原理讲解

归并排序,顾名思义呢,是先递归,再合并,不难.它是怎么递归,又是怎么合并的呢?例如排序如下数组
在这里插入图片描述

首先呢,先拆数组.找到数组的中间位置mid,将数组分为左右两部分,左半部分是left到mid,右半部分是mid+1到right.如下图
在这里插入图片描述
重新确定left,right,mid,再次拆数组,直到只剩一个元素的时候,例如下图,这是拆右面的数组.可以很清晰的看到,递归的截止条件是(left == right)
在这里插入图片描述
拆完之后,就开始合并数组啦,怎么合并呢?我们来继续看.
我们合并的核心思想就是合并两个有序数组,使合并后的数组仍然有序.

  1. 先分别合并3,2,使其成为一个有序数组,合并4,1,使其成为一个有序数组.如下图
  2. 在这里插入图片描述
    再合并2314数组,使其成为一个有序数组,如下图
    在这里插入图片描述
    左小组也是一样,先拆,再合并,如下图
    在这里插入图片描述
    最后,在合并两个大数组,使其称为有序数组,这个数组就排序完成了.
    在这里插入图片描述

6.2 代码详解

首先,我们要明确每次分组时,每组的起止位置.左小组的left不变,right变成mid,右小组的right不变,left变成mid+1.如下图所示.
在这里插入图片描述
所以递归我们这么写

public static void mergeChild(int[] arr, int left, int right){if(left == right){return;}int mid = (left+right)/2;mergeChild(arr,left,mid);mergeChild(arr, mid+1, right);merge(arr,left,mid,mid+1,right);}

然后,怎么合并两个有序数组呢,如下图,tmp是新数组,用于容纳最后排好序的数组.注意新数组的长度(right-left+1)
注意这里,由于最后要用到s1的初始值,所以要定义index记录一下s1.代码的最后一句话好好看一下.

private static void merge(int[] arr, int s1, int e1, int s2, int e2){int index = s1;int[] tmp = new int[e2-s1+1];//合并后数组的新长度(尾-首+1)int k = 0;while(s1 <= e1 && s2 <= e2){if(arr[s1] <= arr[s2]){tmp[k++] = arr[s1++];}else{tmp[k++] = arr[s2++];}}while(s1 <= e1){tmp[k++] = arr[s1++];}while(s2 <= e2){tmp[k++] = arr[s2++];}for(int i = 0; i < k; i++){//注意这里,由于最后要用到s1的初始值,所以要定义index记录一下arr[i+index] = tmp[i];}}

完整代码如下

	public static int[] mergeSort(int[] arr){mergeChild(arr,0,arr.length-1);return arr;}public static void mergeChild(int[] arr, int left, int right){if(left == right){return;}int mid = (left+right)/2;mergeChild(arr,left,mid);mergeChild(arr, mid+1, right);merge(arr,left,mid,mid+1,right);}private static void merge(int[] arr, int s1, int e1, int s2, int e2){int index = s1;int[] tmp = new int[e2-s1+1];//合并后数组的新长度(尾-首+1)int k = 0;while(s1 <= e1 && s2 <= e2){if(arr[s1] <= arr[s2]){tmp[k++] = arr[s1++];}else{tmp[k++] = arr[s2++];}}while(s1 <= e1){tmp[k++] = arr[s1++];}while(s2 <= e2){tmp[k++] = arr[s2++];}for(int i = 0; i < k; i++){//注意这里,由于最后要用到s1的初始值,所以要定义index记录一下arr[i+index] = tmp[i];}}

6.3 时间复杂度,空间复杂度分析

使用了递归,空间复杂度为O(N)
时间复杂度为O(n*logn)

7. 堆排序

7.1 排序原理

堆排序使用到完全二叉树这个数据结构,那我们来复习一下会用到的关于树的相关知识吧.
如下图,是一颗普通的树
根节点:没有前驱结点的结点,就是它前面没有别的结点了.
下图的根结点有两个孩子,左边的叫左孩子,右边的叫右孩子.
左孩子又作为父亲节点,有左右两个孩子.
每个结点都有自己的值(下面会展示,这个图没写结点的值)
在这里插入图片描述
完全二叉树
下面这棵树是完全二叉树,完全二叉树就是树必须从左到右按顺序,中间不能有空的地方,上面那棵树由于最后一棵子树空出了左孩子,所以不是完全二叉树.
在这里插入图片描述
大根堆
大根堆是每一个父亲结点都要大于它的左右孩子的值,如下图
在这里插入图片描述
小根堆就是所有的父亲结点的值都要小于左右孩子.
为结点标下标的话,我们会发现一些规律,从根为0下标开始,设父亲结点坐标为i,它的左孩子下标为2 x i+1,右孩子的坐标为2 x i+2.,那么设孩子结点下标为t时,父亲结点为(t-1)/2.
在这里插入图片描述
我们是怎么利用这棵树排序数组的呢?

  1. 我们先根据要排序的数组数据,建一个大根堆.
    那么根节点的值就是数组的最大值
  2. 把根节点放到树的末尾,数组的最大值就排好了.
  3. 之后再把其余结点调整为大根堆,那么根节点就是其余节点的最大值.
  4. 再把这个节点放到末尾.
  5. 这样循环,调整完所有结点,这个树从上到下,从左到右就是有序的了

7.2 画图讲解

1.先要建一个大根堆,这个要怎么建堆呢?我们往下看.
先从最后一棵树开始向下调整,使每棵树的父亲结点的值大于左右孩子结点的值.
怎么实现这个操作呢,就是先在左右孩子结点找出较大的值,与父亲结点值比较,若是父亲结点值较小,就将父亲结点值与这个孩子节点值交换.
如图,看最后一棵树,父亲结点值28,小于左孩子结点值37,交换父亲结点值与左孩子结点值,需要注意,我们这里说的树的顺序是从上到下,从左到右的.
在这里插入图片描述
交换后如下图,最后一棵树就调整好了
在这里插入图片描述
之后,按照同样的方法再从倒数第二棵树开始向下调整.如下图,找出这棵树左右孩子的较大值左孩子49,与父亲结点18比较,大于父亲节点的值,交换父亲结点值和左孩子结点值
在这里插入图片描述
交换后,如下图
在这里插入图片描述
再往前一棵树调整,找出左右孩子较大值65,比父亲结点19大,交换
在这里插入图片描述
交换后如图
在这里插入图片描述
再往前调整,找出左右孩子较大值49,比父亲结点15大,交换
在这里插入图片描述
交换后如图,这是我们发现下面调整好的的树也被影响了.父亲结点为15的那棵树,它的父亲结点值比左右孩子的值都小,所以,要把这棵树调整一下,令父亲结点值15与右孩子值25交换.
在这里插入图片描述
交换后如下图
在这里插入图片描述
再调整前面的树.同样的套路,这里不再赘述.
在这里插入图片描述
大家自己试着调整一下,调整好的树如下图所示.这个就是最终的大根堆了.我们看到,每一棵子树,它的父亲结点的值都要大于左右孩子节点的值.而根节点65是所有节点中最大的值.
在这里插入图片描述
还没完哦,之后把根节点值与末尾值交换,这样,就把最大值换到最后了.如下图
在这里插入图片描述
之后,在不动65的基础上再次把树调整为大根堆,从根元素开始向下调整
在这里文字描述.根元素28,小于左孩子结点值49,交换28与49,之后以28为父亲结点的子树,28小于右孩子节点值37,交换28与37.到这里,一个大根堆又建造好了.建好的大根堆如下图所示.
在这里插入图片描述
同样,49是第二大的元素,将49与倒数第二个元素15交换,这样,就把倒数第二大的元素换到倒数第二的位置了.
同样的方法,再次调整为大根堆,交换堆顶元素和末尾元素的值.这里大家自己操作试试.展示排好序的树
在这里插入图片描述

7.3 代码详解

第一步,建大根堆,从上图中我们看到,建大根堆是需要从最后一棵树的父亲结点开始调整.比较父亲结点与数值较大的孩子节点.一直到调整完第一棵树.
最后一棵树的父亲结点是啥捏.我们知道最后一个节点坐标是arr.length-1,那么它的父亲结点坐标就是==(arr.length-1-1)/2==.OK,循环的开始条件为(parent = (arr.length-1-1)/2),如下循环

		for(int parent = (array.length-1-1)/2; parent >= 0; parent--){shiftDown(array, parent, array.length);}

第二步,调整每一棵树,就是找到左右孩子的较大值,与父亲结点比较,比父亲结点大,则交换.再往后观察,看调整完之后有没有影响后面的树.

			if(child+1 < len && array[child+1] > array[child]){child++;}if(array[parent] < array[child]){swap(array, parent, child);}

如下图,调整完第一棵树后,发现父亲结点为15的树不满足条件了在这里插入图片描述
所以,我们要注意,调整完一棵树后,我们要检查一下后面的树还是否满足条件,不满足的话,还得继续往后调整一下.这里,令parent = child,child = 2 * parent +1, 再次进入循环,直到检查完最后一棵树,也就是child = arr.length时,跳出循环.

综上,调整树的代码如下

	private static void shiftDown(int[] array, int parent, int len){//从parent位置开始向下调整,调整一次后,parent = child, child = 2*parent + 1,child>len时跳出循环int child = 2*parent + 1;while(child < len){if(child+1 < len && array[child+1] > array[child]){child++;}if(array[parent] < array[child]){swap(array, parent, child);}parent = child;child = 2*parent + 1;}}

建完大根堆之后,就一次将堆顶元素与最后一个元素交换,换完之后,再把树调整为大根堆,再交换.需要注意的一点是,换好的元素就不能参与下一次循环了,所以,end要自减1.

		int end = array.length-1;while(end >= 0){swap(array,0,end);shiftDown(array,0,end);end--;}

综上,完整代码如下

public static void heapSort(int[] array){create(array);int end = array.length-1;while(end >= 0){swap(array,0,end);shiftDown(array,0,end);end--;}}private static void create(int[] array){for(int parent = (array.length-1-1)/2; parent >= 0; parent--){shiftDown(array, parent, array.length);}}private static void shiftDown(int[] array, int parent, int len){//从parent位置开始向下调整,调整一次后,parent = child, child = 2*parent + 1,child>len时跳出循环int child = 2*parent + 1;while(child < len){if(child+1 < len && array[child+1] > array[child]){child++;}if(array[parent] < array[child]){swap(array, parent, child);}parent = child;child = 2*parent + 1;}}public static void swap(int[] array, int parent, int child){int tmp = array[parent];array[parent] = array[child];array[child] = tmp;}

7.4 时间复杂度,空间复杂度分析.

时间复杂度: O(n x log n)
空间复杂度: O(1)


总结

总算总算是完成了,我们收藏起来多复习吧,不复习的话,没几天就忘没了,大家加油鸭!!

相关文章:

7K325T 引脚功能详解

本文针对7K325T芯片&#xff0c;详细讲解硬件连接需要注意的技术点&#xff0c;可以作为设计和检查时候的参考文件。为了方便使用&#xff0c;按照Bank顺序排列&#xff0c;包含配置Bank、HR Bank、HP Bank、GTX Bank、供电引脚等。 参考文档包括DS182、UG470、UG475、UG476等。…...

【设计模式】装饰者模式:以造梦西游的例子讲解一下装饰者模式,这也是你的童年吗?

文章目录1 概述1.1 问题1.2 定义1.3 结构1.4 类图2 例子2.1 代码2.2 效果图3 优点及适用场景3.1 优点3.2 适用场景1 概述 1.1 问题 众所周知&#xff0c;造梦西游3有四个角色&#xff0c;也就是师徒四人&#xff0c;这师徒四人每个人都有自己专属的武器和装备。假定我们以及设…...

QT 编译zlib

博主环境&#xff1a;QT 5.9.1 VS2105 从zlib官网下载zlib源代码&#xff0c;官网链接&#xff1a;https://www.zlib.net/&#xff0c;根据自己的需求进行下载&#xff0c;博主下载的是zip格式的。 下载完成后&#xff0c;进行解压。打开Developer Command Prompt for VS2015…...

沉睡者IT - 为你解密那些卖虚拟资源和知识付费课程的平台到底有多简单和多赚钱。

潜力博主推荐&#xff0c;点击上面关注博主 ↑ ↑ 上图为平台首页面截图&#xff0c;官方总站演示&#xff1a;vip.zzzz.la 备用演示&#xff1a;VIP.网站 1.虚拟资源平台介绍&#xff01; &#xff08;1&#xff09;虚拟资源项目站是一个在线知识付费平台&#xff0c;全自动…...

斐波那契数列、跳台阶、矩形覆盖、而进制中1的个数、判断是否是素数

文章目录1、斐波那契数列2、跳台阶3、矩形覆盖4、二进制中1的个数5、判断是否是素数1、斐波那契数列 本题考点&#xff1a; 间复杂度&#xff0c;fib理解&#xff0c;剪枝重复计算 牛客链接 题目描述&#xff1a; 解题思路&#xff1a; 代码&#xff1a; class Solution {…...

【Designing ML Systems】第 5 章 :特征工程

&#x1f50e;大家好&#xff0c;我是Sonhhxg_柒&#xff0c;希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流&#x1f50e; &#x1f4dd;个人主页&#xff0d;Sonhhxg_柒的博客_CSDN博客 &#x1f4c3; &#x1f381;欢迎各位→点赞…...

第5章 C语言高级的库函数

文章目录文档配套视频讲解链接地址第05章 C库函数5.1 assert.h 断言库5.2 ctype.h 测试和映射字符5.3 math.h 数学库5.4 stdlib.h 标准库1. 字符串转整数、浮点数2. strtod 把字符串中的数字转换成浮点数并返回数字的下一个字符的位置3. strtol 字符串转整数4. strtoul 字符串转…...

PCL Super4PCS算法实现点云粗配准(版本二)

目录 一、算法概述参数解析二、代码实现三、结果展示四、编译好的库一、算法概述 Win10系统下实现Super4PCS: Fast Global Pointcloud Registration via Smart Indexing一文中的配准算法。与版本一实现方式不同的是:这里直接将OpenGR集成到PCL中,目前网上也有很多相关的实现代…...

括号有效配对题型问题解法

目录 问题描述&#xff1a; 问题一&#xff1a;怎么判断一个括号字符串有效&#xff1f; 问题二&#xff1a;如果一个括号字符串无效&#xff0c;返回至少填几个字符能让其整体有效。 问题三&#xff1a;返回一个括号字符串中&#xff0c;最长的括号有效子串的长度。 问题四…...

前端学习路线(一)

很多人问我前端学习的路线是怎么样的&#xff0c;css要学多久&#xff0c;js高级要不要学&#xff0c;先学node.js还是先学vue&#xff0c;所以想通过一篇博文来讲一下这个事情 要不要学前端三剑客 这个问题是很多想快速上手前端的同学问的最多的一个问题&#xff0c;因为有很…...

【Linux系统】网络配置保姆级教学

目录 文章目录网络配置yum install tree 安装和tree显示Linux网络配置[原理图](https://so.csdn.net/so/search?q原理图&spm1001.2101.3001.7020)查看ip和网关ipconfig查看windows网络配置ifconfig查看Linux网络配置ping测试主机之间网络连通性Linux网络环境配置**第一种方…...

kibana 操作elasticsearch索引

前言 使用kibana可以很方便的对es进行各种操作&#xff0c;比如创建索引&#xff0c;删除索引&#xff0c;查询文档等&#xff0c;本篇先演示如何基于kibana 对es的索引进行常见的操作。 环境准备 请提前安装好es和kibana&#xff0c;可以参考 docker搭建es kibana操作es索引…...

什么是IP路由?思科与华为在IP路由配置上有啥区别?

什么是 IP 路由&#xff1f; IP 路由是将数据包从一个网络上的主机发送到不同远程网络上的另一台主机的过程。这个过程通常由路由器完成&#xff0c;路由器检查数据包的目标 IP 地址&#xff0c;确定下一跳地址&#xff0c;然后转发数据包。路由器使用路由表来确定应将数据包转…...

应该记住的10个SQL 查询

注意&#xff1a;所有查询都是用PostgreSQL编写的。 文章目录选择所有行where 语句Group by and Have 子句Order By and Limit日期函数内连接、左连接或右连接子查询相关子查询Case When 子句窗口函数对值进行排序选择所有行 SELECT * FROM employees如下&#xff1a; where…...

java毕业生设计医院新型冠状病毒疫苗接种管理系统计算机源码+系统+mysql+调试部署+lw

java毕业生设计医院新型冠状病毒疫苗接种管理系统计算机源码系统mysql调试部署lw java毕业生设计医院新型冠状病毒疫苗接种管理系统计算机源码系统mysql调试部署lw本源码技术栈&#xff1a; 项目架构&#xff1a;B/S架构 开发语言&#xff1a;Java语言 开发软件&#xff1a;…...

【python】都2022年不会还有人不会在电脑桌面上养宠物吧~

前言 嗨喽~大家好呀&#xff0c;这里是魔王呐 ! 上班枯燥&#xff0c;对着冷冰冰的电脑&#xff0c;相信很多小伙伴即使摸鱼&#xff0c;心情也不愉快。 这时如果有个萌宠能大家进行实时互动&#xff0c;这该有多好呀。再无聊的工作也能增添那么一丝趣味。 今天博主就来给大…...

双十一3000元投影仪评测排名,性价比最高的投影仪是什么品牌

今年的双十一各位都付尾款了吗&#xff1f;作为一年一度的大型电商节活动相信每个人都有参与&#xff0c;尤其是家用产品买的人应该会很多&#xff0c;就比如投影仪&#xff0c;能够代替电视使用&#xff0c;还能呈现出百寸以上的画面&#xff0c;视觉感觉俱佳。可以说3000元左…...

【跟学C++】C++STL标准模板库——算法详细整理(中)(Study18)

文章目录1、简介2、STL算法分类及常用函数2.1、变序算法(一)2.2.1 初始化算法(2个)2.2.2 修改算法(2个)2.2.3 复制算法(6个)2.2.4 删除算法(6个)3、总结 【说明】 大家好&#xff0c;本专栏主要是跟学C内容&#xff0c;自己学习了这位博主【 AI菌】的【C21天养成计划】&#x…...

嵌入式分享合集106

一、可控硅控制电路实例 可控硅是可控硅整流器的简称。可控硅有单向、双向、可关断和光控几种类型。它具有体积小、重量轻、效率高、寿命长、控制方便等优点&#xff0c;被广泛用于可控整流、调压、逆变以及无触点开关等各种自动控制和大功率的电能转换的场合。 单向可控硅是一…...

翻译文本的软件有哪些?这几个翻译工具你可以试试看

文本翻译&#xff0c;是我们在生活中或工作中比较常见的一个需求。例如有时收到一份英文资料&#xff0c;没时间逐字翻译成中文&#xff0c;那就需要借助翻译工具来帮忙了&#xff1b;或者是有时需要将一些内容翻译成英文&#xff0c;而碰巧遇到句子不知道如何翻译&#xff0c;…...

Android 通过Room操作SQLite数据库

谷歌推荐使用Room操作数据库&#xff0c;Room在 SQLite 上提供了一个抽象层&#xff0c;在充分利用 SQLite强大功能的同时&#xff0c;能够流畅地访问数据库。 Room的三个主要组件&#xff1a; 数据库类&#xff0c;用于保存数据库并作为应用持久性数据底层连接的主要访问点。…...

css--内外边距、 盒子模型、位置、浮动

一、内外边距 1.margin 1.1属性为给定元素设置所有四个&#xff08;上下左右&#xff09;方向的外边距属性。 上下左右具有四个方向:margin-top、margin-right、margin-bottom、margin-left可取值&#xff1a;length&#xff1a;固定值 percentage&#xff1a;相对于包…...

数据结构每日亿题(六)

文章目录一.用队列实现栈2.大概思路3.代码实现3.13.23.33.43.53.63.7二.用栈实现队列2.大概思路3.代码实现3.13.23.33.43.53.63.7三.结束一.用队列实现栈 原题传送门&#xff1a;力扣 题目&#xff1a;题目的意思是&#xff1a;给你两个队列&#xff0c;让你实现后入先出的操作…...

Java八股文

2022年接近年底了&#xff0c;想必绝大多数的小伙伴跳槽的心已经蠢蠢欲动。但一边又是互联网寒冬、大厂裁员&#xff0c;导致人心惶惶&#xff0c;想跳又不敢跳。但现在罡哥&#xff0c;给大家整理了八股文大厂面试真题和面试技巧。这里免费分享给大家。 资料包括&#xff1a;…...

自动化早已不是那个自动化了,谈一谈自动化测试现状和自我感受……

前言 从2017年6月开始接触自动化至今&#xff0c;已经有好几年了&#xff0c;从17年接触UI自动化&#xff08;unittestselenium&#xff09;到18年接触接口自动化&#xff08;unittestrequests&#xff09;再到18年自己编写自动化平台&#xff08;后台使用python的flask&#…...

蓝桥杯刷题(二)

蓝桥杯刷题一.空间二.排序三.成绩分析四.蛇形填数五.跑步锻炼&#xff08;较难&#xff09;一.空间 这道题很简单&#xff0c;要弄清单位间的转换和如何输出就可以啦 #include <stdio.h>int main() {printf("%.0f",256/(32/4/2/1024.0000/1024));return 0; }记…...

进程和线程详解

目录 前言&#xff1a; 操作系统定位 并发 并行 并发 进程 描述 PCB 管理 内存管理 进程间通信 线程 小结&#xff1a; 前言&#xff1a; 当一个程序运行起来时&#xff0c;操作系统要为之分配一些资源&#xff0c;这样的运行起来的程序称之为一个进程。为了有效解…...

flex blaze+java通信的例子

步骤&#xff1a; 1&#xff1a;建立java web程序 2&#xff1a; 下载blazeDS包&#xff0c;解压后将WEB-INF下的 flex&#xff0c;lib&#xff0c;web.xml复制到java程序的WEB-INF下 3&#xff1a;打开web.xml文件将以下代码的注释去掉&#xff0c;并修改 <param-value>…...

Allegro如何输出IDF文件操作指导

Allegro如何输出IDF文件操作指导 Allegro支持输出IDF文件,用于导入结构软件中检查和查看,具体操作如下 点击File-export-IDF 会弹出一个对话框,file name type选择IDF 然后点击export,输出IDF文件,文件已经输出 This section is describe what the function allegro h…...

生产工艺审批管理系统java项目开发jsp编程软件myeclipse开发Mysql数据库计算机网页

一、源码特点 JSP 生产工艺审批管理系统 是一套完善的web设计系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql&#xff0…...

actionScript 数组去重

public function unique(array:Array):Array { for (var i:int0; i < array.length; i) { for (var j:inti 1; j < array.length; j) { //注意 if (array[i] array[j]) { array.splice(j, 1); j--; } } } return array…...

【C++音视频开发】初级篇 | RGB与YUV

前言 本专栏将不间断更新有关C音视频开发的内容&#xff0c;其中有初级篇、中级篇与高级篇的内容&#xff0c;包括但不限于音视频基础、FFmpeg实战、QT、流媒体客户端、流媒体服务器、WebRTC实战、Android NDK等等。是博主花了将近5000元购买的课程中的知识点&#xff0c;其中…...

Html-文本属性

常用的文本属性 属性描述说明font-size字体大小单位是px&#xff0c;浏览器默认是16px。font-family字体多个字体中间用逗号链接&#xff0c;先解析第1个字体,如果没有解析第2个字体,以此类推color颜色 red;#ff0;rgb(255,0,0); 0-255font-weight加粗 bolder(更粗的&#xff09…...

Dockerfile

Dockerfile指令集 对于Dockerfiel而言&#xff0c;是在学习docker工具里面&#xff0c;最重点的内容&#xff0c;它可以帮助我们生成自己想要的基础镜像。部署一个容器最重要的就是镜像&#xff0c;指令都已经内置好了。 FROM 这个镜像的妈妈是谁&#xff1f;&a…...

Java反射04:获取运行时类的属性结构及其内部结构

文章目录获取运行时类的属性结构及其内部结构新建测试类1.获取每一个Field&#xff08;属性&#xff09;2.获取运行时类的方法结构3.获取运行时类的构造器4.获取当前运行时所继承的父类和接口5.获取当前运行时类的注解、包、泛型获取运行时类的属性结构及其内部结构 通过反射获…...

双软企业认定需要什么条件

认定双软企业的好处 1、税收优惠:所得税两免三减半。双软认证企业&#xff0c;自获利年度起&#xff0c;第一年和第二年免征企业所得税&#xff0c;第三年至第五年减半征收企业所得税。 增值税超过3%的部分即征即退。 2、政策支持:各地政府对于科研专项资金、税收减免科技计划、…...

qsettings 读写注册表

qsettings简单的实现一个注册表读写操作&#xff0c;记录程序中需要保存的信息。使用qsettings声明对象之前&#xff0c;需要指明qsettings的组织名和应用名&#xff0c;分别利用QCoreApplication::setOrganizationName()和QCoreApplication::setApplicationName()来指定组织名…...

【JavaScript高级进阶】构造函数和原型,学会prototype

目录 前言 1.构造函数和原型 1.1使用prototype解决内存浪费的问题 1.2constructor构造函数构造器构造函数 2.原型链 2.1js中成员查找规则 2.2原型对象this指向 2.3扩展内置对象 3.call作用 4.继承 4.1利用原型对象继承 写在最后 前言 哈喽哈喽大家好&#xff0c;因为…...

VMware16虚拟机添加硬盘(磁盘)和挂载硬盘(磁盘)

记录&#xff1a;317 场景&#xff1a;在VMware16虚拟机&#xff0c;安装了CentOS 7.9操作系统场景下&#xff0c;添加硬盘(磁盘)和挂载硬盘(磁盘)。 版本&#xff1a; 操作系统&#xff1a;CentOS 7.9 1.机器配置 机器名称&#xff1a;B200&#xff1b;主机名称&#xff…...

【学生个人网页设计作品】使用HMTL制作一个超好看的保护海豚动物网页

&#x1f389;精彩专栏推荐 &#x1f4ad;文末获取联系 ✍️ 作者简介: 一个热爱把逻辑思维转变为代码的技术博主 &#x1f482; 作者主页: 【主页——&#x1f680;获取更多优质源码】 &#x1f393; web前端期末大作业&#xff1a; 【&#x1f4da;毕设项目精品实战案例 (10…...

短视频社交|电影点播平台Springboot+vue+ElementUI前后端分离

感谢您的关注&#xff0c;请收藏以免忘记&#xff0c;点赞以示鼓励&#xff0c;评论给以建议&#xff0c;爱你哟 项目编号&#xff1a;BS-PT-071 一&#xff0c;项目简介 本项目基于Springbootvue开发实现了一个电影点播和短视频分享平台&#xff0c;名为爱奇艺影视平台系统。…...

基于Springboot+mybatis+mysql+html图书管理系统

基于Springbootmybatismysqlhtml图书管理系统一、系统介绍二、功能展示1.用户登陆2.图书管理3.读者管理4.借还管理5.密码修改6.图书查询&#xff08;读者&#xff09;7.个人信息&#xff08;读者&#xff09;8.我的借还&#xff08;读者&#xff09;一、系统介绍 系统主要功能…...

【数据结构】第三章 栈和队列

1.单选(2分) ‏下列关于队列的叙述正确的是&#xff08; &#xff09;。 A.在队列中只能删除数据 B.队列是先进先出的线性表 C.队列是后进先出的线性表 D.在队列中只能插入数据 正确答案&#xff1a;B 2.单选(2分) ‌一个栈的输入序列为1&#xff0c;2&#xff0c;3&#xff0…...

公众号网课查题系统

公众号网课查题系统 本平台优点&#xff1a; 多题库查题、独立后台、响应速度快、全网平台可查、功能最全&#xff01; 1.想要给自己的公众号获得查题接口&#xff0c;只需要两步&#xff01; 2.题库&#xff1a; 查题校园题库&#xff1a;查题校园题库后台&#xff08;点击…...

02 LaTex之小tips

1.运行 2.头&#xff0b;尾 \documentclass[11pt]{article}\usepackage{algorithm, algpseudocode} \usepackage{amsmath,amssymb,amsthm} \usepackage{mathrsfs}% huaxie zimu \textwidth 16cm\textheight 22cm\oddsidemargin0cm\evensidemargin\oddsidemargin\usepackage{un…...

使用kubeadm搭建高可用集群-k8s相关组件及1.16版本的安装部署

本文是向大家分享k8s相关组件及1.16版本的安装部署&#xff0c;它能够让大家初步了解k8s核心组件的原理及k8s的相关优势&#xff0c;有兴趣的同学可以部署安装下。 什么是kubernetes kubernetes是Google 开源的容器集群管理系统&#xff0c;是大规模容器应用编排系统&#xff…...

为了摸鱼,我开发了一个工具网站

&#x1f3e1; 博客首页&#xff1a;派 大 星 ⛳️ 欢迎关注 &#x1f433; 点赞 &#x1f392; 收藏 ✏️ 留言 &#x1f3a2; 本文由派大星原创编撰 &#x1f6a7; 系列专栏&#xff1a;《开源专栏》 &#x1f388; 本系列主要输出作者自创的开源项目 &#x1f517; 作品&…...

CodeForces - 545E Paths and Trees 最短路建树

题目链接&#xff1a;点击查看 Little girl Susie accidentally found her elder brothers notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to a…...

koa + pug模板引擎

模板引擎 模板引擎&#xff1a;模板引擎是web应用中动态生成html的工具&#xff0c;负责将数据和模板结合。常见模板引擎有&#xff1a;ejs、jade&#xff08;现更名为pug&#xff09;、Handlebars、Nunjucks、Swig等&#xff1b;使用模板引擎可以是项目结构更加清晰&#xff…...

数字集成电路设计(二、Verilog HDL基础知识)

文章目录1. 语言要素1.1 空白符1.2 注释符1.3 标识符1.3.1 转义标识符1.4 关键字1.5 数值1.5.1 整数及其表示方式1.5.2 实数及其表示方式1.5.3 字符串及其表示方式2. 数据类型2.1 物理数据类型2.1.1 连线型2.1.2 寄存器型2.2 连线型和寄存器型数据类型的声明2.2.1 连线型数据类…...