文档章节

常用高级排序算法

穿
 穿靴子的猫LJL
发布于 2015/10/13 15:02
字数 1015
阅读 107
收藏 8

首先初始化了一个MAX大小的数组,用乱序函数将数组打乱,用于测试各个排序函数,先附上要测试的几个基础排序函数,后面附上乱序函数和主调度函数。代码就那么几行,只是注释的思乱占了比较多的行数

快速排序

//快速排序,思想的重点是 递归+分组(分治)+前后交叉操作
void quickSort(int *array, int low, int hight)
{
	//判断是否满足条件
	if (hight <= low)	//如果只有一个元素或者前后错位了,就不用排序了,一个元素就是成序的
		return;
	//满足排序条件,进入排序部分
	int i = low, j = hight;	//定义函数内的临时变量为low和hight的副本,避免修改low和 hight,后面还要使用
	int temp = array[low];
	//对整个序列进行一次筛选,以目标值为分割点,只有当i<j时表示遍历没有完成,需要继续遍历
	while (i < j){
		while (i<j && array[j]>temp){
			j--;
		}
		if (i < j){
			array[i++] = array[j];
		}
		while (i < j && array[i] < temp){
			i++;
		}
		if (i < j){
			array[j--] = array[i];
		}
	}
	//循环跳出,证明i=j,遍历相遇,一轮筛选完成,将目标数放在中间
	array[i] = temp;
	//递归部分
		//将前半部分交给快排函数
	quickSort(array, low, i - 1);
		//将后半部分交给快拍函数
	quickSort(array, i + 1, hight);
}

shell排序(基于插入排序)

//shell排序(希尔排序)
void shellSort(int *array, int size, int d)
{
	//循环1 控制步长的循环
	for (int increment = d; increment > 0; increment /= 2){
		//循环2 属于插入排序内容,控制遍历次步长可以访问到的元素
		for (int i = increment; i < size; i += increment){
			int temp = array[i];
			int j = i - increment;
			//循环3 属于插入排序内容,赋值寻找目前元素可以插入的位置
			while (j >= 0 && array[j]>temp){
				array[j + increment] = array[j];
				j -= increment;
			}
			array[j + increment] = temp;
		}
	}
}

shell排序(基于选择排序)

相比于基于插入排序实现的shell排序,这个看起来循环多,实现的时候逻辑也不简单于基于插入排序,

不知道是我写的问题,还是问题的本身就是这样的,求指教

void shellSort2(int *array, int size, int d)
{
	//循环1,控制步长变化,直到步长为1也执行后结束
	for (int increment = d; increment > 0; increment /= 2){
		//循环2,找出每组的开头
		for (int k = 0; k < increment; k++){
			//循环3,属于选择排序范围了,对上面提供的开头的组内元素做选择排序
			for (int i = k; i < size - 1; i += increment){
				int tempIndex = i;
				//循环4,属于选择排序
				for (int j = i + increment; j < size; j += increment){
					if (array[j] < array[tempIndex]){
						tempIndex = j;
					}
				}
				if (tempIndex != i){
					int temp = array[i];
					array[i] = array[tempIndex];
					array[tempIndex] = temp;
				}
			}
		}
	}
}

辅助的操作函数,包括 乱序函数,打印数组函数,交换元素值得函数

