Data Structure--排序--顺序表(非递归快排) --队列(非递归快排)

川长思鸟来 2022-11-03 11:19 132阅读 0赞

### 非递归快排 ###

*  顺序表实现
 *  队列实现

# 顺序表实现 #

在这里利用顺序表实现快排需要包含顺序表对应的接口,具体: [点击此处][Link 1]

//划分函数
    int partion(int* arr, int begin, int end){ 
    
    	//获取基准值位置
    	int mid = getMid(arr, begin, end);
    	//把基准值放到起始位置
    	Swap(arr, begin, end);
    
    	//首先选择基准值
    	int key = arr[begin];
    	int start = begin;
    
    	while (begin < end){ 
    
    		//从后向前找小于基准值的位置
    		while (begin < end&&arr[end] >= key)
    			--end;
    
    		//从前向后找大于的位置
    		while (begin < end&&arr[begin] <= key)
    			++begin;
    		//调用函数交换
    		Swap(arr, begin, end);
    	}
    	//交换基准值与相遇位置的数据
    	Swap(arr, start, begin);
    	return begin;
    }
    
    //================================================================顺序表实现
    void quickSortNoR(int* arr, int n){ 
    
    	//创建一个顺序表,保持划分区间
    	seqList sq;							//创建
    	initSeqList(&sq);					//初始化
    
    	//先保存整个区间
    	//首先==========================!!!放右,在放左!!!
    	pushBack(&sq, n - 1);					
    	pushBack(&sq, 0);
    
    	//遍历顺序表,处理区间
    	while (!empty(&sq)){ 		//判空,进行循环
    
    		//取出一个区间
    		int left = seqListBack(&sq);		//左边先插入一个
    		popBack(&sq);						//取出
    
    		int right = seqListBack(&sq);		//右边插入
    		popBack(&sq);						//取出
    
    		//划分区间
    		int div = partion(arr, left, right);		//调用函数对区间进行划分
    
    		//保存产生的新区间
    		if (left < div - 1){ 		//如果存在于左半边
    
    			pushBack(&sq, div - 1);		//对左边进行插入
    			pushBack(&sq, left);
    		}
    		if (div + 1 < right){ 		//存在于右半边,对右半边进行插入
    
    			pushBack(&sq, div + 1);
    			pushBack(&sq, right);
    		}
    	}
    }

接口很简单,主要是理解逻辑规律,充分理解顺序表,画图来进行解决.

# 队列实现 #

队列对应的接口:具体:[点击此处][Link 2]

//划分函数
    int partion(int* arr, int begin, int end){ 
    
    	//获取基准值位置
    	int mid = getMid(arr, begin, end);
    	//把基准值放到起始位置
    	Swap(arr, begin, end);
    
    	//首先选择基准值
    	int key = arr[begin];
    	int start = begin;
    
    	while (begin < end){ 
    
    		//从后向前找小于基准值的位置
    		while (begin < end&&arr[end] >= key)
    			--end;
    
    		//从前向后找大于的位置
    		while (begin < end&&arr[begin] <= key)
    			++begin;
    		//调用函数交换
    		Swap(arr, begin, end);
    	}
    	//交换基准值与相遇位置的数据
    	Swap(arr, start, begin);
    	return begin;
    }
    
    //================================================================队列实现
    void quickSortNoR2(int* arr, int n){ 
    	
    	Queue q;		//创建
    	queueInit(&q);	//初始化
    	//保存[0,n-1]区间
    
    	//队列先进先出
    	queuePush(&q, 0);
    	queuePush(&q, n - 1);
    	while (!queueEmpty(&q)){ 		//判空
    		
    		//取出一个区间的其实和结束位置
    		int left = queueFront(&q);		//左边取出队列的头
    		queuePop(&q);				//出队
    	
    		int right = queueFront(&q);		//右边取出队列的头 
    		queuePop(&q);				//出队
    		
    		//划分[left,right]
    		int div = partion(arr, left, right);		//调用函数进行划分
    
    		//子区间[left,div-1]
    		if (left < div - 1){ 		///在左半边进行操作
    			
    			queuePush(&q, left);
    			queuePush(&q, div - 1);
    		}
    
    		//子区间[div+1,right] 
    		if (div + 1 < right){ 		//右半边进行操作
    			
    			queuePush(&q, div + 1);
    			queuePush(&q, right);
    		}
    	}
    }

利用以前学过的实现较为简单,大体类似,只要学会运用其中一种,其他的都差不多,一起加油!!!多敲代码!!!开学也要继续努力!!!

[Link 1]: https://blog.csdn.net/weixin_46554582/article/details/113764090
[Link 2]: https://blog.csdn.net/weixin_46554582/article/details/113874587