内部排序(插入、交换、选择)

一、排序的部分基本概念

1. 算法的稳定性

若待排序表中有两个元素 Ri 和 Rj ,其对应的关键字相同即 keyi = keyj,且在排序前 Ri 在 Rj 的前面,若使用某一排序算法排序后,Ri 仍然在 Rj 的前面,则称这个排序算法是稳定的,否则称排序算法是不稳定的。

需要注意的是,算法是否具有稳定性并不能衡量一个算法的优劣 ,它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复,则排序结果是唯一的,那么选择排序算法时的稳定与否就无关紧要。

2. 排序的分类

在排序过程中,根据数据元素是否完全在内存中,可将排序算法分为两类:

1)内部排序

是指在排序期间元素全部存放在内存中的排序。

2)外部排序

是指在排序期间元素无法全部同时存放在内存中,必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

3. 一些结论

对于任意序列进行基于比较的排序,求至少的比较次数应考虑最坏情况。对任意 n 个关键字排序的比较次数至少为 ⌈log2(n!)⌉ 。

上述公式证明如下:在基于比较的排序方法中,每次比较两个关键字后,仅出现两种可能的转移。假设整个排序过程至少需要做 t 次比较,则显然会有 2t 种情况。由于 n 个记录共有 n! 种不同的排列,因而必须有 n! 种不同的比较路径,于是有 2t >= n!,即 t >= log2(n!) 。考虑到 t 为整数,故为 ⌈log2(n!)⌉ 。

二、插入排序

插入排序是一种简单直观的排序方法,其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列,直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法:直接插入排序、折半插入排序和希尔排序。
【注】默认排序结果为非递减有序序列。

1. 直接插入排序

1)算法思想与实现步骤

① 直接插入排序的基本思想是:
将待排序的数组分为已排序和未排序两部分。每次从未排序部分中取出一个元素,找到其在已排序部分中的合适位置并插入。

② 直接插入排序的实现步骤是:
a)从第二个元素开始,依次取出待排序部分的第一个元素(当前元素)。
b)与已排序部分的元素进行比较,找到当前元素合适的插入位置。
(即找到元素 L(i) 在有序序列 L[1…i - 1] 中的插入位置 k )
c)将已排序部分中大于当前元素的元素向后移动一位,为当前元素腾出位置。
(即将 L[ k…i - 1] 中的所有元素依次后移一个位置)
d)将当前元素插入到找到的位置
(即将 L(i) 复制到 L(k) )
e)重复步骤 a-d 直到所有元素均被插入。

为了实现对 L[1…n] 的排序,可以将 L(2) ~ L(n) 依次插入前面已排好序的子序列,初始 L[1] 可以视为是一个已排好序的子序列。插入排序在实现上通常采用 就地排序(空间复杂度为 O(1) ),因而在从后向前的比较过程中,需要反复把已排序元素逐步向后挪位,为新元素提供插入空间。

2)算法的C++代码

void InsertSort(ElemType A[],int n) {int i, j;for(i=2; i<=n; i++) {		// 依次将A[2]~A[n]插入前面已排好序的序列中if(A[i]<A[i-1]) {		// 若A[i]关键字小于其前驱,将A[i]插入有序表A[0] = A[i];		// 复制为哨兵,A[O]不存放元素for(j=i-1; A[0]<A[j]; --j){	// 从后往前查找待插入位置A[j+1] = A[j];	// 向后挪位} A[j+1] = A[O] ;		// 复制到插入位置}}
}

3)示例

假定初始序列为 49, 38, 65, 97, 76, 13, 27, 49’,初始时 49 可以视为一个已排好序的子序列,按照上述算法进行直接插入排序的过程如下图所示,括号内是已排好序的子序列。

4)算法的性能分析

① 时间复杂度与空间复杂度

I、空间效率:仅使用了常数个辅助单元,因而空间复杂度为 O(1) 。

II、时间效率:在排序过程中,向有序子表中逐个地插入元素的操作进行了 n - 1 趟,每趟操作都分为比较关键字和移动元素,而比较次数和移动次数取决于待排序表的初始状态。

  • 在最好情况下:表中元素已经有序,此时每插入一个元素,都只需比较一次而不用移动元素,因而时间复杂度为 O(n) 。
  • 在最坏情况下:表中元素顺序刚好与排序结果中的元素顺序相反(逆序),总的比较次数达到最大,总的移动次数也达到最大,总的时间复杂度为 O(n2) 。
  • 平均情况下:考虑待排序表中元素是随机的,此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度,总的比较次数与总的移动次数均约为 n2 / 4 。

