文档章节

常用基础排序算法

穿
 穿靴子的猫LJL
发布于 2015/10/13 14:52
字数 1592
阅读 14
收藏 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
8个常用算法的超常剖析

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

gitchat
2017/11/30
0
0
程序员?这些面试题你能答对几个?

  三人行必有我师,人生是需要不断学习的,在这里我们相遇就是缘分,希望各位可以看完这篇文章,也欢迎大家在下面留言讨论,天冷了,也动动手指转发收藏一下,谢谢大家!   一、数据结构...

java分享
2017/12/03
0
0
Java实现几种常见排序方法(下)

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

晨曦之光
2012/03/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

C++基础知识

链接:https://zhuanlan.zhihu.com/p/38399566 本文主要提一下以下三个区别: 引用必须初始化,而指针可以不初始化。 我们在定义一个引用的时候必须为其指定一个初始值,但是指针却不需要。 ...

悲催的古灵武士
18分钟前
0
0
Oracle备份脚本,保留10天数据

@echo off echo 删除10天前的备分文件和日志forfiles /p "D:\oracleback\backfile" /m *.dmp /d -10 /c "cmd /c del @path" forfiles /p "D:\oracleback\backfile" /m *.log /d -10......

lyle_luo
20分钟前
0
0
window版mysql备份数据

@echo off ::title name title db_backup ::color is green COLOR 2 ::defined value set yy=%date:~0,4% set mm=%date:~5,2% set dd=%date:~8,2% if /i %time:~0,2% lss 10 set hh=0%time:~......

恋码之子
22分钟前
0
0
hashmap嘿嘿嘿

1、jdk1.7 数组加链表 2、链表存放数据:hashcode相同,Entry{key:键 value:值 next:下一个节点} 3、取模算法,计算出存放数组的下标 int index = key.hashCode()%tables.length;...

熊猫你好
35分钟前
0
0
ca证书创建和docker-api证书设置

openssl genrsa -aes256 -out ca-key.pem 4096 // 这一步的密码千万不能忘记,下面要用到 openssl req -new -x509 -days 3650 -key ca-key.pem -sha256 -out ca.pem# 国家:CN# 省:.# 市......

chenbaojun
35分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部