数据结构排序系列之选择排序(三)

举报
yd_221104950 发表于 2020/12/03 00:57:18 2020/12/03
【摘要】 1.选择排序 选择排序有直接选择排序和堆排序。基本思想:每一趟在待排序的记录中选出关键字最小的元素,依次存放在已排好序的序列的最后。直到所有元素都好排好序为止。 1.1.直接选择排序 算法思想: 每次从待排序的无序区中选出关键字最小的元素,将该元素与该无序区中的第一个元素交换位置。初始时,从[0…n-1]选出一个关键字最小的元素,与R[0]交换位置。第二趟排序时,...

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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。