文档章节

常用高级排序算法

穿
 穿靴子的猫LJL
发布于 2015/10/13 15:02
字数 1015
阅读 106
收藏 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
博文 20
码字总数 13498
作品 0
海淀
前端笔试&面试爬坑系列---算法

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

Vincent Ko
08/15
0
0
通用双向链表(一)——接口设计

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

地狱的烈火
2014/04/08
0
0
排序算法-09-冒泡排序(Bubble Sort)

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

Corwien
2016/06/17
41
0
Java Web学习计划

--- 本月为入门阶段,从零开始,一步一步的做出一个实用的网站。 深入学习Java语言,初步掌握前端技术,使用JSP和MySQL完成一个简单的网站 第1周 Java高级编程学习目标:
1.深入了解JDK环境...

SVD
2016/12/01
55
0
图书馆刘大妈除了要帮我找对象,还教我排序算法

在图书馆偶遇 快速排序算法 一次关于排序的偶遇 今天,在图书馆发生了一件事。 图书馆书架 新来的志愿者小王被安排将归还的书整理回书架,初次被委派工作的小王瞬间充满热情。然而。。。 面对...

超级数学建模
03/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Memcached启动参数详解

memcached -d -m 1024 -l 192.168.100.101 -p 11211 -P /tmp/memcached.pid -c 1024 -f 1.25 -n 80 -t 16 运行参数描述 -d:以守护(daemon)进程方式启动; -u:是运行Memcache的用户,例如 ......

月下狼
24分钟前
0
0
xgboost-kaggle

https://www.kaggle.com/dansbecker/xgboost This tutorial is part of the Learn Machine Learning series. In this step, you will learn how to build and optimize models with the powe......

tantexian
25分钟前
0
0
nginx学习八 代理服务

最常用的语法 proxy_pass Syntax: proxy_pass URL;Default: --Context:location.if in location,limit_exception 反向代理 例:/etc/nginx/conf.d/default.conf 反向代理(代理服务端)......

Romanceling
32分钟前
0
0
npm ERR! Unexpected end of JSON ...

npm install 报错: npm ERR! Unexpected end of JSON input while parsing near '..."^2.8.14"},"_hasShrin' npm ERR! A complete log of this run can be found in: ... 打开终端 命令: 第......

大_侠
36分钟前
0
0
Android中的设计模式之责任链模式

参考 《设计模式:可复用面向对象软件的基础 》5.1 Chain of responsibility 职责链 对象行为型模式 《Android源码设计模式解析与实战》第9章 使编程更有灵活性--责任链模式 意图 使多个对象...

newtrek
39分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部