因此,直接插入排序算法的时间复杂度为 O(n2) 。

② 稳定性

由于每次插入元素时总是从后向前先比较再移动,所以不会出现相同元素相对位置发生变化的情况,即直接插入排序是一个稳定的排序方法。

③ 适用性

直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时,可以从前往后查找指定元素的位置。

2. 折半插入排序

从直接插入排序算法中,不难看出每趟插入的过程中都进行了两项工作: ① 从前面的有序子表中查找出待插入元素应该被插入的位置;② 给插入位置腾出空间,将待插入元素复制到表中的插入位置。
当排序表为顺序表时,可以对直接插入排序算法做如下改进: 由于是顺序存储的线性表,所以查找有序子表时可以用折半查找来实现。确定待插入位置后,就可统一地向后移动元素。

1)算法思想与实现步骤

① 折半插入排序的基本思想是:
折半插入排序是对直接插入排序的优化,通过折半查找的方法来提高插入的位置寻找效率。它减少了比较次数,但在后面的插入步骤中仍需移动元素。

② 折半插入排序的实现步骤是:
a)从第二个元素开始,依次取出待排序部分的第一个元素(当前元素)。
b)在已排序部分使用折半查找找到当前元素的插入位置。
c)移动已排序部分中大于当前元素的元素,为当前元素腾出位置。
d)将当前元素插入到找到的位置。
e)重复步骤 a-e 直到所有元素均被插入。

2)算法的C++代码

void InsertSort(ElemType A[], int n) {int i, j, low, high, mid;for(i=2; i<=n; i++) {	// 依次将A[2]~A[n]插入前面的已排序序列A[O] = A[i];		// 将A[i]暂存到A[O]low = 1; high = i-1; 	// 设置折半查找的范围while(low <= high) {	// 折半查找(默认递增有序)mid = (low+high)/2; 	// 取中间点if(A[mid]>A[O]){high = mid-1;}	// 查找左半子表else{low = mid+1;}		// 查找右半子表}for(j=i-1; j>=high+1; --j){		// 此时的high+1=lowA[j+1] = A[j]; 		// 统一后移元素,空出插入位置}A[high+1] = A[O]; 		// 插入操作}
}

3)算法的性能分析

① 时间复杂度与空间复杂度

I、空间效率:仅使用了常数个辅助单元,因而空间复杂度为 O(1) 。

II、从上述算法中,不难看出折半插入排序仅减少了比较元素的次数,约为 O(nlog2n),该比较次数与待排序表的初始状态无关,仅取决于表中的元素个数 n ;而元素的移动次数并未改变,它依赖于待排序表的初始状态。
因此,折半插入排序的时间复杂度仍为 O(n2) ,但对于数据量不很大的排序表, 折半插入排序往往能表现出很好的性能。

② 稳定性

折半插入排序是一种稳定的排序方法。

③ 适用性

折半插入排序算法仅适用于顺序存储的线性表。

3. 希尔排序

直接插入排序算法的时间复杂度为 O(n2),但若待排序列为“正序”时,其时间效率可提高至 O(n),由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的,又称缩小增量排序。

1)算法思想与实现步骤

① 希尔排序的基本思想是:
希尔排序是插入排序的一种改进版本,通过选取增量序列来将数组分成多个子序列,分别进行局部排序,最后再进行整体插入排序。这种方法可以减少元素的移动次数,提升排序效率。

② 希尔排序的实现步骤是:
a)选择一个增量序列。
(例如,初始增量为 d(小于 n ,通常 d = n / 2),随后不断缩小增量,直到增量为 1 )
b)对于每个增量,按增量将整个数组分为若干个子序列。
(即将待排序表分割成若干形如 L[ i, i + d, i + 2d, … , i + kd ] 的“特殊"子序列)
c)对每个子序列进行直接插入排序。
d)重复步骤 b-c,直到增量为 1 。
e)最后对整个数组进行一次插入排序,确保整体有序。

2)算法的C++代码

void ShellSort(ElemType A[] , int n) {
// A[O]只是暂存单元,不是哨兵,当j<=O时,插入位置已到int d, i, j;for(d=n/2; d>=1; d=d/2){	// 增量变化(无统一规定)for(i=d+1; i<=n; ++i){if(A[i]<A[i-d]){		// 需将A[i]插入有序增量子表A[O] = A[i];		// 暂存在A[O]for(j=i-d; j>O && A[0]<A[j]; j-=d){A[j+d] = A[j];		// 记录后移,查找插入的位置}A[j+d] = A[0]; 		// 插入}}}
}

