专栏首页desperate633LintCode整数排序题目分析解答选择排序插入排序小结

LintCode整数排序题目分析解答选择排序插入排序小结

题目

Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n2) algorithm.

Example Given[3, 2, 1, 4, 5] , return[1, 2, 3, 4, 5] .

分析

显然这道题我们可以用冒泡,选择,插入等排序方法实现。 就此机会正好复习一下这三种复杂度为 O(n2)的排序算法

解答

冒泡排序

public class Bubble {

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

选择排序

public class Selection {

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

插入排序

public class Insert {

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

小结

三种排序都用了两个for循环实现。实现这三种排序的代码很多,也可以用while循环实现。重要的是三种排序方法的思想以及将算法转换为代码的能力

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 3. Longest Substring Without Repeating Characters题目分析

    样例 例如,在"abcabcbb"中,其无重复字符的最长子字符串是"abc",其长度为 3。

    desperate633
  • LeetCode 215. Kth Largest Element in an Array分析

    显然最简单的思想就是排序,然后取出倒数第k个元素就可以了,我们可以直接调用内部的排序函数。

    desperate633
  • LeetCode 75. Sort Colors题目分析

    给定一个包含红,白,蓝且长度为 n 的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0,1 和 2 分别代...

    desperate633
  • 挑战程序竞赛系列(79):4.3 2-SAT(3)

    挑战程序竞赛系列(79):4.3 2-SAT(3) 传送门:POJ 2723: Get Luffy Out 题意: 题目意思有点坑,实际上给出每一对钥匙,如...

    用户1147447
  • 1005 生日礼物

    1005 生日礼物  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descriptio...

    attack
  • 古典密码加密解密之多表代换

    多表代换密码首先将明文M 分为由n 个字母组成的分组, , … ,对每个分组的加密为 ≡ + ( ), = , , … 其中,(A,B)是密钥,A 是 ...

    张泽旭
  • 西南民族大学程序竞赛

    No matter what activities you join,whether you want or not, you could gain unexp...

    AngelNH
  • HDU 1083 Courses(二分图最大匹配)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1083

    Ch_Zaqdt
  • 蓝桥杯vip测试题系统试题-算法提高 矩阵转置

    给定一个n×m矩阵相乘,求它的转置。其中1≤n≤20,1≤m≤20,矩阵中的每个元素都在整数类型(4字节)的表示范围内。

    TrueDei
  • P1903 【模板】分块/带修改莫队(数颜色)

    题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

    attack

扫码关注云+社区

领取腾讯云代金券