快速排序递归与非递归算法

快速排序是不稳定的，是对冒泡排序的改进。

它的改进之处在于每轮会使一个基数归位，同时可以使基数两边的两组数基本有序（基数左边的数都小于基数，基数右边的数都大于基数）

它的平均时间复杂度O(nlogn)，最坏时间复杂度就是退化成冒泡排序O(n^2)

思路

无论是递归还是非递归，都需要给基数归位，那么基数怎样归位呢？

首先是选取基数(一般选取数组第一个或者是最后一个，这样方便计算)。然后从数组最右端依次向左端搜索，当遇到第一个小于基数的数时停下，再从数组最左端向右搜索，遇到第一个大于基数的数时停下，这时再交换这个两个逆序的数，就可以使得两边基本有序了。一直这样做直至左边的指针等于右边的指针（此时指针所指位置就是基数应该位于数组的里的位置）。

下面给出C语言递归代码

#include<stdio.h>
#define n 10
//快速快速
//思想是跳着交换两个位置，每次遍历都会使一个基数归位 
//升序排列。 
void quickSort(int a[],int left,int right);
int main(void){
	int num[n]={20,38,84,23,6,17,49,12,37,21};		//原始未排序数列 
	
	//quick sort
	quickSort(num,0,n-1);							//递归实现快速排序 
	
	int i;
	for(i=0;i<n;i++){
		printf("%d\n",num[i]);
	} 
	return 0;
}
void quickSort(int a[],int left,int right){
	int i,j,temp,t;
	if(left+1>right) return;						//每轮完成的是left位置的基数归位 
	temp=a[left];									
	i=left;j=right;
	while(i<j){										//归为基数 
		while(a[j]>=temp&&i<j){						//从基数位右边把小于基数的数与左边互换位置完成分组 
			j--;
		}while(a[i]<=temp&&i<j){
			i++; 
		}
		if(i<j){									//左右互换 
			t=a[i];
			a[i]=a[j];
			a[j]=t;
		} 
	}
	a[left]=a[i];
	a[i]= temp;
	quickSort(a,left,i-1);							//递归分完组的左边 
	quickSort(a,i+1,right);							// 递归分完组的右边
}

其实按照思路来写，并不是很难。

那么非递归算法又该如何写呢。

因为要用到stl容器，下面给出C++代码

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#define n 10
using namespace std;
int main(void){
	int num[n] = {4,7,1,2,9,0,4,6,11,3};
//	stack<int> st;
//	st.push(0);
//	st.push(n-1);
//	while(!st.empty()){
//		int end = st.top();				
//		st.pop();
//		int start = st.top();
//		st.pop();
//		int index = num[start];
//		int i = start ;
//		int j = end;
//		while (i<j){
//			while(i<j&&num[j]>=index){
//				j--;
//			}
//			while(i<j&&num[i]<=index){
//				i++;
//			}
//			if(i<j){
//			int temp=num[i];
//			num[i]=num[j];
//			num[j]=temp;
//			}
//		}
//		int temp = num[i];
//		num[i]=num[start];
//		num[start] = temp;
//		if(start<i-1){
//			st.push(start);
//			st.push(i-1);
//		}if(i+1<end){
//			st.push(i+1);
//			st.push(end);
//		}
//	}
//	
	queue<int> q;					//无论是队列还是栈，都是来储存数组下标的。 
	q.push(0);						//将最左端的下标加入队列 
	q.push(n-1);					//将最右端的下标加入队列 
	while(!q.empty()){				//可以把快速排序的非递归算法想象成广度优先搜素 
		int left = q.front();
		q.pop();
		int right = q.front();
		q.pop();
		int i = left;
		int j = right;
		int index = num[left];							//选择最左端的数作为基数 
		while(i<j){
			while(i<j&&num[j]>=index){					//从右向左找一个比基数小的数 
				j--;
			}while(i<j&&num[i]<=index){					//从左向右找一个比基数大的数 
				i++;
			}
			if(i<j){
				int temp = num[i];
				num[i]= num[j];
				num[j] = temp; 
			}
		}
		
		int temp = num[left];						//将基数归为 
		num[left] = num[i];
		num[i] = temp;
		
		if(left<i-1){								//这就相当于递归。  就是把分组的数组上下界加入队列 
			q.push(left);
			q.push(i-1);
		}if(right>i+1){
			q.push(i+1);
			q.push(right);
		}
	} 
	for(int i=0;i<n;i++){
		cout<<num[i]<<endl;
		}
	return 0;
}

可以看到注释里的是用栈写的快速排序非递归算法，没注释的是用队列写的

其实也可以用数组写，这都不是重点。它们只是容器用来记录数组分组界限的下标的。