3)示例

(先追求表中元素部分有序,再逐渐逼近全局有序。)

4)算法的性能分析

① 时间复杂度与空间复杂度

I、空间效率: 仅使用了常数个辅助单元,因而空间复杂度为 O(1) 。

II、时间效率: 由于希尔排序的时间复杂度依赖于增量序列的函数,这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。

  • 当 n 在某个特定范围时,希尔排序的时间复杂度约为 O(n1.3) 【优于直接插入排序】。
  • 在最坏情况下希尔排序的时间复杂度为 O(n2) 。

希尔排序最好的情况是序列原本就有序,比较好的情况是序列基本有序。

② 稳定性

当相同关键字的记录被划分到不同的子表时,可能会改变它们之间的相对次序,因此希尔排序是一种不稳定的排序方法。

③ 适用性

希尔排序算法仅适用于线性表为顺序存储的情况。

三、交换排序

所谓交换,是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法很多,下面主要介绍冒泡排序和快速排序。

1. 冒泡排序

1)算法思想与实现步骤

① 冒泡排序的基本思想是:
冒泡排序通过从后往前(或从前往后)两两比较相邻元素的值,若为逆序(即 A[i - 1] > A[ i ] ),则交换它们,将最小的元素逐步“冒泡”到序列的开头(或将最大的元素逐步“冒泡”到序列的末尾)。这个过程重复进行,前一趟确定的最小(或最大)的元素不再参与比较,每趟冒泡都会将未确定序列中下一个最小(或最大)的元素放到正确的位置。这样最多做 n - 1 趟冒泡就能把所有元素排好序。

② 冒泡排序的实现步骤是:
a)从尾到头(或从头到尾)遍历序列,比较相邻的两个元素。
b)如果前一个元素大于后一个元素,则交换这两个元素。
c)每遍历一轮,最小的元素会传到序列的开头(或最大的元素会传到序列的末尾)。
d)重复步骤 a-c,直到没有交换发生为止。

注意:冒泡排序中所产生的有序子序列一定是全局有序的(不同于直接插入排序),也就是说,有序子序列中的所有元素的关键字一定小于(或大于)无序子序列中所有元素的关键字,这样每趟排序都会将一个元素放置到其最终的位置上。

2)算法的C++代码

void BubbleSort(ElemType A[],int n){for(int i=O; i<n-1; i++){bool flag = false;		// 表示本趟冒泡是否发生交换的标志for(int j=n-1; j>i; j--){	// 一趟冒泡过程if(A[j-1] > A[j]){		// 若为逆序swap (A[j-1], A[j]);	// 交换flag = true;}}if(flag==false){return;}	// 本趟遍历后没有发生交换,说明表已经有序}
}

3)示例

4)算法的性能分析

① 时间复杂度与空间复杂度

I、空间效率:仅使用了常数个辅助单元,因而空间复杂度为 O(1) 。

II、时间效率:

  • 当初始序列有序时,显然第一趟冒泡后 flag 依然为 false(本趟没有元素交换),从而直接跳出循环,比较次数为 n - 1,移动次数为 0,从而最好情况下的时间复杂度为 O(n);
  • 当初始序列为逆序时,需要进行 n - 1 趟排序,第 i 趟排序要进行 n - i 次关键字的比较,而且每次比较后都必须移动元素 3 次来交换元素位置。

从而,最坏情况下的时间复杂度为O(n2),平均时间复杂度为O(n2) 。

② 稳定性

由于 i > j 且 A [i] = A [j] 时,不会发生交换,因此冒泡排序是一种稳定的排序方法。

③ 适用性

冒泡排序算法适用于顺序存储和链式存储的线性表。

2. 快速排序

1)算法思想与实现步骤

① 快速排序的基本思想是:
快速排序采用分治法,在待排序表 L[1…n] 中任取一个元素 pivot 作为枢轴(或称基准,通常取首元素),通过一趟排序将待排序表划分为独立的两个子表 L[1…k - 1] 和 L[k + 1…n],使得 L[1…k - 1] 中的所有元素小于 pivot,L[k + 1…n] 中的所有元素大于或等于 pivot,则 pivot 放在了其最终位置 L(k) 上,这个过程称为一次划分。然后分别递归地对左右两个子表重复上述过程,直至每部分内只有一个元素或空为止,即所有元素放在了其最终位置上。

