排序算法-----快速排序(非递归实现)

这篇具有很好参考价值的文章主要介绍了排序算法-----快速排序(非递归实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言

快速排序

 基本思路

 非递归代码实现

算法分析

空间复杂度

时间复杂度

稳定性


前言

        很久没跟新数据结构与算法这一栏了,因为数据结构与算法基本上都发布完了,哈哈,那今天我就把前面排序算法那一块的快速排序完善一下,前面只发布了快速排序递归算法,那这一次就去用非递归来去实现。(递归算法:排序算法-----快速排序(递归)_快排递归_Gretel Tade的博客-CSDN博客)

快速排序

 快速排序(Quicksort),计算机科学词汇,适用领域Pascal,C++等语言,是对冒泡排序算法的一种改进。

        快速排序采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素pivot,利用pivot将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列。

 基本思路

现在给定一个数组初始 [25,24,6,65,11,43,22,51] ,然后进行快速排序

 第一步,先选取一个参考数字temp,一般选取第一个即temp=25,然后标记最左边和最右边数字的位置分别为i, j

 25        24        6        64        11        43        22        51

  i                                                                                 j

temp

 第二步,先去向左移动j 的位置,当j指向的数字小于temp时候,就停止移动,然后开始向右移动i 

当i 移动到比temp要大的数字时,停止移动,此时将i 和 j 指向的数字进行交换,如下所示:

 25        24        6        64        11        43        22        51

temp                             i                                   j

交换后:

 25        24        6        22        11        43        65       51

temp                             i                                   j

 第三步,此时,开始接着移动 j,当j 移动到比temp要小的数字的时候,停止移动, 如下所示:

 25        24        6        22        11        43        65       51

temp                             i           j

 然后开始移动i ,当i 移动到与j 相遇的位置时,i停止移动(如果i 移动到比temp要大的数字的时候就执行上面的第二步,i与j 进行数字交换)

 25        24        6        22        11        43        65       51

temp                                        i,j

第四步,此时,i与j指向的数字与temp指向的数字进行数字交换

 11        24        6        22        25        43        65       51

temp                                        i,j

这时候我们会发现,此时i和j指向的数字的位置,左边的都比这个数字要小,右边的都比这个数字要大,于是我们就可以去进入到递归,分别对左边和右边的数字进行以上步骤的递归,最后两边的数字都会被排好序。

动态图

排序算法-----快速排序(非递归实现),数据结构与算法,排序算法,数据结构,算法,c语言,c++

 非递归代码实现

#include<stdio.h>
#include<stdlib.h>
//每一趟排序
int sort(int* arr, int left, int right) {
	int i = left;
	int j = right;
	int temp = arr[left];
	while (i != j) {
		while (temp <= arr[j] && i < j)//j左移
			j--;
		while (temp >= arr[i] && i < j)//i向右移
			i++;
		if (i < j) {//i与j都停止移动的时候,交换数字
			int t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
		}
	}
	//此时i与j相遇,进行数字交换
	arr[left] = arr[i];
	arr[i] = temp;
	
	return i;//返回这个交汇点
}

void quick_sort(int* arr, int left, int right) {
	int* stack = (int*)malloc(sizeof(int) * right);//创建一个数组栈
	for (int i = 0; i < right; i++)
		stack[i] = -1;//初始化为-1
	int count = 0;//当前栈数据的个数
	if (left < right) {//入栈
		stack[count++] = left;
		stack[count++] = right;
	}
	while (count) {//当栈为非空的时候
		//出栈操作
		int r_pop = stack[count-1];
		int l_pop = stack[count-2];
		stack[count - 1] = stack[count - 2] = -1;//出栈后,清空已出栈数据,设置为-1
		count -= 2;
		int i = sort(arr, l_pop, r_pop);
		//如果这个交汇点前面数据的下标比当前最左边的数据下标要大的话,就入栈
		if (l_pop < i - 1) {
			stack[count++] = l_pop;
			stack[count++] = i - 1;
		}
		//如果这个交汇点后面一个数据的下标比当前最右边数据的下标要小的话,入栈
		if (r_pop > i + 1) {
			stack[count++] = i + 1;
			stack[count++] = r_pop;
		}
	}
	//释放空间
	free(stack);
	stack = NULL;
}


int main() {
	int array[8] = { 25,24,6,65,11,43,22,51 };
	printf("排序前:");
	for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
		printf("%d ", array[i]);
	}
	printf("\n排序后:");
	quick_sort(array, 0, sizeof(array) / sizeof(int) - 1);
	for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
		printf("%d ", array[i]);
	}
}

运行结果:排序算法-----快速排序(非递归实现),数据结构与算法,排序算法,数据结构,算法,c语言,c++

算法分析

空间复杂度

快速排序算法没有涉及到空间的开辟,使用的空间是原数组空间,空间复杂度为O(1)

时间复杂度

快速排序之所以比较快,是因为与冒泡排序相比,每次的交换时跳跃式的,每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样整体交换次数和比较次数就少很多, 故排序速度就提高了许多,当然如果是最坏的情况下时间复杂度还是为O(n^2),其平均的时间复杂度为 O(nlog2​n)

稳定性

 俗话说得好:有得必有失。快速排序虽然排序速度快了很多,但是其缺牺牲了稳定性,当出现相同大小元素的时候,相同大小元素的相对位置会发生改变,每次递归都会发生变化,这就导致了快速排序的稳定性不好,这是因为快速排序改变了交换的规则,使用跳跃式交换,没有进行数字大小的一一比较,故快速排序是不稳定的,所以选择排序算法的时候要慎重选择,充分考虑到稳定性

以上就是本期的全部内容了,喜欢的话给个赞吧!

分享一张壁纸: 排序算法-----快速排序(非递归实现),数据结构与算法,排序算法,数据结构,算法,c语言,c++文章来源地址https://www.toymoban.com/news/detail-811577.html

到了这里,关于排序算法-----快速排序(非递归实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包