快排算法

QuickSort.cpp

#include <iostream>
using namespace std;

/**
 *   一趟快排算法
 *   @author Boychenney
 *   @date   2013-10-25T10:54:47+0800
 *   @param  s 待排序的数组
 *   @param  l 开始索引
 *   @param  r 结尾索引
 *   @return 标杆索引
 *   @ref	http://blog.csdn.net/morewindows/article/details/6684558
 */
int AdjustArray(int s[],int l,int r){
	int i = l,j = r;
	int x = s[l];
	while(i<j){
		//从右到左边找小于x的数来填
		while(i<j && s[j]>=x) j--;
		if(i<j){
			s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑 
			i++;
		}

		//从左向右找大于或等于x的数来填s[j]
		while(i<j && s[i]<x) i++;
		if(i<j){
			s[j] = s[i];
			j--;
		}
	}
	//退出时，i等于j。将x填到这个坑中。
	s[i] = x;
	return i;
}

/**
 *   快排算法
 *   @author Boychenney
 *   @date   2013-10-25T11:03:25+0800
 *   @param  s 待排序数组
 *   @param  l 数组左边界
 *   @param  r 数组右边界
 */
void QuickSort(int s[],int l,int r){
	if(l < r){
		int i = AdjustArray(s,l,r);//先挖坑填
		QuickSort(s,l,i-1);
		QuickSort(s,i+1,r);
	}
}

int main(){
	int arr[13] = {7,23,29,31,42,14,35,38,21,46,49,52,18};
	int len = 13;
	cout<<"first method:"<<endl;
	QuickSort(arr,0,12);
	for(int i = 0; i< len;i++){
		cout<<arr[i]<<"-";
	}

	return 0;
}