② 快速排序的实现步骤是:
a)从待排序表中选择一个基准元素(通常选第一个、最后一个或中间的元素)。
b)将待排序表重排,使得基准的左侧是所有小于基准的元素,右侧是所有大于基准的元素。
c)递归地对基准左侧和右侧的子表进行快速排序。
d)直到子表的规模为 1 或 0(即已经是有序的)。

注意:在快速排序算法中,并不产生有序子序列,但每趟排序后会将上一趟划分的各个无序子表的枢轴(基准)元素放到其最终的位置上。

2)算法的C++代码

void QuickSort (ElemType A[],int low,int high){if(low < high) {	// 递归跳出的条件int pivotpos = Partition(A, low, high);		// 划分// Partition()就是划分操作,将表A[low…high]划分为满足上述条件的两个子表QuickSort(A, low, pivotpos-1);		// 依次对两个子表进行递归排序QuickSort(A, pivotpos+l, high);}
}
int Partition(ElemType A[], int low, int high) {	// 一趟划分ElemType pivot = A[low];	// 将当前表中第一个元素设为枢轴,对表进行划分while(low < high) {			// 循环跳出条件while(low < high && A[high] >= pivot) {--high;}A[low] = A[high];		// 将比枢轴小的元素移动到左端while(low < high && A[low] <= pivot) {++low;}A[high] = A[low];		// 将比枢轴大的元素移动到右端}A[low] = pivot;		// 枢轴元素存放到最终位置return low;			// 返回存放枢轴的最终位置
}

3)示例

用二叉树的形式描述这个举例的递归调用过程,如下图所示:

4)算法的性能分析

① 时间复杂度与空间复杂度

I、空间效率:由于快速排序是递归的,需要借助一个递归工作栈来保存每层递归调用的必要信息,其容量与递归调用的最大深度一致。

  • 最好情况下为 O(log2n);
  • 最坏情况下,因为要进行 n - 1 次递归调用,所以栈的深度为 O(n) ;
  • 平均情况下,栈的深度为 O(log2n) 。

II、时间效率:快速排序的运行时间与划分是否对称有关。快速排序的最坏情况发生在两个区域分别包含 n - 1 个元素和 0 个元素时,这种最大限度的不对称性若发生在每层递归上,即对应于初始排序表基本有序或基本逆序时,就得到最坏情况下的时间复杂度为 O(n2) 。

有很多方法可以提高算法的效率: 一种方法是尽量选取一个可以将数据中分的枢轴元素,如从序列的头尾及中间选取三个元素,再取这三个元素的中间值作为最终的枢轴元素;或者随机地从当前表中选取枢轴元素,这样做可使得最坏情况在实际排序中几乎不会发生。
在最理想的状态下,即 Partition() 可能做到最平衡的划分,得到的两个子问题的大小都不可能大于n / 2,在这种情况下,快速排序的运行速度将大大提升,此时,时间复杂度为O(nlog2n) 。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近,而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法

② 稳定性

在划分算法中,若右端区间有两个关键字相同,且均小于基准值的记录,则在交换到左端区间后,它们的相对位置会发生变化,即快速排序是一种不稳定的排序方法。

③ 适用性

快速排序算法仅适用于顺序存储的线性表。

四、选择排序

选择排序的基本思想是: 每一趟(如第 i 趟)在后面 n - i + 1( i = 1, 2, … , n - 1 )个待排序元素中选取关键字最小的元素,作为有序子序列的第 i 个元素,直到第 n - 1 趟做完,待排序元素只剩下 1 个,就不用再选了。

1. 简单选择排序

1)算法思想与实现步骤

① 简单选择排序的基本思想是:
简单选择排序通过不断选择未排序部分中的最小的元素,将其放到已排序部分的末尾,逐步构建出一个非递减有序的序列。

② 简单选择排序的实现步骤是:
a)从排序表的未排序部分 L[i…n] 找到最小元素。
b)将找到的最小元素交换到已排序部分的末尾,即 L( i ) 处,每一趟排序可以确定一个元素的最终位置。
c)标记已排序部分的边界,继续对未排序部分重复步骤 a-b 。
d)直到整个数组变为有序。

2)算法的C++代码

