0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 快速排序【模板】

this_is_bill 2016-03-22 07:35:00 浏览1403

# 一、递归版本

``````void quickSort(int *arr, int left,int right) {

if(left>=right)
return;

int i=left,j=right;
int standard = arr[left];

while(i<j) {

//find some elements bigger than standard
while( i<j && arr[i] < standard)
++i;

//find some elements smaller than standard
while( i<j && arr[j] > standard)
--j;

//exchange arr.i and arr.j
swap(arr[i],arr[j]);
}
// i == j where the standard should be

quickSort(a,left,i-1);
quickSort(a,i+1,right);
}``````

《数据结构理论与实践》版本：

``````int Partition(int *arr, int i,int j) {

arr[0] = arr[i]; //arr[0] is a temp space

while(i<j) {

while(i<j && arr[j] >= arr[0]) --j;

if( i < j) { //move the smaller element to the front
arr[i] = arr[j];
++i;
}

while(i<j && arr[i] < arr[0]) ++i;

if( i < j) { //move the bigger element to the tail
arr[j] = arr[i];
--j;
}
}

arr[i] = arr[0];
return i;
}

void quickSort(int *arr, int left,int right) {

int i;
if(left<right) {
i = Partition(arr,left,right); //divide the arr into 2 parts
quickSort(arr,left,i-1);
quickSort(arr,i+1,right);
}
}``````

``````void quickSort(int *arr, int left, int right){
int i = left, j = right;
int mid = arr[(i+j)/2];
while(i <= j){
while(arr[i] < mid) i ++;
while(arr[j] > mid) j --;
if(i <= j){
int tmp;
tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
i ++; j --;
}
}
if(i < right) quickSort(arr,i, right);
if(left < j) quickSort(arr,left, j);
}``````

# 二、非递归版本

``````/**使用栈的非递归快速排序**/
template<typename Comparable>
void quicksort2(vector<Comparable>
&vec,int low,int high){
stack<int>
st;
if(low<high){
int mid=partition(vec,low,high);
if(low<mid-1){
st.push(low);
st.push(mid-1);
}
if(mid+1<high){
st.push(mid+1);
st.push(high);
}
//其实就是用栈保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，对这段子序列进行partition操作
while(!st.empty()){
int q=st.top();
st.pop();
int p=st.top();
st.pop();
mid=partition(vec,p,q);
if(p<mid-1){
st.push(p);
st.push(mid-1);
}
if(mid+1<q){
st.push(mid+1);
st.push(q);
}
}
}
}``````

this_is_bill
+ 关注