首页 > 代码库 > 算法之快速排序

算法之快速排序

2024-07-15 02:33:38   227人阅读

快速排序 是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 }

 


联系
我们