插入排序与归并排序

前言:

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

插入排序:

插入排序可以对应到现实生活中的排队去停车场停车的场景。假设某家饭店的饭菜十分好吃(流口水),导致来这里吃饭的人特别多,后面来吃饭准备停车的车排起了长队。每次只允许一辆车过去找位置,找到位置之后才允许下一辆车进入,依此类推,直到所有的车都停好。转换成专业的数学模型就是:现有一个无序数组 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 条评论
登录 后参与评论

相关文章

来自专栏潇涧技术专栏

Python Data Structures - C2 Sort

参考内容: 1.Problem Solving with Python Chapter5: Search and Sorting online_link ...

621
来自专栏目标检测和深度学习

排序算法算法对比

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

3126
来自专栏Vamei实验室

纸上谈兵: 排序算法简介及其C实现

排序的目标是将一组数据 (即一个序列) 重新排列,排列后的数据符合从大到小 (或者从小到大) 的次序。这是古老但依然富有挑战的问题。Donald Knuth的经...

1829
来自专栏攻城狮的动态

简谈归并排序

3466
来自专栏计算机视觉与深度学习基础

Leetcode 134 Gas Station

There are N gas stations along a circular route, where the amount of gas at sta...

1955
来自专栏开源优测

Python3冒泡排序

Python3冒泡排序 概述 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的数列,一次比较两个元素,如果他...

3216
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

552
来自专栏人工智能LeadAI

排序算法对比、总结(Python代码)

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

3418
来自专栏后端技术探索

视觉直观感受 7 种常用的排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

702
来自专栏轮子工厂

八大排序算法稳定性分析,原来稳定性是这个意思...

2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

896

扫码关注云+社区