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

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

系列文章:

由快速排序到分治思想

一、选择排序

这是一种最简单的排序算法 第一步他先找到数组中最小的元素,然后将它和本数组中第一个元素交换位置。然后把剩下的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 条评论
登录 后参与评论

相关文章

来自专栏ml

hdu 3635 Dragon Balls (带权并查集)

Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

3466
来自专栏专知

【关关的刷题日记63】Leetcode 111 Minimum Depth of Binary Tree

关关的刷题日记63 – Leetcode 111 Minimum Depth of Binary Tree 题目 Given a binary tree, fi...

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

1267 老鼠的旅行 2012年CCC加拿大高中生信息学奥赛

题目描述 Description You are a mouse that lives in a cage in a large laboratory. 你是一...

3427
来自专栏ACM算法日常

Dijkstra(单源最短路径)-PKU1062

图论中另一个求最小生成树的的经典算法Prim算法与Dij过程极其类似,都是贪心思想。只是一个是对顶点的选择,另外一个是对边的选择。

532
来自专栏HansBug's Lab

2020: [Usaco2010 Jan]Buying Feed, II

2020: [Usaco2010 Jan]Buying Feed, II Time Limit: 3 Sec  Memory Limit: 64 MB Subm...

2657
来自专栏HansBug's Lab

1692: [Usaco2007 Dec]队列变换(BZOJ1640强化版)

1692: [Usaco2007 Dec]队列变换 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 682  So...

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

BZOJ1046: [HAOI2007]上升序列(LIS)

  对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且( ax1 < ...

843
来自专栏HansBug's Lab

1339 / 1163: [Baltic2008]Mafia

1163: [Baltic2008]Mafia Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 96  Sol...

2485
来自专栏小樱的经验随笔

BZOJ 3211: 花神游历各国【线段树区间开方问题】

3211: 花神游历各国 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 3514  Solved: 1306...

3045
来自专栏HansBug's Lab

1671: [Usaco2005 Dec]Knights of Ni 骑士

1671: [Usaco2005 Dec]Knights of Ni 骑士 Time Limit: 5 Sec  Memory Limit: 64 MB Su...

2465

扫码关注云+社区