void SelectSort(ElemType A[], int n) {for(int i=O; i<n-1; i++){		// 一共进行n-1趟int min = i;		// 记录最小元素位置for(int j=i+1; j<n; j++){	// 在A[i…n-1]中选择最小的元素if(A[j] < A[min]) {min = j;}	// 更新最小元素位置}if(min != i) {swap(A[i], A[min]);}	// 封装的swap()函数共移动元素 3 次}
}

3)示例

4)算法的性能分析

① 时间复杂度与空间复杂度

I、空间效率:仅使用常数个辅助单元,故空间效率为 O(1) 。

II、时间效率:在简单选择排序过程中,元素移动的操作次数很少,不会超过 3(n - 1) 次,最好的情况是移动 0 次,此时对应的表已经有序;但元素间比较的次数与序列的初始状态无关,始终是 n(n - 1) / 2 次,因此时间复杂度始终是 O(n2) 。

② 稳定性

在第 i 趟找到最小元素后,和第 i 个元素交换,可能会导致第 i 个元素与其含有相同关键字元素的相对位置发生改变。例如:L = {2, 2’, 1} 经过一趟排序后 L = {1, 2’, 2}。因此,简单选择排序是一种不稳定的排序方法。

③ 适用性

简单选择排序算法适用于顺序存储和链式存储的线性表,以及关键字较少的情况。

2. 堆排序

1)了解堆的定义

① 定义1:一棵大根树(小根树) 是这样一棵树,其中每个结点的值都大于(小于)或等于其子结点(如果有子结点的话)的值。在大根树或小根树中,结点的子结点个数可以任意。

② 定义2:一个大根堆(小根堆)既是大根树(小根树)也是完全二叉树。
因为堆是完全二叉树,具有 n 个元素的堆的高度为 ⌈log2(n + 1)⌉ 。因此,如果能够在 O(height) 时间内完成插人和删除操作,那么这些操作的复杂性为 O(log2n) 。

堆的定义如下,n 个关键字序列 L [1…n] 称为堆,当且仅当该序列满足:
a)L(i) >= L(2i) 且 L(i) >= L(2i + 1) 或
b)L(i) <= L(2i) 且 L(i) <= L(2i + 1) (1 <= i <= ⌊n / 2⌋)
可以将堆视为一棵完全二叉树。

  • 满足条件 a 的堆称为大根堆(大顶堆),大根堆的最大元素存放在根结点,且其任意一个非根结点的值小于或等于其双亲结点值。
  • 满足条件 b 的堆称为小根堆(小顶堆),小根堆的定义刚好相反,根结点是最小元素。

2)大根堆的“上浮”和“下沉”

在大根堆中,上浮操作(Upward Sift 或 Bubble Up)和下沉操作(Downward Sift 或 Bubble Down)是确保堆性质(每个父结点的值大于或等于子结点的值)得以维持的重要操作。

① “上浮”操作:上浮操作用于在插入新元素后,调整堆的结构,确保大根堆的性质得以满足。
步骤:(自下而上)
a)将新插入的元素放在数组的末尾(即堆的最后一个位置)。
b)从该新元素的位置开始,检查其值是否大于其父结点的值。
c)如果大于,则与父结点交换位置。
d)重复以上步骤,直到达到根结点或堆的性质得以满足。

② “下沉”操作:下沉操作用于在删除堆顶元素(或在将堆的最后一个元素移到根结点后),调整堆的结构,确保大根堆的性质得以满足。
步骤:(自上而下)
a)将堆顶元素(通常是最大值)与最后一个元素交换位置。
b)移除最后一个元素(即原堆顶元素)。
c)从新根结点开始,检查其值与左右子结点的值。
d)若根结点小于任一子结点,则与较大的子结点交换位置。
e)重复以上步骤,直到达到叶结点或堆的性质得以满足。

3)大根堆的插入、初始化和删除操作

① 大根堆的插入:
a)添加元素:将新元素添加到数组末尾(堆的最后一个位置)。
b)上浮操作(自下而上):检查新插入元素是否满足大根堆的性质。
从新元素的位置开始,若其值大于其父结点的值,则交换两者,继续向上比较,直到满足大根堆的性质或到达根结点。
示例如下图所示:在已经建好的大根堆中加入新元素 63 。

实现这种插入策略的时间复杂性为 O(height) = O(log2n) 。

