常用基础排序算法
常用基础排序算法
穿靴子的猫LJL 发表于2年前
常用基础排序算法
  • 发表于 2年前
  • 阅读 14
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

摘要: 本文整理自己回顾,冒泡排序,选择排序,插入排序,二分插入排序,的程序,顺便带上二分查找的循环版本和递归版本

首先初始化了一个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
博文 11
码字总数 13498
×
穿靴子的猫LJL
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: