快速排序是一个比较好的算法，其平均时间复杂度为O(nlog(n)),最极端状态为O(n2)

对于排序算法来说是比较快的，但排序算法是递归的调用，会占用大量资源

实现如下：

 

/*	Filename:quickSort.cpp	Author: xiaobing	E-mail: xiaobingzhang29@gmail.com	Date: 2013-08-25*/#include
    
     #include
     
      #include
      
       #include
       
        #define N 10using 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
        
         = 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<
         
          <<" "; } cout<
         
        
       
      
     
    

转载请付上地址：