中最大或者最小的元素写入数组，并把这个元素放在buffer里。保持最大值低于这些关键数据，最小值高于这些关键数据，从而避免对已经有序的中间的数据进行重排。完成后，数组的中间空位必然空出，把这个buffer写入数组中间空位。然后递归地对外部更小的部分，循环地对其他部分进行排序。 三路基数快排（Three-way Radix Quicksort，也称作Multikey Quicksort、Multi-key Quicksort）：结合了基数排序（radix sort，如一般的字符串比较排序就是基数排序）和快排的特点，是字符串排序中比较高效的算法。该算法被排序数组的元素具有一个特点，即multikey，如一个字符串，每个字母可以看作是一个key。算法每次在被排序数组中任意选择一个元素作为关键数据，首先仅考虑这个元素的第一个key（字母），然后把其他元素通过key的比较分成小于、等于、大于关键数据的三个部分。然后递归地基于这一个key位置对“小于”和“大于”部分进行排序，基于下一个key对“等于”部分进行排序。 编辑本段排序
快速排序伪代码（非随机） 下面的过程实现快速排序： QUICKSORT(A，p，r) 1 if p 2 then q ←PARTITION(A，p，r) 3 QUICKSORT(A，p，q-1) 4 QUICKSORT(A，q+1，r) 为排序一个完整的数组A，最初的调用是QUICKSORT(A，1，length[A]）。 快速排序算法的关键是PARTITION过程，它对子数组A[p..r]进行就地重排： PARTITION(A，p，r) 1 x←A[r] 2 i←p-1 3 for j←p to r-1 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[1] 快速排序伪代码（随机） 对PARTITION和QUICKSORT所作的改动比较小。在新的划分过程中，我们在真正进行划分之前实现交换： （其中PARTITION过程同快速排序伪代码（非随机）） RANDOMIZED-PARTITION(A，p，r) 1 i← RANDOM(p，r) 2 exchange A[r+←→A[i] 3 return PARTITION(A，p，r) 新的快速排序过程不再调用PARTITION，而是调用RANDOMIZED-PARTITION。 RANDOMIZED-QUICKSORT(A，p，r) 1 if p 2 then q← RANDOMIZED-PARTITION(A，p，r) 3 RANDOMIZED-QUICKSORT(A，p，q-1) 4 RANDOMIZED-QUICKSORT(A，q+1，r)[1] Python，递归排序（非随机） 1 def partition(inlist,start_index,end_index): 2 flag = inlist[end_index] 3 i = start_index - 1 4 for j in range(start_index,end_index): 5 if inlist[j] > flag: 6 pass 7 else: 8 i += 1 9 tmp = inlist[i] 10 inlist[i] = inlist[j] 11 inlist[j] = tmp 12 tmp = inlist[end_index] 13 inlist[end_index] = inlist[i+1] 14 inlist[i+1] = tmp 15 return i+1 16 17 def quickSort(inlist,start_index,end_index): 18 if start_index >= end_index: 19 return 20 middle = partition(inlist,start_index,end_index) 21 quickSort(inlist,start_index,middle-1) 22 quickSort(inlist,middle+1,end_index) 23 return inlist 24 25 print quickSort([49,27, 38,1, 13, 76, 97, 65],0,len([49,27, 38,1, 13, 76, 97, 65])-1) C++，递归快排（非随机） 1 #include 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 } a[right] = a[left]; qs(begin,right-1); qs(right+1,end); } int main(){ int i; for (i =0;i< 50;i++){ a[i] =50-i; } cout<<\排序前\ for (i= 0;i<50;i++){ cout<<\ } cout<<\排序后\ qs(0,49); for (i=0;i<50;i++){ cout<<\ } system(\ return 0; } C++，快排（函数） 在c++中可以用函数qsort（）可以直接为数组进行排序。 用法: 1 void qsort(void *base, int nelem, int width, 2 int (*fcmp)(const void *,const void *)); 参数： 1 待排序数组首地址 2 数组中待排序元素数量 3 各元素的占用空间大小 4 指向函数的指针，用于确定排序的顺序 qsort 的函数原型是 1 void __cdecl qsort ( void *base, size_t num, size_t width, 2 int (__cdecl *comp)(const void *, const void* ) ); 其中base是排序的一个集合数组，num是这个数组元素的个数，width是一个元素的大小，comp是一个比较函数。 比如：对一个长为1000的数组进行排序时，int a[1000]; 那么base应为a，num应为 1000，width应为 sizeof(int)，comp函数随自己的命名。 1 qsort(a,1000,sizeof(int ),comp); 其中comp函数应写为: 1 int comp(const void *a,const void *b){ 2 return *(int *)a-*(int *)b; 3 } 上面是由小到大排序，return *(int *)b-*(int *)a; 为由大到小排序。 很显然快速排序在对于大的、乱数列表一般相信是最快的已知排序。所以在c++的函数库里，已经为我们写好此函数。 在c++中我们也可以自己写快速排序的函数源代码： 1 void sort(int *a,int x,int y){ 2 int xx=x,yy=y; 3 int k=a[x]; 4 if(x>=y) return ; 5 while(xx!=yy){ 6 while(xx Pascal，递归快排1 1 procedure work(l,r: longint); 2 var i,j,tmp: longint; 3 begin 4 if l 26 27 28 29 end; //本段程序中stone是要排序的数组，从小到大排序，stone数组为 //longint（长整型）类型。 //在主程序中的调用命令为“work(1,n）;”不含引号。 //表示将stone数组中的1到n号元素进行排序。 Pascal，递归快排2 1 Program quiksort; 2 //快速排序法 3 const max=100; 4 var n:integer; 5 a:array[1..max] of longint; 6 procedure sort(l,r: longint); 7 var i,j,x,y: longint; 8 begin 9 i:=l; j:=r; x:=a[(l+r) div 2]; 10 repeat 11 while a[i] Pascal，递归快排3 1 procedure qsort(first,last:integer); 2 var k,left,right,mid:integer; 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库快速法排序(2)在线全文阅读。
相关推荐：