数据结构面试之十——排序2(归并、快速、堆排序）
题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。
十、数据结构面试之十——排序2(归并、快速、堆排序）
5. 归并排序
【算法思想】：采用分治法的算法思想，将原始数组分为A、B两个子数组，然后对A、B两个子数组继续划分为A1L,A1R，B1L,B1R四个子数组，继续划分直到数组中元素个数为1个时，即认为数组有序；然后再合并相邻的数组据可以。
核心分为3步骤：
第一，Divided，对应Divided()函数。
第二，Conquer，做相关处理。
第三，Merge，对应MergeArray()函数。
步骤示意图：
数组下标
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
元素值
9
8
7
6
5
4
3
2
1
0
Divided
1
first
mid
last
2
first
mid
last
3
first
mid
last
4
first&mid
last
Merge
5
first&mid
last
6
first
mid
last
Divided
7
first&mid
last
Merge
8
first&mid
last
Merge
9
first
mid
last
Divided
11
first
mid
last
12
first
mid
last
13
first&mid
last
Merge
14
first&mid
last
15
first
mid
last
Divided
16
first&mid
last
Merge
17
first&mid
last
Merge
18
first
mid
last
Merge
19
first
mid
last
【算法实现】：
枢轴
0
1
2
3
4
5
6
7
8
9
72
6
57
88
60
42
83
73
48
85
pivot=72
<--48
<--42
left=right
88-->
<--48
6
57
<--42
60
72
83
73
88-->
85
pivot=48
48
6
57
42
60
<--42
left=right
57-->
60
<--42
6
48
57-->
60
pivot=42
42
6
<--6
42
pivot=57
57
60
57
60
pivot=83
83
73
88-->
85
73
83
88-->
85
pivot=73
73
83
73
83
pivot=88
88
85
85
88
排序结果
6
42
48
57
60
72
73
83
85
88
【算法实现】：
template<typename T>void heapAdjust(T arr[], int i, int N){ intj; inttemp = arr[i]; //临时存储需要节点信息. j= i*2+1; //左孩子节点 while(j< N) { if(j+1< N && arr[j+1] < arr[j]) { j++; //取左右孩子中的小值. } if(arr[j]>= temp) { break; //小顶堆，如果出现孩子节点值大，则终止循环. } //找寻是否存在孩子节点的孩子节点. arr[i]= arr[j]; i= j; j= 2*i + 1; }//endwhile arr[i]= temp; //存储新的位置.} //堆排序.template<typename T>void heapSort(T arr[], int N){ //构建小顶堆，初始是凌乱的，调整后成一个小顶堆 for(int i = N-1; i >= 0; i--) { heapAdjust(arr,i/2,N-1);//比较的位置从中间开始. } for(int i = N-1; i >= 0; i--) { swap(arr[i],arr[0]); heapAdjust(arr,0,i); //终止的大小为i,每次只调整根节点即可。 }}
- 1楼hxx00昨天 10:30
- 解释得很详细 顶一个