快速排序(qsort)

         快速排序是一种高效的非稳定排序，它的基本思路是分支法，在一个序列a[]中找到一个数a[mid]，然后将序列a[]分为3部分a[start]---a[i-1],a[i],a[i+1]---a[end],第一部分的序列中，所有的数都小于a[i],第二部分的序列中，所有的数都大于a[i]。然后递归的对前后两部分进行处理，直到序列完成排序。

        那么快速排序的关键步骤就是对序列进行重排。有两种思路1）单向扫描。2）双向扫描。

       单向扫描：根据算法导论第二版他的算法流程为：

PARTITION(A, p, r)
1  x ← A[r]         //以最后一个元素，A[r]为主元
2  i ← p - 1
3  for j ← p to r - 1    //注，j从p指向的是r-1，不是r。
4       do if A[j] ≤ x
5             then i ← i + 1
6                  exchange A[i] <-> A[j]
7  exchange A[i + 1] <-> A[r]    //最后，交换主元
8  return i + 1

    可以看到，以序列的最后一个元素为基准元素，从序列头部开始扫描，如果发现a[i]小于基准元素，将他交换到序列前部（注意前部指针交换一次就加1）

       双向扫描：

OARE-PARTITION(A, p, r)
 1  x ← A[p]
 2  i ← p - 1
 3  j ← r + 1
 4  while TRUE
 5      do repeat j ← j - 1
 6           until A[j] ≤ x
 7         repeat i ← i + 1
 8           until A[i] ≥ x
 9         if i < j
10            then exchange A[i] <-> A[j]
11            else return j

  可以看到，扫秒从2头开始，如果发现a[i]>mid&&a[j]<mid将两者交换，注意基准元素为a[p],最后返回的是j

    最后给出具体代码，附带了随机化版本：

  

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
using namespace std;
void swap(int *src,int a,int b)
{
	int temp=src[a];
	src[a]=src[b];
	src[b]=temp;
}
int partition(int* src,int start,int end)
{
	int result;
	int i=start;
	int j=end;
	int mid=src[start];
	end=end+1;
	while(1)
	{
		while(src[++start]<mid&&start<j);
		while(src[--end]>mid);
		if(start>=end)
		break;
		swap(src,start,end);
	}	
	swap(src,i,end);
	return end;
}
int partition_single(int*src,int start,int end)
{
	int mid=src[end];
	int i=start-1;
	for(int j=start;j<end;j++)
	{
		if(src[j]<=mid)
		{
			++i;
			swap(src,i,j);
		}
	}	
	swap(src,i+1,end);
	return i+1;
}
int randomPartition(int*src,int start,int end)
{
	srand(time(NULL));
	int n=rand()%(end-start+1);
	int r=start+n;
	swap(src,start,r);
	return partition(src,start,end);
	//return partition_single(src,start,end);
}
void q_sort(int *src,int start,int end)
{
	if(start>=end)
		return;
	//int result=partition(src,start,end);
	//int result=partition_single(src,start,end);
	int result=randomPartition(src,start,end);
	q_sort(src,start,result-1);
	q_sort(src,result+1,end);
	
}
int main()
{
	int src[16]={16,11,15,9,10,13,14,8,2,1,5,12,6,3,7,4};
	q_sort(src,0,15);
	for(int i=0;i<16;i++)
	cout<<src[i]<<" ";
	cout<<endl;
	
	return 0;
}