快速排序非递归算法

柔光的暖阳◎ 2022-04-13 04:09 237阅读 0赞

#define MaxN 1000
    typedef int keytype;
    void QUICKSORT(keytype K[],int n){
    
    	int i,j,left,right,pos=-1;
    	int buf[MaxN][2];//数组buf用以保存下一趟快拍的起始和末尾位置
    	keytype temp;
    	while(1){/*K[left]为分界元素*/
    		i = left;
    		j = right;
    		while(1){ //每一次排序从这里开始
    			do i++; while(i!= right && K[i]<K[left]);
    			do j--; while(j!= left && K[j]>K[left]);
    			if (i<j)
    			{
    				temp = K[i];
    				K[i] = K[j];
    				K[j] = temp; //以上三条交换K[i]与K[j]的内容
    			}else{
    				break;
    			}
    		}
    		temp = K[left];
    		K[left] = K[i];
    		K[i] = temp; //交换K[left]与K[i]的内容
    		if (j+1>=right && j-1<=left)//被分成两部分都不足两个元素
    		{
    			if (pos == -1)
    			{
    				break; //保存排序首,尾位置的数组为空,排序结束
    			}
    			left = buf[pos][0];//获取新的排序范围的起始位置
    			right = buf[pos--][1];//获取新的排序范围的末尾位置
    		}else{
    			if (j+1<right && j-1 > left)//若前后两部分都超过一个元素
    			{
    				buf[++pos][0] = j+1;
    				buf[pos][1] = right; //保存排序后边部分的首尾位置
    				right = j-1;
    			}
    			else if (j+1>=right)//若只有被分成的前部分只有一个元素
    			{
    				right = j-1;
    			}else{ //若只有被分成的后部分只有一个元素
    				left = j+1;
    			}
    		}
    
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，237人围观）

还没有评论，来说两句吧...

相关阅读

相关非递归算法——快速排序、归并排序

![30adcf5df8b44dc8bc660f667cada2c4.jpeg][] 哈喽大家好，我是保护小周ღ，本期为大家带来的是常见[排序算法][Link 1]中的快

古城微笑少年丶/ 2023年10月03日 19:34/ 0 赞/ 15 阅读

相关 280-归并排序算法(递归和非递归)

归并排序算法(递归和非递归) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM

深碍√TFBOYSˉ_/ 2023年01月14日 13:57/ 0 赞/ 151 阅读

相关 238-快速排序算法(递归，非递归，随机取）

快速排序算法（递归）的实现 int Parition(int ar, int left,int right) { assert

Love The Way You Lie/ 2022年11月12日 01:44/ 0 赞/ 207 阅读

相关快速排序的非递归算法（使用队列）

　　前些天学习了程序栈空间的大小是会有上限的。看来递归的算法永远无法应用到大规模的数据上，毕竟栈空间有限。这几天写了点算法题目，刚好涉及到如何广度优先搜索。想起自己学数据结构的

怼烎@/ 2022年09月20日 11:13/ 0 赞/ 174 阅读

相关快速排序递归与非递归

递归法快排的思想设当前需要排序的数组为int A\[bt...ed\] 分解：在A\[\]中任选一个记录作为基准（pivot

素颜马尾好姑娘i/ 2022年09月18日 01:59/ 0 赞/ 243 阅读

相关快速排序的递归与非递归实现

import java.util.Arrays; import java.util.Stack; class QuickSort {

╰半夏微凉°/ 2022年06月09日 00:42/ 0 赞/ 255 阅读

相关排序算法：快速排序算法实现及分析（递归形式和非递归形式）

快速排序算法介绍从名字上就可以看出快速排序算法很嚣张，直接以快速命名。确实快速排序的确很快速，被列为20世纪十大算法之一。程序员难道不应该掌握么。快速排序（Quick

た入场券/ 2022年05月31日 14:16/ 0 赞/ 242 阅读

相关快速排序非递归算法

define MaxN 1000 typedef int keytype; void QUICKSORT(keytype K[],int n){

柔光的暖阳◎/ 2022年04月13日 04:09/ 0 赞/ 238 阅读

相关 java非递归快速排序

java非递归快速排序 public static void quickSort(int[] a) { //创建类保存开始结束索引

柔情只为你懂/ 2022年03月22日 03:19/ 0 赞/ 242 阅读

相关非递归的快速排序

一般的快速排序是用递归来实现的，如何将快速排序改写为迭代而不是递归？由于递归函数需要保护现场（在栈中），所以可以认为的构建一个栈。由于快速排序中处理排序是partition

骑猪看日落/ 2022年02月24日 13:58/ 0 赞/ 266 阅读