高速排序 时间复杂读O(N*logN),最差O(N^2),平均O(N*logN)

主要思想是选取一个标志位，大于标志位的放到右边。小于标志位的放到左边。在以标志位为切割，分而制之，左递归，右递归。直到完毕。

高速排序的思想（双边扫描）

高速排序就像一个数据快，前后各有一个下标（指针）i/j，随机选取（此处取下标为0的）一个元素作为标志位。存储在暂时变量中（tmp），j从后向前移动（j--）直到碰到比tmp还要小的数时与i交换，此时i開始像后走，直到遇到第一个比tmp大的数，与j交换。

递归直至完毕。

高速排序思想（单边扫描）

从左到右扫一遍，类似于冒泡排序，仅仅是不停的把小于标志位的值放到左边，大于的放到右边。找到切割位置将标志位放入。

单边扫描怎么把小于标志位（下标end）的放左边。大于标志位的放右边，双边扫描是通过挖坑埋数的方式来实现的，单边扫描能够通过一个small 标志位记录连续最小的哪一个数，index一直向前走找到第一个不连续的小于标志位的值，与small++（第一个大于标志位的值）进行交换。直到循环结束，将small++的值放到标志位end的下标位置。

注：如有错误，望批评指正。算法主要是思想，其次就是依照思想去实现了。//双边int partition2(long *str,int start,int end,int length){
	if(str == NULL || length <=1 || start >end)
		return 0;
	int i=start;
	//标志位        long tmp = str[start];
	int j=end;
	while(i!=j){
		while(i<j && str[j]>tmp)
			j--;
		if(i<j)
			swap(&str[j],&str[i++]);	
		
		while(i<j && str[i]<tmp)
			i++;
		if(i<j)
			swap(&str[i],&str[j--]);
		
	}
	swap(&str[i],&tmp);
	return i;
}//单边扫描 int  partition(long *str,int start,int end,int length){
	if(str ==NULL || length<=0 || start<0 || end >length)
		return;
	int i=start;
	int small = i-1;
	for(i;i<end;i++){               //通过对照调整small的位置，直到small的位置到达连续小于标志位的最右端数据                if(str[i]<str[end]){
			++small;
			if(small != i)
				swap(&str[i],&str[small]);
		}
		
	}
	++small;
	swap(&str[small],&str[end]);
	
	return small;
}//递归调用，实现高速排序 void quickSort(long *str,int start,int end,int length){
	if(str == NULL || length<1 || start >end)
		return;
	
	//int mid = quick(str,start,end,length);	
	int mid = partition2(str,start,end,length); 
	int i=0;
	for(i;i<length;i++)
		printf("%ld\t",str[i]);
	printf("\n");
		quickSort(str,start,mid-1,length);
	
		quickSort(str,mid+1,end,length);
}

执行环境：ubuntu 14.04 kylin、gcc

#include <stdio.h>#include <malloc.h>void swap(long *A,long *B){    long tmp;    tmp = *A;    *A = *B;    *B = tmp;}int partition2(long *str,int start,int end,int length){    if(str == NULL || length <=1 || start >end)        return 0;    int i=start;    long tmp = str[start];    int j=end;    while(i!=j){        while(i<j && str[j]>tmp)            j--;        if(i<j)            swap(&str[j],&str[i++]);                    while(i<j && str[i]<tmp)            i++;        if(i<j)            swap(&str[i],&str[j--]);            }    swap(&str[i],&tmp);    return i;}int  partition(long *str,int start,int end,int length){    if(str ==NULL || length<=0 || start<0 || end >length)        return;    int i=start;    int small = i-1;    for(i;i<end;i++){        if(str[i]<str[end]){            ++small;            if(small != i)                swap(&str[i],&str[small]);        }            }    ++small;    swap(&str[small],&str[end]);        return small;}void quickSort(long *str,int start,int end,int length){    if(str == NULL || length<1 || start >end)        return;        //int mid = quick(str,start,end,length);        int mid = partition2(str,start,end,length);     int i=0;    for(i;i<length;i++)        printf("%ld\t",str[i]);    printf("\n");        quickSort(str,start,mid-1,length);            quickSort(str,mid+1,end,length);}int genrand(int num,long * array ){    if (num>10000)        return 0 ;    srand((unsigned int)time(0));    int i=0;    for(i=0;i<num;i++)        array[i] = rand();    return 1;    }void main(){    int num = 10;    long *array=(long *)malloc(sizeof(long)*num) ;     genrand(num,array);         int i=0;    /*for(i=0;i<num;i++)        printf("%ld\n",array[i]);    */    quickSort(array,0,9,10);    printf("\n\n");        for(i=0;i<num;i++)        printf("%ld\n",array[i]);}