常用高级排序算法
常用高级排序算法
穿靴子的猫LJL 发表于3年前
常用高级排序算法
  • 发表于 3年前
  • 阅读 105
  • 收藏 8
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

摘要: 本文整理一下自己回顾排序算法时候的整理,包括, 快速排序,shell排序(希尔排序),shell排序写了两个版本,基于插入排序的和基于选择排序的,归并排序我也写了,但是总是测试出问题,没有找到问题所在,就不贴出来了,求指教

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