文档章节

常用基础排序算法

穿
 穿靴子的猫LJL
发布于 2015/10/13 14:52
字数 1592
阅读 15
收藏 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;
}


© 著作权归作者所有

共有 人打赏支持
穿
粉丝 3
博文 20
码字总数 13498
作品 0
海淀
私信 提问
排序算法-09-冒泡排序(Bubble Sort)

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

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

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

waffle930
2016/09/22
6
0
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

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

yinwenjie
2017/06/06
0
0
Java实现几种常见排序方法(下)

插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。其具体步骤参见代码及注释。 /** 插入排序<br/> <ul> <li>从第一个元素开始,该元...

晨曦之光
2012/03/09
0
0
算法与数据结构(二):排序篇-O(n^2)算法:选择 & 插入算法优化

排序基础 O(n^2)的算法虽然简单,但也实用!让我们从最简单的基础排序算法开始,打开我们的算法大门! 排序算法 O(n^2)的排序算法 最优的时间复杂度为O(nlogn)的算法。 为什么要学习O(n^2)的...

天涯明月笙
2017/09/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Hive的三种Join方式

Hive中就是把Map,Reduce的Join拿过来,通过SQL来表示。 参考链接:https://cwiki.apache.org/confluence/display/Hive/LanguageManual+Joins Common/Shuffle/Reduce Join Reduce Join在Hiv......

GordonNemo
22分钟前
1
0
Spark学习记录(三)核心API模块介绍

spark ------------- 基于hadoop的mr,扩展MR模型高效使用MR模型,内存型集群计算,提高app处理速度。 spark特点 ------------- 速度:在内存中存储中间结果。 支持多种语言。Scala、Java、P...

我爱春天的毛毛雨
27分钟前
1
0
PHP5、PHP7安装

11月13日任务 11.10/11.11/11.12 安装PHP5 11.13 安装PHP7 PHP官网www.php.net 当前主流版本为5.6/7.1 cd /usr/local/src/ wget http://cn2.php.net/distributions/php-5.6.32.tar.bz2 tar z......

zgxlinux
28分钟前
1
0
React 项目结构和组件命名之道

摘要: > * 原文地址:[structuring projects and naming components in react](https://hackernoon.com/structuring-projects-and-naming-components-in-react-1261b6e18d76) > * 原文作者:......

阿里云官方博客
28分钟前
3
0
无维护地稳定运行了8 年的 Hyperic HQ

最近在诊断一个系统意外停机时, 发现一个8年前部署部署的Hypeirc HQ 4.2,已经免维护,稳定运行了8年多。提供了及时的诊断信息。单击右下角的蓝色泡泡,可显示报警信息。

MartinKing
43分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部