插入排序与归并排序

前言:

  排序算法应该算是算法入门级的东西了,这里重新学习算法,先暂时归纳下个人对两种算法的理解。

插入排序:

插入排序可以对应到现实生活中的排队去停车场停车的场景。假设某家饭店的饭菜十分好吃(流口水),导致来这里吃饭的人特别多,后面来吃饭准备停车的车排起了长队。每次只允许一辆车过去找位置,找到位置之后才允许下一辆车进入,依此类推,直到所有的车都停好。转换成专业的数学模型就是:现有一个无序数组 A[n],要想对其进行排序。我们先从一个数开始考虑,A0肯定是排好序的。现在假设有A1,那么这时候应该将A1和A0 进行比较排序。这时候假设再来A2,A2需要与前面排好队的A0、A1 再进行比较排序。这里需要注意的是在排序的过程中可能会产生数组的移动。下面是java代码实现的升序排列的整数版本:

 1 public static void main(String[] args) {
 2         int[] arr = {2, 1, 23, 22, 15, 76, 43, 36};
 3         ascInsertionSort(arr);
 4         System.out.println(Arrays.toString(arr));
 5     }
 6     
 7     /**
 8      * 升序插入排列
 9      * @param arr 传入的数组
10      */
11     private static void ascInsertionSort(int[] arr) {
12         int key = 0;
13         for (int j=1; j<arr.length; j++) {                // 因为如果只有一个元素根本不需要排序,所以带插入的元素的下边从1开始
14             key = arr[j];                                // 用key表示当前用来插入到已排序数组中的值
15             int i = j-1;
16             for (; i>=0; i--)
17             {    
18                 // 如果已排完序的数组的最后一个数比当前待插入的数小,说明不需要移动,直接break,否则需要交换两个比较值的元素的位置
19                 if (arr[i] > arr[i+1])                    
20                 {
21                     arr[i+1] = arr[i];
22                     arr[i] = key;
23                 }
24                 else
25                 {
26                     break;
27                 }
28             }
29         }
30     }

很容易算出该算法的耗时主要是两层for循环嵌套导致的,第一层for循环循环的次数为n次。第二层for循环每次运行的最坏的结果是需要把前面排序好的数组再全部循环一次,为:

1 + 2 + 3 + ... + (n-1) = (n2-1)/2。 我们知道对于n的多项式,随着n的增长,对多项式结果影响结果最大的其实是最高的次数的那个项。所以不难得到该算法的时间复杂度为:θ(n2)。

选择排序:

  既然讲了插入排序,顺便讲讲选择排序。选择排序简而言之就是每次选最帅的,选到最不帅的终结排序。

  java实现的代码如下:

 1 /**
 2      * 升序选择排序
 3      * 
 4      * @param arr
 5      */
 6     private static void ascSelectionSort(int[] arr) {
 7         int min;
 8         int minIndex;
 9         for (int i = 0; i < arr.length - 1; i++) {
10             min = arr[i]; // 假设最小的元素是当前就在该位置的元素
11             minIndex = i;
12             for (int j = i + 1; j < arr.length; j++) {
13                 if (arr[j] < min) // 如果有元素比最小的元素小,则将该元素的值作为最小元素的值,依次查找下去,最终找到最小元素所在的下表
14                 {
15                     min = arr[j];
16                     minIndex = j;
17                 }
18             }
19 
20             // 循环完发现最小元素的位置不是当前在该位置的元素,则交换两个元素的位置
21             if (minIndex != i) {
22                 int temp = arr[i];
23                 arr[i] = arr[minIndex];
24                 arr[minIndex] = temp;
25             }
26         }
27     }

  可以发现一个很悲伤的事实,这个算法的时间复杂度也为:θ(n2)。

