文档章节

常用基础排序算法

穿
 穿靴子的猫LJL
发布于 2015/10/13 14:52
字数 1592
阅读 23
收藏 0

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

冒泡排序

//冒泡排序
void bubbleSort(int *array, int size)
{
	//循环1 从后向前逐个缩短比较范围,因为后面是逐个成序的
	for (int i = size - 1; i > 0; i--){
		int flag = 1;//定义标志变量,确定当一次遍历完成时候发生过交换
		//循环2 逐个遍历当前无序序列
		for (int j = 0; j < i; j++){
			//如果满足交换条件,则交换
			if (array[j]>array[j + 1]){
				swap(&array[j], &array[j + 1]);
				flag = 0;//由于发生了交换,所以标志变量置为0
			}
		}
		if (flag){//判断标志变量的值,如果此判断可以通过,则证明当遍历玩整个无序部分都没有发生一次交换,
			break;//证明整个序列都已经成序,直接跳出循环
		}
	}
}

选择排序

//选择排序
void selectSort(int *array, int size)
{
	//循环1 用于控制遍历最小值坐标,每次首先以为当前值最小,和后面所有元素开始比较
	for (int i = 0; i < size-1; i++){
		int index = i;//存储当前最小值的索引,
		//这样只在最后需要交换的时候发生一次交换,避免没有必要的交换,加快程序执行
		//循环2 用于控制遍历后面没有成序的部分和最小值比较
		for (int j = i + 1; j < size; j++){
			if (array[index]>array[j]){
				index = j;
			}
		}
		//如果最小值的索引改变了,则交换
		if (index != i){
			swap(&array[index],&array[i]);
		}
	}
}

插入排序

//插入排序
void insertSort(int *array, int size)
{
	//由于第0个元素就一个,所以是成序的,从第1个开始认为是不成序的,和前面程序部分比较
	//循环1 控制遍历后面的不成序的序列
	for (int i = 1; i < size; i++){
		int temp = array[i];//记录当前拿出来比较的值,它的位置可能被别人填充,所以记录下来
		int j = 0;
		//循环2 控制遍历从目标数前一个向前遍历成序序列,寻找目标数可插入的位置
		for (j = i - 1; j >= 0 && array[j]>temp; j--){
				array[j + 1] = array[j];
		}
		if (j!= i - 1){//当j!=i-1说明上面循环的条件进入过,执行过,所以位置需要改变
			array[j+1] = temp;//切记这里是j+1,原因是j的位置不满足条件退出,所以插入位置应该是j+1
		}
	}
}

二分插入排序

//二分插入排序,原理和插入排序相同,就是在找插入位置的时候使用了二分查找
void binaryInsertSort(int *array, int size)
{
	for (int i = 1; i < size; i++){
		int temp = array[i];
		int left = 0;
		int right = i - 1;
		//二分查找部分,这样比简单的插入排序效率更高
		while (left <= right){
			int mid = (left + right) / 2;
			if (array[mid] < temp){
				left = mid+1;
			}
			else{
				right = mid - 1;
			}
		}
		int j = 0;
		for (j = i - 1; j >= left; j--){
			array[j + 1] = array[j];
		}
		if (j != i - 1){
			array[j + 1] = temp;
		}
	}
}

二分查找循环版

//二分查找,循环版
void binarySearch(int *array, int des, int size)
{
	int left = 0;
	int right = size - 1;//这里的size是数组长度,要访问最后一个元素,就样长度减一
	int mid = 0;
	//当left和right没有错过,则证明查找范围合理,继续查找
	while (left <= right){
		//每次开始循环,都要重新确认中间位置
		mid = (left + right) / 2;
		//如果中间位置就是目标值,则找到了,跳出循环
		if (array[mid] == des){
			break;
		}
		//如果中间值大于目标,则在前半部分寻找,寻找上限编程mid-1
		if (array[mid] > des){
			right = mid - 1;
		}
		//反之,在后半部分寻找,寻找的下限变成mid+1
		else{
			left = mid + 1;
		}
	}
	//如果循环跳出的时候,还满足left<=right,则证明是因为找到了目标数,所以跳出,所以此时返回目标数索引
	if (left <= right){
		printf("\n查找成功,在数组的%d号位置\n",mid);
	}
	//反之,查找失败
	else{
		printf("\n查找失败\n");
	}
}

