快速排序是一个比较好的算法，其平均时间复杂度为O(nlog(n)),最极端状态为O(n2)
对于排序算法来说是比较快的，但排序算法是递归的调用，会占用大量资源
实现如下：
/*
Filename:quickSort.cpp
Author: xiaobing
E-mail: xiaobingzhang29@gmail.com
Date: 2013-08-25
*/
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#define N 10
using namespace std;
int Partition(int data[],int low,int high);
/*
快速排序算法(quick sort),此算法的原理是：
才用分治的思想，排序过程有三个值需要注意：
一个是low，指向分组中的第一个元素，如第一次为a[0]
一个是high 指向分组中的最后一个元素，如第一次为a[n-1]
一个是mid 这个值用来做对这个分组进行分割的值，按理可以取任何值
但为了维护方便，总是取第一个值，即：a[low]
在数组a[0:n-1]进行排序时， 开始选择a[0]作为中间值mid，然后开始
1. 从最右边开始找一个比mid小的值，将a[low] = a[hight];接着，
2. 从最左边找一个比mid大的值，将a[high] = a[low];
注意：在两个位置low递增和high递减时，都得满足low < high
这样重复进行1,2,最终结束的条件就是low == high，
这时，将a[low] = mid，就把这个值给还原了，并且，可以发现，在a[low]
的右边都大于等于a[low]，在a[low]左边都小于等于a[low]，
这时，将分界点low返回，进行下一次从0到low - 1 和 low + 1到high的排序
最终将全部排序完毕为left + mid + high
*/
//这是一个递归函数，无限递归下去，所以快速排序要占大量的空间
void Quick_sort(int data[],int low,int high)
{
int mid;
if(low<high)
{
mid=Partition(data,low,high);
Quick_sort(data,low,mid-1); // 递归调用
Quick_sort(data,mid+1,high);
}
}
/* 要注意看清楚下面的数据之间是如何替换的，
* 首先选一个中间值，就是第一个元素data[low],
* 然后从该元素的最右侧开始找到比它小的元素，把
* 该元素复制到位置low (data[low]=data[high])，
* 然后low位置找到比它大的元素，把
* 该元素复制到位置high(data[high]=data[low])，
* 最后经过一个while(low < high)循环，最终low == high，
* 这时装入中间值(data[low]=mid])，
* 这样一来比mid大的都会跑到mid的右侧，小于mid的会在左侧，
* 最后一行，返回的low是中间元素的位置，左右分别递归就可以排好序了。
*/
int Partition(int data[],int low,int high)
{
int mid;
//先保存分界点值，作为mid来比较
mid=data[low];
while(low < high)
{
//这个循环是从右边开始找比mid小的元素的位置
while((low < high) && (data[high] >= mid))
{
--high;
}
// 从high的位置开始往low的方向找，找到比data[low]小的元素，存到data[low]中
data[low]=data[high];
// 这个循环是从左边开始找比mid大的元素的位置
while((low < high) && (data[low] < mid))
{
++low;
}
// 从low的位置开始往high的方向找，找到比data[high]大的元素，存在data[high]中
data[high]=data[low];
}
//注意到这里结束的条件是low == high，我看的时候这里没注意，想了很长时间
//将中间值存入mid，保持data[low] 左边的元素小于等于他，右边的大于等于他
data[low] = mid;
//返回分解点
return low;
}
//打印数据
void print(int a[], int n){
int i;
for(i = 0;i < n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
int main(){
int a[N] = {23,234,34,35,45,6,5,6,35,267};
int b[N] = {0,1,2,3,4,5,6,7,8,9};
Quick_sort(a, 0, N - 1);
print(a, N);
Quick_sort(b, 0, N - 1);
print(b, N);
return 0;
}
转载请付上地址： http://blog.csdn.net/hello_ok_google/article/details/10309337