前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >排序算法总结

排序算法总结

作者头像
SuperHeroes
发布2018-05-30 17:24:53
5030
发布2018-05-30 17:24:53
举报
文章被收录于专栏:云霄雨霁

稳定性:如果一个排序算法能够保留数组中重复元素的相对位置,则可以被称为稳定的。有很多办法能够将任意排序算法变为稳定的,但一般只有在稳定性要求是必要的情况下才会去实现。

算法

是否稳定

是否原地排序

时间复杂度

空间复杂度

选择排序

N^2

1

插入排序

介于N和N^2之间

1

希尔排序

NlgN?   N^(6/5)?

1

快速排序

NlgN

lgN

三向快速排序

介于N和NlgN之间

lgN

归并排序

NlgN

N

堆排序

NlgN

1

快速排序是最快的通用排序算法。

java系统库中主要的的排序算法java.util.Arrays.sort()实际上代表了一系列排序算法:

  • 每种原始数据类型有一种不同的排序算法
  • 一个适用于所有实现了Comparable接口的数据类型的排序算法
  • 一个适用于实现了比较器Comparator的数据类型的排序算法

Java系统选择对原始数据类型使用(三向切分的)快速排序,对引用类型使用归并排序。

使用排序算法解决其他问题的思想是算法设计领域的基本技巧----归约的一个例子。规约是指为了解决某个问题而发明出来的一个算法正好可以用来解决另一个问题。

下面是排序算法解决一些其他问题的例子:

找出重复元素

对大数组,平方级别的算法将元素互相比较一遍不太合适。我们可以先将数组排序,然后记录连续出现的重复元素即可。

代码语言:javascript
复制
Quick.sort(a);
int count = 1;
for(int i=1;i<a.length;i++){
    if(a[i].compareTo(a[i-1])!=0)
        count++;
//统计a[]数组中不重复元素个数

排列

一组排列就是一组N个整数的数组,其中0到N-1每个数都只出现一次。两个排列之间的Kendall tau距离就是两组排列中顺序不同的数对的数目。如0 3 1 6 2 5 4和1 0 3 6 4 2 5之间的Kendall tau距离是4。因为0-1,3-1,2-4,5-4这4对数字在两组数列中相对顺序不同。可以根据插入排序算法设计一个算法计算Kendall tau距离。

选取第k小元素

下面的select()方法可以在线性时间内解决这个问题,它用两个变量lo和hi限制含有k元素的子数组,并用快速排序的切分法来缩小子数组范围。

切分法将数组分为a[lo...j], a[j], a[j+1...hi]三个数组。如果j=k,问题解决。如果k<j,我们就需要切分左子数组,否则切分右子数组。不断切分直到子数组只含第k个元素,此时a[0...k-1]都小于a[k], a[k+1...hi]都大于k,算法完成。

代码语言:javascript
复制
public static select(Comparable[] a,int k){
    int lo = 0, hi = a.length;
    while(hi>lo){
        int j = partition(a,lo,hi);//调用快速排序的切分方法
        if(j == k)return a[k];
        else if(j>k) hi = j-1;
        else if(j<k) lo = j+1;
    {
    return a[k];
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017.11.30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档