快速排序 时间复杂读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]);}
版权声明：本文为博主原创文章，未经博主允许不得转载。
问候不一定要慎重其事，但一定要真诚感人
