高速排序 时间复杂读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
     
      tmp)			j--;		if(i
      
       length)		return;	int i=start;	int small = i-1;	for(i;i
       
        end)		return;		//int mid = quick(str,start,end,length);		int mid = partition2(str,start,end,length); 	int i=0;	for(i;i
       
      
     

完整代码

执行环境：ubuntu 14.04 kylin、gcc

#include 
     
      #include 
      
       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
       
        tmp)            j--;        if(i
        
         length)        return;    int i=start;    int small = i-1;    for(i;i
         
          end)        return;        //int mid = quick(str,start,end,length);        int mid = partition2(str,start,end,length);     int i=0;    for(i;i
          
           10000)        return 0 ;    srand((unsigned int)time(0));    int i=0;    for(i=0;i