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 条评论
登录 后参与评论

相关文章

来自专栏lzj_learn_note

6-条件,循环语句

​ is运算符是用于判断同一性而不是相等性, x,y因为指向同一个列表所以结果为True, 但是变量z指向的是另一个 列表,即使列表中的值相等...

1304
来自专栏技术小站

c++(二)

算数运算符:+,-,*,/,%,++,--  进行算数运算时,如果存在溢出,则把溢出的部分拿掉(浮点型的难以预测),如 int i=0xffffffff,j;j...

1071
来自专栏王磊的博客

把字符串转化为类型

问题:可以得到类型的String格式的名称,想要转化为相应的类型? ps:今天定义了好多个枚举类型,把枚举名称存放在一个ComboBox类名,控件值改变的时候要...

2675
来自专栏韦弦的偶尔分享

Swift 两个数组的交集 II - LeetCode

给定两个数组,写一个方法来计算它们的交集。 例如: 给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

2952
来自专栏我是攻城师

在Scala里面如何使用正则处理数据

3365
来自专栏desperate633

LintCode 合并排序数组 II题目代码

合并两个排序的整数数组A和B变成一个新的数组。 注意事项 你可以假设A具有足够的空间(A数组的大小大于或等于m+n)去添加B中的元素。

642
来自专栏我是攻城师

Java里面关于数组拷贝的几种方式

3074
来自专栏十月梦想

正则表达式之(exp),(?:exp),(?=exp),(?!exp)的区别

正则表达式通过使用括号将表达式分为不同的分组,识别的方法是通过从左至右搜寻左半括号,遇到第一个左半括号时,则该左半括号与对应的右半括号所包含的内容即为第一分组,...

893
来自专栏HTML5学堂

提取数字——字符串、正则面试题

提取数字——字符串、正则面试题 HTML5学堂:正则、数组、字符串,是JavaScript语言中让人头痛的一些知识,今天这篇文章我们使用数组字符串、正则两种方法...

2986
来自专栏IT可乐

Java数据结构和算法(九)——高级排序

  春晚好看吗?不存在的!!!   在Java数据结构和算法(三)——冒泡、选择、插入排序算法中我们介绍了三种简单的排序算法,它们的时间复杂度大O表示法都是O(...

4046

扫码关注云+社区

领取腾讯云代金券