数据结构排序系列之选择排序(三)
1.选择排序
选择排序有直接选择排序和堆排序。基本思想:每一趟在待排序的记录中选出关键字最小的元素,依次存放在已排好序的序列的最后。直到所有元素都好排好序为止。
1.1.直接选择排序
算法思想:
每次从待排序的无序区中选出关键字最小的元素,将该元素与该无序区中的第一个元素交换位置。初始时,从[0…n-1]选出一个关键字最小的元素,与R[0]交换位置。第二趟排序时,从[1…n-1]选出一个关键字最小的元素,与R[1]交换位置,此时R[0…1]为有序区,依次类推,进行n-1趟后,R[0…n-1]中的元素按递增有序。
算法实现:
#include <stdio.h>
void selectSort(int R[],int n){
// 进行n-1趟排序
for(int i = 0;i < n-1;i++){
int k = i;
// 在R[i..n-1]区间选出关键字最小的元素
for(int j = i;j < n;j++){ if(R[k] > R[j]){ k = j; }
}
// 将最小的元素与R[i]进行交换
if(i != k){ int temp = R[i]; R[i] = R[k]; R[k] = temp;
}
}
}
int main(){
int data[] = {38,33,65,82,76,38,24,11};
selectSort(data,8);
for(int i = 0; i < 8;i++){
printf("%d ",data[i]);
}
printf("\n");
return 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
1.2. 堆排序
堆排序是一个种树形选择排序,算法思想:
在排序过程中,将数组R[0…n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和该子结点之间的内存关系,在当前无序区中选择关键字最大(或最小)的元素。
堆排序正是利用大根堆(或小根堆)来选择当前无序区中关键字最大(或最小)的元素来实现排序的。每一趟排序就是将当前无序区调整为一个大根堆,选择关键字最大的堆顶元素和无序区中最后一个元素进行交换。通过不断将剩余的无序区调整为一个大根堆,然后再将堆顶元素与无序区中最后一个元素进行交换来完成排序的。
那么堆排序的关键就是构造堆,构造堆的过程:
将待排序的文件的关键字存储在一个数组R[0…n-1]中(存储在R[1…n])更好理解,将R看成一棵完全二叉树的顺序存储结构,每个结点代表一个元素。那么任意结点Ri的左孩子是R[2i+1](如果是R[1…n],那么左孩子就是R[2i]),右孩子是R[2i+2](如果是R[1…n],那么右孩子就是R[2i+1]),R[i]的双亲结点就是R[i/2]。构造大根堆的过程:假设完全二叉树的某一个结点i的左子树和右子树已是堆,那么将R[2i+1]和R[2i+2]中的较大者与R[i]比较,如果R[i]较小,则交换,交换后,就有可能破坏下一级的堆,因此继续采取同样的方法构造下一级的堆,直至完全二叉树中以结点i为根的子树成堆为止,当无序区调整为大根堆时,堆顶元素就是无序区中关键字最大的元素,将其与无序区中最后一个元素进行交换。重复构造堆和进行交换,经过n-1趟后就可以排好序。
参考:
-
完全二叉树的顺序存储结构就是从树根开始自上到下,每层从左到右地给该树中每个结点进行编号(假定从0开始),就能够得到一个反映整个二叉树结构的线性序列。
-
堆:n个元素的关键字序列k1,k2,…,kn称为堆,那么它必须满足以下条件:ki≤k2i且ki≤k2i+1,或ki≥k2i且ki≥k2i+1(也就是双亲结点要么都小于左右子结点,要么都大于左右子结点,前者叫小根堆(如15,27,44,76,38 ,59),后者叫大根堆(如76,38,59,27,15,44))
算法实现:
#include <stdio.h>
void check(int R[],int i,int l){
// i当前结点,l为无序区的长度
int j = 2*i +1; // R[i]的左孩子
if((j+1) < l && R[j] < R[j+1]){
j++;
}
// R[i]与左右孩子结点中较大者进行比较
if(j < l && R[i] < R[j]){
int tmp = R[i];
R[i] = R[j];
R[j] = tmp;
check(R,j,l);
}
}
void heapSort(int R[],int n){ // 堆排序就是不断建堆的过程
int temp = n;
while(temp != 0){
// 恰好temp/2的结点的子树就是R的最后的元素
for(int i = temp/2-1;i<temp/2 && i >= 0; i--){ // 检查是否是堆,不是就调整,直到无序区变为大根堆 check(R,i,temp);
}
temp--;
// 堆顶元素与无序区最后一个元素交换
int t = R[temp];
R[temp] = R[0];
R[0] = t;
}
}
int main(){
int data[] = {45,36,72,18,53,31,48,36};
heapSort(data,8);
for(int i =0 ; i < 8; i++){
printf("%d ",data[i]);
}
printf("\n");
return 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
1.3.总结
在直接选择排序中存在着不相邻元素之间的交换,因而可能会改变具有相同关键字的前后位置,因此直接选择排序算法是不稳定的。堆排序也是不稳定的。在直接排序序中,为了从n个关键字中选择出最小的,需要进行n-1次的比较,然后再在n-1个关键字找出次小的关键字,需要进行n-2次比较,实际上,在进行n-2比较中,有许多比较都已经做过只是没有记录下来,堆排序刚好弥补了这一点的不足。
文章来源: blog.csdn.net,作者:WongKyunban,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/weixin_40763897/article/details/106010189
- 点赞
- 收藏
- 关注作者
评论(0)