② 大根堆的删除:(通常删除堆顶元素)
a)替换根节点:将堆顶(最大值)与最后一个元素交换。
b)移除最后元素:从堆中移除最后一个元素(原堆顶)。
c)下沉操作(自上而下):从新根结点开始,进行下沉调整。
比较新根结点与其子结点,若其值小于任一子结点的值,则与较大的子结点交换,直到满足大根堆的性质。
示例如下图所示:在已经建好的大根堆中删除堆顶元素 87 。

实现这种删除策略的时间复杂性为 O(height) = O(log2n) 。

③ 大根堆的初始化:
a)创建数组:使用数组来存储堆中的元素。
b)构建堆:将无序数组转换成大根堆,通常采用“自下而上”的方法,遍历所有的非叶结点,从最后一个非叶结点开始(索引为 ⌊(n / 2)⌋ ,n 为结点总数,索引从 1 开始),依次向上调整每个结点,使其满足大根堆的性质。
c)调整结点:对每个结点调用“下沉”操作,确保其大于或等于其子结点。

数组构建堆的过程可以分为两种:
I、把数组元素逐个插入到一个空堆中,这时需要用“上浮”操作来维护大根堆的性质【为了构建这个初始的非空堆,我们需要在空堆中执行 n 次插入操作,插入操作所需的总时间为 O(nlog2n) 】;
II、更高效的做法是直接将一个无序数组转化为大根堆,再依次调整结点,这种方法称为“堆化”(Heapify),这时只需通过“下沉”操作便可完成初始化【用这种方法初始化堆的时间复杂度为 O(n) 】。
目前我们讨论的就是“堆化”的过程。

示例如下图所示:初始数组序列为 {49, 38, 65, 97, 76, 13, 27, 49’}

在大根堆的初始化过程和删除操作中,主要依赖“下沉”操作,而大根堆的插入操作中可能会使用到“上浮”操作。

4)算法思想与实现步骤

① 堆排序的基本思想是:
堆排序利用堆这种数据结构的性质,首先构建一个最大堆或最小堆,然后反复将堆顶元素(最大或最小)取出并放入有序部分。

② 堆排序的实现步骤是:
a)将待排序数组 L[1…n] 中的 n 个元素构建成一个最大堆(或最小堆)。
b)将堆顶元素与最后一个元素交换,并从堆中移除堆顶元素。
c)对剩余的元素调整为堆结构。
d)重复步骤 b 和 c,直到所有元素都有序(直到堆中仅剩一个元素为止)。

5)算法的C++代码

void BuildMaxHeap(ElemType A[],int len){for(int i=len/2; i>O; i--){		// 从i=[n/2]~1,反复调整堆HeadAdjust(A, i, len);}
}
void HeadAdjust(ElemType A [], int k, int len) {
// 函数HeadAdjust将元素k为根的子树进行调整A[O] = A[k]; 		// A[O]暂存子树的根结点for(int i=2*k; i<=len; i*=2){	// 沿key较大的子结点向下筛选if(i<len && A[i]<A[i+l]) {i++;}		// 取key较大的子结点的下标if (A[0]>=A[i]) {break;}	// 筛选结束else{A[k] = A[i];	// 将A[i]调整到双亲结点上k = i;			// 修改k值,以便继续向下筛选}}A[k] = A[O];		// 被筛选结点的值放入最终位置
}
void HeapSort(ElemType A[], int len) {BuildMaxHeap(A, len);		// 初始建堆for(int i=len; i>l; i--) {	// n-1趟的交换和建堆过程Swap(A[i], A[1]);		// 输出堆顶元素(和堆底元素交换)HeadAdjust(A, 1, i-1);	// 调整,把剩余的i-1个元素整理成堆}
}

调整的时间与树高有关,为 O(h) 。在建含 n 个元素的堆时,关键字的比较总次数不超过 4n,时间复杂度为 O(n) ,这说明可以在线性时间内将一个无序数组建成一个堆。

6)算法的性能分析

堆排序适合关键字较多的情况。例如,在 1 亿个数中选出前 100 个最大值。首先使用一个大小为 100 的数组,读入前 100 个数,建立小顶堆,而后依次读入余下的数,若小于堆顶则舍弃,否则用该数取代堆顶并重新调整堆,待数据读取完毕,堆中 100 个数即为所求。

① 时间复杂度与空间复杂度

I、空间效率:仅使用了常数个辅助单元,所以空间复杂度为 O(1) 。

