简单排序

简单排序(Java实现)。

冒泡排序

原理

  1. 比较相邻元素,如果前者比后者大,交换
  2. 对所有相邻元素重复
  3. 对除了最后一个的所有元素重复2

复杂度

最好情况:O(n) 平均时间复杂度:O(n^2)

代码

public static void bubbleSort(int[] a){
    for(int outer = a.length - 1; outer > 1; outer--)
        for(int inner = 0; inner < outer ;inner++)
            if(a[inner] > a[inner + 1])
                swap(a, inner, inner+1);
}

选择排序

原理

每次选出最小的元素放到开始位置。

复杂度

时间复杂度 O(n^2) 但是交换次数比冒泡排序少

代码

public static void selectSort(int[] a){
    int min;
    for(int i = 0; i < a.length - 1; i++){
        min = i;
        for(int j = i + 1; j < a.length; j++)
            if(a[j] < a[min]) min = j;
        swap(a, i, min);
    }
}

插入排序

原理

在局部有序的数字中插入被标记的值。

复杂度

时间复杂度为O(n^2) 但是一般情况下比冒泡排序快一倍,比选择排序也快一点。

代码

public static void insertSort(int[] a){
    for(int i = 1; i < a.length; i++){
        int j = i, temp = a[i];
        while(j > 0 && a[j - 1] >= temp){
            a[j] = a[j - 1];j--;
        }
        a[j] = temp;
    }
}

三种排序的比较

选择排序降低了交换次数,但是比较次数仍然很多,当数据量比较少,或者基本上有序的时候,使用选择排序。 对于其他情况,应该选择插入排序。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode-463.整数排序

    给一组整数,按照升序排序,使用选择排序,冒泡排序,插入排序或者任何 O(n2) 的排序算法。

    悠扬前奏
  • LintCode-3.统计数字

    例如n=12,k=1,在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],我们发现1出现了5次 (1, 10, 11, 1...

    悠扬前奏
  • Scala-4.控制结构-break和continue

    Scala中没有break和continue这两个关键字,而是以scala.util.control.Breaks类的工具形式提供的。并且需要加上breakab...

    悠扬前奏
  • 程序员进阶之算法练习(七)

    前言 最近来公司面试的开发者很多,经验从1、2年,到5、6年都有,大都不堪重用。 或许在一些程序员眼里,能实现功能,保证上线即可。代码质量,可扩展性,复杂度...

    落影
  • 排序算法的实现与比较

    Zoctopus
  • 14:Challenge 7(map大法好)

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

    attack
  • LOJ#6278. 数列分块入门 2

    内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论测试数据 题目描述 给出...

    attack
  • Plus One

    问题:数组模拟整数加1 class Solution { public: vector<int> plusOne(vector<int> &digits...

    用户1624346
  • LOJ#6279. 数列分块入门 3

    内存限制:256 MiB时间限制:1500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论 1 测试数据 ...

    attack
  • BZOJ4259: 残缺的字符串(FFT 字符串匹配)

    考虑把B翻转过来,如果\(\sum_{k = 0}^M (B_{i - k} - A_k)^2 * B_{i-k}*A_k = 0\)

    attack

扫码关注云+社区

领取腾讯云代金券