归并排序:

  归并排序的思路应该是源自于递归。也就是大事化小,小事化了。既然是个大的数组,我就先分成两个。两个数组还是有点大吧,那我再每个分成两个。依此下去直到最后没一组中只剩下一个元素,这时候排序应该是很简单的事了。而每两个小组排序完了之后组成大组,由于每个大组都是排序好的,这时候合并大组就简单多了。用伪公式表示为:一个大组排序的时间 = 两个小组分别排序的时间 +  两个小组合并的时间。合并的原理也很简单,就相当于两份扑克牌,正着放的,从上到下是从小到大的顺序。首先从两份扑克中各取出一个牌,将较小的那个牌倒着放到另外个地方。再从较小的扑克牌出现的那份牌里面拿出最上面的,与刚才剩下的牌比大小,同样的道理,小的牌继续倒着放到刚刚选出来的那个牌的上面。依次类推,直到有一份牌被拿完。最后将剩下的那份牌倒过来倒着放到选出的牌堆上面,就完成了排序。

  java实现的代码如下:

 1 /**
 2      * 升序归并排列
 3      * 
 4      * @param arr
 5      */
 6     private static void ascMergeSort(int[] arr) {
 7         int startIndex = 0;
 8         int endIndex = arr.length - 1;
 9         divideConquer(arr, startIndex, endIndex);
10 
11     }
12 
13     private static void divideConquer(int[] arr, int startIndex, int endIndex) {
14         int midIndex = (startIndex + endIndex) / 2;
15         if (midIndex > startIndex) {
16             divideConquer(arr, startIndex, midIndex); // 排序前一部分
17             divideConquer(arr, midIndex + 1, endIndex); // 排序后一部分
18         }
19         mergeSortedArr(arr, startIndex, midIndex, endIndex); // 合并排序后的两个数组
20     }
21 
22     private static void mergeSortedArr(int[] arr, int startIndex, int midIndex,
23             int endIndex) {
24         int[] newArr = new int[endIndex + 1];
25         int i = startIndex;
26         int j = midIndex + 1;
27         int k = startIndex;
28         while (i <= midIndex && j <= endIndex) {
29             // 将小的放入当前位置,并且下一个比较大小的从出现小的那一组更新
30             if (arr[i] < arr[j]) {
31                 newArr[k++] = arr[i++];
32             } else {
33                 newArr[k++] = arr[j++];
34             }
35         }
36 
37         // 需要将还剩牌的那一组元素加到排序好的数组后面
38         while (i <= midIndex) {
39             newArr[k++] = arr[i++];
40         }
41         while (j <= endIndex) {
42             newArr[k++] = arr[j++];
43         }
44 
45         // 将新数组的值复制到老数组
46         for (i = startIndex; i <= endIndex; i++) {
47             arr[i] = newArr[i];
48         }
49     }

该算法具体到每一层的时间是n的一定倍数,然后从最顶层到最下面一层可分的层次为logn.所以该算法的时间复杂度为: θ(nlogn).

冒泡排序:

  因为冒泡排序不是今天的主角,所以这里不再将其代码贴出来。只是说说冒泡排序的原理:其实和选择排序有些类似,也是最小的或者最大的冒出来,不同之处在于在冒泡的过程中会发生置换,每次比较只要比较相邻的两个数即可。其时间复杂度其实和选择排序一样,这里直接跳过。

OK!算法入门之简单的排序算法到此完结!

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏熊二哥

深入入门系列--Data Structure--04树

终于有机会重新回头学习一下一直困扰自身多年的数据结构了,赶脚棒棒哒。一直以来,对数据结构的掌握基本局限于线性表,稍微对树有一丢丢了解,而对于图那基本上就是不懂(...

1709
来自专栏Scott_Mr 个人专栏

程序员进阶之算法练习(一)

3116
来自专栏HansBug's Lab

3097: Hash Killer I

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

1974
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继续Lee...

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

后缀自动机经典操作

1384
来自专栏编程

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程? 其实说起来宏就是用公式来加工零件,比如说椭圆,如果没有宏的话,我们要逐点算出曲线上的点,然后慢慢来用直线逼近,如果是个光洁度要...

1678
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继...

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

P2375 动物园

题目描述 近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决...

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

P3385 【模板】负环

题目描述 暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索 输入输出格式 输入格式: 第一行一个正整数T表示数据组数,对于每组数据: 第一行两...

2605
来自专栏智能算法

前端面试中的常见的算法问题

作者:Jack Pu 链接:www.jackpu.com/qian-duan-mian-shi-zhong-de-chang-jian-de-suan-fa-w...

4278

扫描关注云+社区