II、时间效率:建堆时间为 O(n) ,之后有 n - 1 次向下调整操作, 每次调整的时间复杂度为 O(h),故在最好、最坏和平均情况下,堆排序的时间复杂度为 O(nlog2n) 。

② 稳定性

进行筛选时,有可能把后面相同关键字的元素调整到前面,所以堆排序算法是一种不稳定的排序方法。

③ 适用性

堆排序仅适用于顺序存储的线性表。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/397757.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【MySQL】详解数据库约束、聚合查询和联合查询

数据库约束 约束类型 数据库的约束类型主要包括以下几种&#xff1a; 主键约束&#xff08;Primary Key Constraint&#xff09;&#xff1a;确保表中的每一行都有唯一的标识&#xff0c;且不能为NULL。 外键约束&#xff08;Foreign Key Constraint&#xff09;&#xff1a…

5.ADC(模拟信号转数字信号)

理论 3个ADC控制器 转换&#xff1a;单次转换模式、 连续转换模式 转换时间 采样时间 12.5周期 当ADCCLK(时钟) 14MHz&#xff0c;采样时间为1.5周期&#xff0c;TcoNv(转换时间) 1.5 12.5 14 周期 1us 采样精度&#xff1a;12位/16位(212 4096) 实际电压值 (通道采…

Java面试题--JVM大厂篇之破解 JVM 性能瓶颈:实战优化策略大全

目录 引言: 正文: 1. 常见的JVM性能问题 频繁的GC导致应用暂停 内存泄漏导致的内存不足 线程争用导致的CPU利用率过高 类加载问题导致的启动时间过长 2. 优化策略大全 2.1 代码层面的优化 2.1.1 避免不必要的对象创建 2.1.2 优化数据结构的选择 2.1.3 使用并发工具…

Python爬虫:下载4K壁纸

&#x1f381;&#x1f381;创作不易&#xff0c;关注作者不迷路&#x1f380;&#x1f380; 目录 &#x1f338;完整代码 &#x1f338;分析 &#x1f381;基本思路 &#x1f381;需要的库 &#x1f381;提取图片的链接和标题 &#x1f453;寻找Cookie和User-Agent &…

突破•指针六

听说这是目录哦 数组和指针笔试题解析&#x1fae7;一维数组1&#x1f355;&#x1f355;&#x1f355;&#x1f355;&#x1f355;&#x1f355;&#x1f355; 字符数组1&#x1f354;&#x1f354;&#x1f354;&#x1f354;&#x1f354;&#x1f354;&#x1f354;2&#…

PCL 采样一致性模型介绍

采样一致性可以简单高效的检测出一些具有数学表达式的目标模型。PCL中的sample consensus模块中不仅包含各种的采样一致性估计方法,也包含一些已经编写好的数学模型,下面主要介绍一下PCL中的采样一致性模型。 1. 二维圆模型 pcl::SampleConsensusModelCircle2D< PointT …

AI学习记录 - 自注意力机制的计算流程图

画图不易&#xff0c;如果你从这个图当中得到灵感&#xff0c;大佬赏个赞 过段时间解释一下&#xff0c;为啥这样子计算&#xff0c;研究这个自注意力花了不少时间&#xff0c;网上很多讲概念&#xff0c;但是没有具体的流程图和计算方式总结…

Win11表情符号输入详细教程,一学就会!

在Win11电脑操作中&#xff0c;用户可以根据自己的需求&#xff0c;点击输入想要的表情符合。但许多新手用户不知道怎么操作才能输入&#xff1f;这时候用户按下快捷键&#xff0c;快速打开表情符号选择界面&#xff0c;然后选择需要的表情符号点击输入即可。以下系统之家小编给…

Can GPT-3 Perform Statutory Reasoning?

文章目录 题目摘要相关工作SARAGPT-3 对美国法典的了解GPT-3 在对合成法规进行简单推理时遇到困难结论 题目 GPT-3 可以进行法定推理吗&#xff1f; 论文地址&#xff1a;https://arxiv.org/abs/2302.06100 摘要 法定推理是用事实和法规进行推理的任务&#xff0c;法规是立法机…

Linux嵌入式学习——C++学习(2)

一、标识符的作用域和可见性 &#xff08;一&#xff09;作用域 1、全局作用域 在函数外部声明的变量和函数具有全局作用域。这些变量和函数在程序的任何地方都可以被访问。 2.局部作用域 在函数内部、循环体内部或条件语句内部声明的变量具有局部作用域。这些变量只能在其…

