开发者社区> 天色渐晚> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

算法之快速排序

简介: 快速排序 是1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称为分治法 (Divide-and-Conquer Method)。 分治法的基本思想 :将原问题分解为若干个规模更小但结构与原问题相似的子问题。
+关注继续查看

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

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
经典算法之快速排序
经典算法之快速排序
23 0
经典算法---快速排序
快速排序是冒泡排序的改进算法,主要思想是在待排序列中取一个元素(通常为第一个)作为参照,将序列分为两个子序列,比参照值小的元素和比参照值大的元素各自组成一个子序列。每趟排序会使参照元素归位,并得到两个子序列。在子序列中继续执行该步骤,直到子序列的长度为0或1.
15 0
算法渣-排序-快速
没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法
345 0
快速排序算法
快速排序算法通过多次比较和交换来实现排序,其排序流程如下
22 0
【算法】快速排序
【算法】快速排序
21 0
排序算法:快速排序
排序算法:快速排序
32 0
算法-快速排序
快速排序是广泛使用的排序算法,它在平均情况下进行n log n比较,以对 n 个元素的数组进行排序。该算法遵循分而治之的方法。分而治之是一种将算法分解为子问题,然后解决子问题,并将结果组合在一起以解决原始问题的技术。
35 0
+关注
天色渐晚
既然选择远行,便只顾风雨兼程!
442
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载