//交换函数
void swap(int *a, int *b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
//乱序函数,通过从后往前遍历数组,使得当前索引的值与随机一个比它索引小的元素交换
void shuffle(int *array, int size)
{
	srand((unsigned int)time(NULL));
	for (int i = size - 1; i > 0; i--){
		int index = rand() % i;
		swap(&array[i], &array[index]);
	}
}
//打印数组函数
void printArray(int *array, int size)
{
	for (int i = 0; i < size; i++){
		printf("%d\t",array[i]);
	}
}

主函数,负责测试各个排序函数

int main()
{
	//定义并初始化数组
	int array[MAX] = { 0 };
	for (int i = 0; i < MAX; i++){
		array[i] = i;
	}
	//对数组数据进行乱序
	shuffle(array, MAX);
	//打印乱序后的数组
	printArray(array, MAX);
	//测试各个排序的效果
	/*printf("\n快速排序后\n");
	quickSort(array, 0, MAX - 1);
	printArray(array, MAX);*/
	printf("\nshell排序后\n");
	shellSort(array, MAX, MAX / 2);
	printArray(array, MAX);
	return 0;
}


© 著作权归作者所有

共有 人打赏支持
穿
粉丝 3
博文 21
码字总数 13795
作品 0
海淀
私信 提问
通用双向链表(一)——接口设计

通用双向链表的特点 链表每个节点占用一块内存。频繁增删,双向链表容易造成内存碎片 双向链表增删数据,只需要修改前后元素的指针 某些高级排序算法在链表中表现不好,使用基本的排序算法即...

地狱的烈火
2014/04/08
0
0
前端笔试&面试爬坑系列---算法

终于来了,算法相关的。 其实个人理解,前端岗位对于算法的要求与其他IT岗位相比,是低得多的。 但是小白我经历了如蚂蚁金服、网易这样的大厂教做人之后,还是觉得,对于一些基本算法、思想的...

Vincent Ko
08/15
0
0
国内大型互联网公司招聘高级推荐算法研究员 高级计算广告研究员 社交网络高级算法研究员[l猎头]

高级推荐算法研究员 1. 参与人人网产品部门数据挖掘,个性化推荐,或信息传播等方面的算法研究; 2. 研究,设计算法在处理大规模数据时的模型,并实现原型;和开发人员协调,沟通算法在处理大...

melodyzym
2012/05/05
604
5
排序算法-09-冒泡排序(Bubble Sort)

Basics Sorting - 基础排序算法 算法复习——排序 算法分析 时间复杂度-执行时间(比较和交换次数) 空间复杂度-所消耗的额外内存空间 使用小堆栈或表 使用链表或指针、数组索引来代表数据 排序...

Corwien
2016/06/17
41
0
【北京】知名互联网公司诚聘数据挖掘研究员&语音识别高级研究员

请在投递简历时,邮件标题为“[姓名]-应聘-[职位名称]”。职位名称选用下述职位说 明!!投递信箱为boxin@sillinfo.com 如有任何疑问可与我联系,以下为具体联系方式: TEL: 010-68158195-80...

jbxyk
2012/04/17
484
5

没有更多内容

加载失败,请刷新页面

加载更多

Web安全之XSS攻击与防御小结

Web安全之XSS攻防 1. XSS的定义 跨站脚本攻击(Cross Site Scripting),缩写为XSS。恶意攻击者往Web页面里插入恶意Script代码,当用户浏览该页之时,嵌入其中Web里面的Script代码会被执行,从...

前端小攻略
20分钟前
1
0
JavaScript中的继承及实现代码

JS虽然不像是JAVA那种强类型的语言,但也有着与JAVA类型的继承属性,那么JS中的继承是如何实现的呢? 一、构造函数继承 在构造函数中,同样属于两个新创建的函数,也是不相等的 function Fn...

peakedness丶
23分钟前
1
0
记一次面试最常见的10个Redis"刁难"问题

导读:在程序员面试过程中Redis相关的知识是常被问到的话题。作为一名在互联网技术行业打击过成百上千名的资深技术面试官,本文作者总结了面试过程中经常问到的问题。十分值得一读。 Redis在...

小刀爱编程
36分钟前
13
0
TiDB Lab 诞生记 | TiDB Hackathon 优秀项目分享

本文由红凤凰粉凤凰粉红凤凰队的成员主笔,他们的项目 TiDB Lab 在本届 TiDB Hackathon 2018 中获得了二等奖。TiDB Lab 为 TiDB 培训体系增加了一个可以动态观测 TiDB / TiKV / PD 细节的动画...

TiDB
49分钟前
4
0
当区块链遇到零知识证明

本文由云+社区发表 当区块链遇到零知识证明 什么是零知识证明 零知识证明的官方定义是能够在不向验证者任何有用的信息的情况下,使验证者相信某个论断是正确的。这个定义有点抽象,下面笔者举...

腾讯云加社区
58分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部