随机快排.txt

里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等

#include <iostream>
#include <ctime>
using namespace std ;

#define N 20

int Partition(int a[], int low,int high)//划分a[m]...a[p]
{
    int i = low,j = high ,temp = a[low] ;
	while(i<j)
	{
		while(i<j && temp <= a[j]) j --;
		if(i < j)
		{
			a[i] = a[j] ;
			i ++ ;
		}

		while(i<j && a[i] < temp) i++ ;
		if(i < j)
		{
			a[j] = a[i] ;
			j -- ;
		}
	}
	a[i] =  temp; 
	return i ;
}

void quickSort(int a[], int low,int high)//////随机快排序
{
	if(low < high )
	{
		if((high-low)>5) swap(a[rand()%(high-low+1) + low] ,a[low]) ;
    	int i = Partition( a, low,high);
        quickSort(a,low,i - 1);
	    quickSort(a,i+1,high);
	}
}

int selection(int a[] , int low , int high , int k )//选择第几小的元素
{
	int s = Partition(a,low,high ) ;
	if(s == k-1) return a[s] ;
	else if(s < k-1) return selection(a, s + 1, high,k) ;
	else return selection(a, low , s -1 ,k) ;
    
}