X射线物质质量衰减系数的查询计算方法

最近进行硕士毕业课题&#xff0c;需要各种各样物质的质量衰减系数&#xff08;线性衰减系数&#xff09;&#xff0c;包括高原子序数的金属物质还有一些复杂的化合物或者混合物&#xff0c;之前知道美国的XCOM &#xff1a;XCOM: Photon Cross Sections Database这个数据库可以…

仓颉语言运行时轻量化实践

杨勇勇 华为语言虚拟机实验室架构师&#xff0c;目前负责仓颉语言静态后端的开发工作 仓颉语言运行时轻量化实践 仓颉Native后端&#xff08;CJNative&#xff09;是仓颉语言的高性能、轻量化实现。这里的“轻量化”意指仓颉程序运行过程中占用系统资源&#xff08;内存、CPU等…

dll修复工具有没有免费的?排行榜Top8更新,一键修复所有dll缺失

DLL 错误是常见的系统问题&#xff0c;可能导致系统崩溃或 Windows 故障&#xff0c;这让每天使用电脑的人倍感烦恼。为了有效解决这些反复出现的问题&#xff0c;使用 DLL 修复工具显得尤为重要。对于喜欢尝试免费软件的用户&#xff0c;市面上有许多优秀的免费dll 修复工具可…

打开 Mac 触控板的三指拖移功能

对于支持力度触控的触控板&#xff0c;可以选择使用三指手势来拖移项目。 相应的设置名称会因你使用的 macOS 版本而有所不同&#xff1a; 选取苹果菜单  >“系统设置”&#xff08;或“系统偏好设置”&#xff09;。 点按“辅助功能”。 点按“指针控制”&#xff08;…

【vue3】【elementPlus】【国际化】

1.如需从0-1开始&#xff0c;请参考 https://blog.csdn.net/Timeguys/article/details/140995569 2.使用 vue-i18n 模块&#xff1a; npm i vue-i18n3.在 src 目录下创建 locales 目录&#xff0c;里面创建文件&#xff1a;en.js、zh-cn.js、index.js 语言js文件&#xff1a;…

html5宠物网站模板源码

文章目录 1.设计来源1.1 主界面1.2 主界面菜单1.3 关于我们界面1.4 宠物照片墙界面1.5 宠物博客界面1.6 宠物服务界面1.7 宠物团队界面1.8 联系我们界面 2.效果和源码2.1 源代码 源码下载万套模板&#xff0c;程序开发&#xff0c;在线开发&#xff0c;在线沟通 【博主推荐】&a…

【轻松掌握】使用Spring-AI轻松访问大模型本地化部署并搭建UI界面访问指南

文章目录 读前必看什么是Spring-AI目前已支持的对接模型本文使用Spring-AI版本构建项目选择必要的依赖配置系统变量 聊天模型API配置文件方式1-使用默认配置方式2-自定义配置配置其他参数使用示例 图像模型API配置文件方式1-使用默认配置方式2-自定义配置配置其他参数使用示例 …

开发效率翻倍攻略!大学生电脑小白管理秘籍,资料秒搜技巧大公开!C盘满了怎么办?如何快速安全的清理C盘?烦人的电脑问题?一键解决!

如何正确管理自己的第一台电脑&#xff1f;大一新生如何管理自己的电脑&#xff1f;老鸟如何追求快捷操作电脑&#xff1f; 文章目录 如何正确管理自己的第一台电脑&#xff1f;大一新生如何管理自己的电脑&#xff1f;老鸟如何追求快捷操作电脑&#xff1f;前言初级基础分区操…

2024年第八届计算生物学与生物信息学国际会议 (ICCBB 2024)即将召开!

2024 年第八届计算生物学和生物信息学国际会议&#xff08;ICCBB 2024&#xff09;将于2024年11月28 -30在日本京都召开&#xff0c;ICCBB 2024是展示理论、实验和应用计算生物学和生物信息学领域新进展和研究成果的主要论坛之一。我们相信&#xff0c;通过大家的共同努力&…

oled使用 f4软件iic 数字 汉字 小图片 HAL库

基于江科大的oled标准库进行移植 到Hal库上 本人参考了许多大佬的源码 进行更改 由于F4和F1主频不一样 由于F4主频太高 在进行软件iic时需要延时一下 才可驱动oled 本人在网上找了一个开源的us延时函数 已经添加进入 文件分享 通过百度网盘分享的文件&#xff1a;delay&#…