二分查找递归版

//递归版二分查找
int recursionBinarySearch(int *array, int left, int right, int des)
{
	//判断left和right没有错位,则查找继续
	if (left <= right){
		//确定中间位置
		int mid = (left + right) / 2;
		//判断中间位置是否是目标值,若是则返回
		if (array[mid] == des){
			return mid;
		}
		//如果中间值大于目标值,在前半部分继续寻找
		else if (array[mid] > des){
			return recursionBinarySearch(array, left, mid - 1, des);
		}
		//如果中间位置小于目标值,在后半部分寻找
		else if (array[mid] < des){
			return recursionBinarySearch(array, mid + 1, right, des);
		}
		//如果这些情况都不是,则是不合法的值,返回-1表示没找到
		else{
			return -1;
		}
	}
	//若left和right已经错过,则证明没有找到
	else{
		return -1;
	}
}

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

//交换函数
void swap(int *a, int *b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
//乱序算法,从后向前遍历数组,让目前位置数和小于它的任意索引位置交换,循环完成即完成简单的乱序
void shuffle(int *array, int size)
{
	srand((unsigned int)time(NULL));
	int index = 0;
	for (int i = size-1; i >0; i--){
		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]);
	}
}

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

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 100

int main()
{
	//定义并初始化数组
	int array[MAX] = { 0 };
	for (int i = 0; i < MAX; i++){
		array[i] = i;
	}
	printf("乱序数组后\n");
	shuffle(array, MAX);
	printArray(array, MAX);
	/*printf("\n冒泡排序后\n");
	bubbleSort(array, MAX);
	printArray(array, MAX);*/
	/*printf("\n选择排序后\n");
	selectSort(array, MAX);
	printArray(array, MAX);*/
	/*printf("\n插入排序后\n");
	insertSort(array, MAX);
	printArray(array, MAX);*/
	printf("\n二分插入排序后\n");
	binaryInsertSort(array, MAX);
	printArray(array, MAX);
	printf("\n二分查找 1 测试\n");
	binarySearch(array, 1, MAX);
	printf("\n递归版二分查找 1 测试\n");
	int index=recursionBinarySearch(array, 0, MAX - 1, 1);
	printf("\n查找成功,在数组的%d号位置\n", index);
	return 0;
}


© 著作权归作者所有

穿
粉丝 4
博文 21
码字总数 13795
作品 0
海淀
私信 提问
排序算法-09-冒泡排序(Bubble Sort)

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

Corwien
2016/06/17
76
0
常用排序算法(Java实现)

计算机最基础的几个排序算法,在笔试面试过程中经常会被问到,解编程题时也经常会被用到。 Ⅰ.直接插入排序 Ⅱ.希尔排序: Ⅲ.冒泡排序: Ⅳ.快速排序: Ⅴ.直接选择排序: Ⅵ.堆排序 Ⅶ.二路...

waffle930
2016/09/22
12
0
排序算法——冒泡排序VS插入排序

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq_26545305/article/details/87988991 一、概述 最经典、最常用的排序算法有:冒泡排序、插入排序、选择排序...

LemmonTreelss
03/04
0
0
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

1、概述 在之前的一篇文章《线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)》中,我们使用了fork/join框架提高归并排序的性 能。那篇文章发布后,有的读者联系我,觉得单就归...

yinwenjie
2017/06/06
0
0
8个常用算法的超常剖析

本文来自作者 jack 在 GitChat 上分享「最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析」,「阅读原文」查看交流实录 「文末高能」 「更多同类话题」 「查看全部话题」 编辑 | ...

gitchat
2017/11/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 如果是个帅小伙你愿意和他出去吗

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 小小编辑推荐:《Ghost 》游戏《死亡搁浅》原声 《Ghost 》游戏(《死亡搁浅》原声) - Au/Ra / Alan Walker 手机党少年们想听歌,请使劲儿戳...

小小编辑
今天
193
7
java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
今天
6
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
5
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
16
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部