C语言快速排序

tacheno 贡献于2011-11-09

作者 YIYI  创建于2009-07-04 22:35:27   修改者  修改于1899-12-30 00:00:00字数6641

文档摘要:快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2),但由于平均运行时间为O(nlogn),并且在内存使用、程序实现复杂性上表现优秀,尤其是对快速排序算法进行随机化的可能,使得快速排序在一般情况下是最实用的排序方法之一。
关键词:

快速排序 (一)概述   快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2),但由于平均运行时间为O(nlogn),并且在内存使用、程序实现复杂性上表现优秀,尤其是对快速排序算法进行随机化的可能,使得快速排序在一般情况下是最实用的排序方法之一。   快速排序被认为是当前最优秀的内部排序方法。 (二)实现   快速排序的实现基于分治法,具体分为三个步骤。假设待排序的序列为L[m..n]。   分解:序列L[m .. n]被划分成两个可能为空的子序列L[m .. pivot-1]和L[pivot+1 .. n],使L[m .. pivot-1]的每个元素均小于或等于L[pivot],同时L[pivot+1.. n]的每个元素均大于L[pivot]。其中L[pivot]称为这一趟分割中的主元(也称为枢轴、支点)。   解决:通过递归调用快速排序,对子序列L[m .. pivot-1]和L[pivot+1 .. r]排序。   合并:由于两个子序列是就地排序的,所以对它们的合并不需要操作,整个序列L[m .. n]已排好序。 (三)性质   内部排序   快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。   比较排序   快速排序确定元素位置的方法基于元素之间关键字大小的比较。   所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明,请参考有关算法的书籍,例如《算法导论》(第一版)第8章(第二版在第七章QuickSort)。   在理想情况下,能严格地达到O(nlgn)的下界。一般情况下,快速排序与随机化快速排序的平均情况性能都达到了O(nlgn)。   不稳定性   快速排序是一种不稳定的排序方法。简单地说,元素a1, a2的关键字有a1.key=a2.key,则不稳定的排序方法不能保证a1, a2在排序后维持原来的位置先后关系。   原地排序   在排序的具体操作过程中,除去程序运行实现的空间消费(例如递归栈),快速排序算法只需消耗确定数量的空间(即S(1),常数级空间)。   这个性质的意义,在于在内存空间受到限制的系统(例如MCU)中,快速排序也能够很好地工作。 (四)时空复杂度   快速排序每次将待排序数组分为两个部分,在理想状况下,每一次都将待排序数组划分成等长两个部分,则需要logn次划分。   而在最坏情况下,即数组已经有序或大致有序的情况下,每次划分只能减少一个元素,快速排序将不幸退化为冒泡排序,所以快速排序时间复杂度下界为O(nlogn),最坏情况为O(n^2)。在实际应用中,快速排序的平均时间复杂度为O(nlogn)。   快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。   但需要注意递归栈上需要花费最少logn 最多n的空间。 (五)随机化算法   快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求。”   随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。 (六)减少递归栈使用的优化   快速排序的实现需要消耗递归栈的空间,而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时,对系统栈的频繁存取会影响到排序的效率。   一种常见的办法是设置一个阈值,在每次递归求解中,如果元素总数不足这个阈值,则放弃快速排序,调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取,节省了时间的消费。   一般的经验表明,阈值取一个较小的值,排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案:阈值T=10,排序算法用选择排序。   阈值不要太大,否则省下的存取系统栈的时间,将会被简单排序算法较多的时间花费所抵消。   另一个可以参考的方法,是自行建栈模拟递归过程。但实际经验表明,收效明显不如设置阈值。 (七)C例程   以下是C语言权威《The C Programming Language》中的例程,在这个例程中,对于数组v的left到right号元素以递增顺序排序。   //Qsort.c by Tydus.   #include   int arr[] = {14,10,11,5,6,15,0,15,16,14,0,8,17,15,7,19,17,1,18,7};   /* swap函数:交换v[k]与v[j]的值 */   inline void swap(int v[], int k, int j)   {   int temp;   temp = v[k];   v[k] = v[j];   v[j] = temp;   }   void qsort(int v[], int left, int right)   {   int j, last;   if (left >= right) /* 若数组包含的元素个数少于两个 */   return; /* 则不执行任何操作 */   swap(v, left, (left + right)/2); /* 将划分子集的元素移动到V[0] */   last=left; /* 用last记录中比关键字小间的最右位置*/   for (j = left+1; j <= right; j++) /* 划分子集 */   {   if (v[j] < v[left])   {   swap(v, last++, j);   }   }   /*小小。。。。关键字大大大大*/   qsort(v, left, last-1);   qsort(v, last+1, right);   }   void main()   {   int j;   qsort(arr, 0, 19);   for(j=0; j<=19; j++)   {   printf("%d ", arr[j]);   }   printf("\n");   } (八)消除递归的快速排序   传统的快速排序是递归的,这就会受到递归栈深度的限制。比如在一台普通的PC上,当待排序元素达到10^6以上时,传统的递归快排会导致栈溢出异常,或者一个莫名其妙的错误结果。所以,对于巨大的数据规模,将快速排序消除递归是十分必要的。而消除递归,又将带来巨大的性能提升,把系统级的消耗降到最低。   消除递归的方法,就是模拟栈操作。但是从代码可以看出,这种模拟的消耗几乎可以忽略不计。因此消除递归的快排的效率是有保障的。   (虽然下面的代码没有使用随机化,但经过测试,它是目前所有快排编写方法中,效率最高,速度最快的!)   ////////////////////////////////////////////////////////////////////////////////   #define MAXARRAY 10000   #define PUSH(A,B) {sl[sp]=A;sr[sp]=B;sp++;}   #define POP(A,B) {sp--;A=sl[sp];B=sr[sp];}   void quicksort(int a[],int l,int r){   static int sl[MAXARRAY], sr[MAXARRAY], sp;   int i,j,p,t;   sp=0;   PUSH(l,r);   while(sp){   POP(l,r);   i=l;j=r;p=a[(i+j)/2];   while(i<=j){   while(a[i]p)j--;   if(i<=j){   t=a[i];a[i]=a[j];a[j]=t;   i++;j--;   }   }   if(l 或 #include   qsort(void* base, size_t num, size_t width, int(*)compare(const void* elem1, const void* elem2))   参数表   *base: 待排序的元素(数组,下标0起)。   num: 元素的数量。   width: 每个元素的内存空间大小(以字节为单位)。可用sizeof()测得。   int(*)compare: 指向一个比较函数。*elem1 *elem2: 指向待比较的数据。   比较函数的返回值   返回值是int类型,确定elem1与elem2的相对位置。   elem1在elem2右侧返回正数,elem1在elem2左侧返回负数。   控制返回值可以确定升序/降序。   一个升序排序的例程:   int Compare(const void *elem1, const void *elem2)   {   return *((int *)(elem1)) - *((int *)(elem2));   }   int main()   {   int a[100];   qsort(a, 100, sizeof(int), Compare);   return 0;   } (十一)PASCAL例程   1. 基本思想:   在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X),用此基准将当前无序区划分为左右两个较小的无序区:R[1..I-1]和R[I+1..H],且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准X则位于最终排序的位置上,即R[1..I-1] ≤X.Key≤R[I+1..H](1≤I≤H),当R[1..I-1]和R[I+1..H]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。   2. 排序过程:   【示例】:   初始关键字 [10 5 8 4 6 1 5 4 7 2](n为10)   第一次交换后[2 5 4 4 5 1] 6[ 8 10 ]   第二次交换后[2 1 4] 4 [5 5] 6 8[10 ]   第三次交换后1 2 4 4 5 5 6 8 10   最后的排序结果 1 2 4 4 5 5 6 8 10   type xxx=array[1..1000000] of longint;   var a,n;longint;   x:xxx;   procedure qsort(var x:xxx;l,r:longint);{x为要排序的数组,l为数组的要排序部分的起始位置,r为数组的要排序部分的终点位置}   var n,i,j,mid:longint;   begin   i:=l;{右边起点值}   j:=r;{左边终点值}   mid:=x[(i+j) div 2]; {基准数(用随机化更快)}   repeat   while (i<=j) and (xmid) do dec(j);{若右边的数比基准数大且左、右区未定,保留在右边}   if i<=j then{若左、右区未定(定且 左>基准数>右),交换}   begin   n:=x;   x:=x[j];   x[j]:=n;   inc(i);   dec(j);   end;   until i>j;{直到左右区已定(即左边终点j小于右边起点i)}   if il then qsort(x,l,j);{若左边多于一个数,快排左边}   end;   begin   readln(n);{读入要排序的数的个数}   for a:=1 to n do read(x[a]);{读入要排序的书}   writeln;   qsort(x,1,n);{排序程序}   for a:=1 to n-1 do write(x[a],' ');{输出排好序得数}   writeln(x[n]);   end. (十二)C语言随机化快排模块化代码   #include "stdio.h"   #include "stdlib.h"   #include "time.h"   Location(int *a,int low,int high)   {   int key,temp,x;   srand((unsigned)time(0));   x=rand()%(high-low+1)+low;   key=a[x];   while(low=a[low])low++;   temp=a[low];   a[low]=key;   a[x]=temp;   x=low;   }   return low;   }   Qsort(int *a,int low,int high)   {   int locat,i;   if(low>=high)return 0;   locat=Location(a,low,high);   Qsort(a,low,locat-1);   Qsort(a,locat+1,high);   } (十三)快速排序的JAVA实现   import java.util.Arrays;   public class QuickSort {   public static void quickSort(int[] array) {   quickSort(array, 0, array.length - 1);   }   private static void quickSort(int[] array, int low, int high) {   if (low < high) {   int p = partition(array, low, high);   quickSort(array, low, p - 1);   quickSort(array, p + 1, high);   }   }   private static int partition(int[] array, int low, int high) {   int s = array[high];   int i = low - 1;   for (int j = low; j < high; j++) {   if (array[j] < s) {   i++;   swap(array, i, j);   }   }   swap(array, ++i, high);   return i;   }   private static void swap(int[] array, int i, int j) {   int temp;   temp = array[i];   array[i] = array[j];   array[j] = temp;   }   /**   * @param args   */   public static void main(String[] args) {   int[] arr ={12,3,5,4,78,67,1,33,1,1,1};   quickSort(arr);   System.out.println(Arrays.toString(arr));   }   }

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 3 人已下载

下载文档