文档章节

常用高级排序算法

穿
 穿靴子的猫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
涨姿势,图文带你了解 8 大排序算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 常见的内部排序算法有...

Java架构
07/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

原型模式

1、原型模式-定义 用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象 克隆(浅度克隆->拷贝值类型或者引用,深度克隆->创建新的对象,开辟新的内存) 例如客户端知道抽象Pro...

阿元
48分钟前
5
0
awk命令扩展使用操作

awk 中使用外部shell变量 示例1 [root@centos01 t1022]# A=888[root@centos01 t1022]# echo "" | awk -v GET_A=$A '{print GET_A}'888[root@centos01 t1022]# echo "aaaaaaaaaaaaa" | aw......

野雪球
今天
10
0
深入解析MySQL视图VIEW

Q:什么是视图?视图是干什么用的? A:视图(view)是一种虚拟存在的表,是一个逻辑表,本身并不包含数据。作为一个select语句保存在数据字典中的。   通过视图,可以展现基表的部分数据;...

IT--小哥
今天
13
0
虚拟机学习之二:垃圾收集器和内存分配策略

1.对象是否可回收 1.1引用计数算法 引用计数算法:给对象中添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时候计数器值为0的对象就是不可能...

贾峰uk
今天
10
0
smart-doc功能使用介绍

smart-doc从8月份底开始开源发布到目前为止已经迭代了几个版本。在这里非常感谢那些敢于用smart-doc去做尝试并积极提出建议的社区用户。因此决定在本博客中重要说明下smart-doc的功能,包括使...

上官胡闹
昨天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部