首页 > 代码库 > 算法之快速排序
算法之快速排序
快速排序 是1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称为分治法 (Divide-and-Conquer Method)。
分治法的基本思想 :
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序的基本思想 :
设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:
(1) 分解
在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1]和R[pivotpos+1..high],并使 左边子区间中所有记录的关键字均<=基准记录的关键字pivot.key,右边的子区间中所有记录的关键字均>=pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。
(2) 求解
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]分别进行快速排序。
(3) 组合
因为当“求解”步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,“组合”步骤无须做什么,可看做是空操作。
1 #include <stdio.h> 2 3 int partition(int *a, int low, int high) 4 { 5 int key = a[low]; 6 while(low<high) 7 { 8 while(low<high && a[high]>key) 9 high--;10 if(a[high]<key)11 a[low] = a[high];12 while(low<high && a[low]<=key)13 low++;14 if(a[low]>key)15 a[high] = a[low];16 }17 a[low] = key;18 return low;19 }20 int quick_sort(int a[], int low, int high)21 {22 int pos;23 if(low<high)24 {25 pos = partition(a, low, high);26 quick_sort(a, low, pos-1);27 quick_sort(a, pos+1, high);28 }29 }30 31 int main()32 {33 int i;34 int arr[] = {12, 33, 25,87, 90, 77, 35, 77, 46, 29};35 quick_sort(arr,0, 9);36 for(i=0;i<10;i++)37 {38 printf("%d\t", arr[i]);39 }40 printf("\n");41 return 0;42 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。