专栏首页云霄雨霁排序算法总结

排序算法总结

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

算法

是否稳定

是否原地排序

时间复杂度

空间复杂度

选择排序

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系统选择对原始数据类型使用(三向切分的)快速排序,对引用类型使用归并排序。

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

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

找出重复元素

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

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,算法完成。

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];
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序----堆排序

    SuperHeroes
  • 加权有向图----无环情况下的最短路径算法

    SuperHeroes
  • 字符串排序----高位优先的字符串排序

    SuperHeroes
  • 请不要无脑ArrayList 还有一个LinkedList也不错哟

    前面讲解过集合框架的大致结构,本章详细介绍List这个接口以及List接口的三个实现,ArrayList,LinkedList和Vector。

    用户5745563
  • 驾校答题小程序实战全过程【连载】——2.答题功能

    思路:优先实现功能逻辑,UI后面调整,我们用iview 拖一个大致结构的页面。 这里用了以下组件

    大王12
  • Arrays.asList使用指南

      List是一种很有用的数据结构,如果需要将一个数组转换为 List 以便进行更丰富的操作的话,可以这么实现:

    老九学堂-小师弟
  • 在mono 3.0 下运行ASP.NET 4网站的主意事项

    由于mono3.0开始,.NET4是以.NET4.5为默认环境,所以,当服务器升级到mono3后,原来的ASP.NET4网站会出现问题,比如“System.Ar...

    张善友
  • 别再SOTA了,那叫“微调”!Science发文炮轰论文灌水

    为了一探究竟,来自MIT的研究人员,便对81种AI算法做了横测,结果令人大跌眼镜:

    Amusi
  • 别再SOTA了,那叫“微调”!Science发文炮轰论文灌水

    为了一探究竟,来自MIT的研究人员,便对81种AI算法做了横测,结果令人大跌眼镜:

    量子位
  • javascript 红皮高程(9)

    这两天把JS的Number类型过了一遍,真是遍地是坑啊,如果这里出一些面试题,我100%要栽在这里。 NaN,undefined,null,Infinity,i...

    web前端教室

扫码关注云+社区

领取腾讯云代金券