排序算法-快速排序（及求第K小元素）

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

速排序：不稳定排序方法, 也是一种分治法的经典应用。

时间复杂度，平均O(n logn), 最坏：O(n^2);  空间复杂度O(logn);

 

//quik sort
template <typename T>
int quick_adjust(T * A, int first,int last){
	int i=first,j=last;
	T x=A[i];
	while(i<j){
		while(i<j && A[j]>=x)
			j--;
		if(i<j)
			A[i++]=A[j];
		while(i<j && A[i]<=x)
			i++;
		if(i<j)
			A[j--]=A[i];
	}
	A[i]=x;
	return i;
}
template <typename T>
void quick_sort(T *A, int first, int last){
	int mid;
	if(first<last){
		mid=quick_adjust(A,first,last);
		quick_sort(A,first,mid-1);
		quick_sort(A,mid+1,last);
	}
	
}

 

优化，参考《编程珠玑》

//更新 2013.9.13
// question1：如果数组A中的数据都一样，则快速排序退化为冒泡排序，优化策略是
//让轴点依然能够移动数据序列中心
// question 2: 如果数列有序，则依然会退化为冒泡排序，解决策略是随机选取一个作为支点
template <typename T>
void quick_sort_u(T A[],int first,int last){
	if(first>=last)
		return;
	int i=first,j=last+1;
	int index=rand()%(last-first+1)+first;
	swap(&A[first],&A[index]); // 取随机数中的一个作为随机轴点
	T x=A[i];
	while(1){
		do{
			i++;
		}while(i<=j && A[i]<x);
		do{
			j--;
		} while (A[j]>x);
		
		if(i>=j)
			break;
		swap(&A[i],&A[j]);
	}
	swap(&A[first],&A[j]);
	quick_sort_u(A,first,j-1);
	quick_sort_u(A,j+1,last);
	
}

2013.9.13

快速排序的一个最明显特点是，每次快排的过程中都能对一个元素进行定位，即知道它的确切元素位置(或者说它在序列中的排名).

求第K小元素可以用快速排序的思想求得，时间复杂度为O(n）

//求第K小元素
template <typename T>
void quick_sort_select_kmin(T A[],int first,int last,int k){// k从下标0开始算起
	if(k<first || k>last){
		cout<<"no this number"<<endl;
		return;
	}
	if(first>=last){
		if(first==last && k==last) //只有一个元素时
			cout<<"found,it is"<<A[k]<<endl;
		return;
	}
	int i=first,j=last+1;
	int index=rand()%(last-first+1)+first;
	swap(&A[first],&A[index]); // 取随机数中的一个作为随机轴点
	T x=A[i];
	while(i<j){
		do{
			j--;
		} while (i<j && A[j]>x);
		do{
			i++;
		}while(i<j && A[i]<x);
		
		if(i>=j)
			break;
		swap(&A[i],&A[j]);
	}
	swap(&A[first],&A[j]);
	if(j==k){
		cout<<"found,it is"<<A[k]<<endl;
		return;
	}
	else if(j>k)
		quick_sort_select_kmin(A,first,j-1,k);
	else
		quick_sort_select_kmin(A,j+1,last,k);
}