#算法基础#选择和插入排序

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第二篇《选择和插入排序》,非常赞!希望对大家有帮助,大家会喜欢!

系列文章:

由快速排序到分治思想

一、选择排序

这是一种最简单的排序算法 第一步他先找到数组中最小的元素,然后将它和本数组中第一个元素交换位置。然后把剩下的n-1个数算为一个数组。继续找到其中最小的 放到第二个位置。以此往复。于是恭喜你得到了大奖,一个有序的数组。哈哈

话不多说 看代码 :

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

特性:

时间复杂度:N²

空间复杂度:N

多索引的稳定性:不稳定

应用: 程序员的日常

二、插入排序

不知道 同学喜欢打牌吗,不知道你喜不喜欢 反正我很喜欢。而插入排序的特点就和抓牌时候是一样一样的。 你先从一大堆数组中抓起一个 然后再抓起一个按大小排序。在抓起一个按大小插进去 。。。。。。。。。。。好了 你手上就是一个理好的牌(数组)了。这就是插入排序。就是这么简单。

对于这个表示不想多说 扔代码吧

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

特性:

时间复杂度:N²

空间复杂度:N

多索引的稳定性:稳定

应用: 程序员的日常

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2018-01-19

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法与数据结构

拓扑排序 ——个人理解,仅供参考

贴代码: #include <bits/stdc++.h> using namespace std; #define maxn 100//可以根据题目条件进行更...

1908
来自专栏函数式编程语言及工具

Scalaz(43)- 总结 :FP就是实用的编程模式

  完成了对Free Monad这部分内容的学习了解后,心头豁然开朗,存在心里对FP的疑虑也一扫而光。之前也抱着跟大多数人一样的主观概念,认为FP只适合学术性探...

2017
来自专栏灯塔大数据

技术 | Python从零开始系列连载(十八)

可迭代对象:在之前学习的基础上,可以简单的理解为可以用for循环遍历的,如学过的list tuple dict set str

791
来自专栏desperate633

LintCode 寻找峰值题目分析代码

相邻位置的数字是不同的 A[0] < A[1] 并且 A[n - 2] > A[n - 1] 假定P是峰值的位置则满足A[P] > A[P-1]且A[P] ...

742
来自专栏大数据文摘

正则表达式太慢?这里有一个提速100倍的方案(附代码)

1444
来自专栏编程

详解 Python的enumerate 函数

你应该在何时何地,如何使用内置的 enumerate() 函数来写出更加简洁、更加具有 Python 范儿的循环结构呢? ? Python 的 enumerat...

1727
来自专栏从流域到海域

《笨办法学Python》 第37课手记

《笨办法学Python》 第37课手记 本节课是复习课。关键字是指系统预先定义好的含有特定含义的字符串或者函数,注意你在自定义函数时不能与关键字重名。可是该课中...

16410
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet系列之 Print Lua Table

Lua中唯一的内建数据结构就是关联数组(table),平时我们使用Lua时自然也一直在和table打交道,由于Lua中table的灵活性,使其拥有了强大的数据表...

481
来自专栏magicsoar

Effective Modern C++翻译(6)-条款5:auto比显示的类型声明要更好

    在概念上说,auto关键字和它看起来一样简单,但是事实上,它要更微妙一些的。使用auto会让你在声明变量时省略掉类型,同时也会防止了手动类型声明带来的正...

18010
来自专栏数据结构与算法

牛客NOIP提高组(二)题解

好难啊,$30$分的枚举颜色dp应该比较好想把,$f[i][j]$表示第$i$个位置,填了$j$个颜色,然后先枚举一下$1$的颜色,前缀和优化一下,$O(n a...

491

扫描关注云+社区