数据结构与算法系列十二(插入排序)

原创
03/23 10:11
阅读数 48

1.引子

1.1.为什么要学习数据结构与算法?

有人说,数据结构与算法,计算机网络,与操作系统都一样,脱离日常开发,除了面试这辈子可能都用不到呀!

有人说,我是做业务开发的,只要熟练API,熟练框架,熟练各种中间件,写的代码不也能“飞”起来吗?

于是问题来了:为什么还要学习数据结构与算法呢?

#理由一:
	面试的时候,千万不要被数据结构与算法拖了后腿
#理由二:
	你真的愿意做一辈子CRUD Boy吗
#理由三:
	不想写出开源框架,中间件的工程师,不是好厨子

1.2.如何系统化学习数据结构与算法?

我想好了,还是需要学习数据结构与算法。但是我有两个困惑:

1.如何着手学习呢?

2.有哪些内容要学习呢?

学习方法推荐:

#学习方法
1.从基础开始,系统化学习
2.多动手,每一种数据结构与算法,都自己用代码实现出来
3.思路更重要:理解实现思想,不要背代码
4.与日常开发结合,对应应用场景

学习内容推荐:

数据结构与算法内容比较多,我们本着实用原则,学习经典的、常用的数据结构、与常用算法

#学习内容:
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
	数组、链表、栈、队列
	散列表、二叉树、堆
	跳表、图
5.常用算法
	递归、排序、二分查找
	搜索、哈希、贪心、分治
	动态规划、字符串匹配

2.考考你

上一篇:数据结构与算法系列十一(冒泡排序)中,我们详细分析了冒泡排序的核心思想,以及代码实现。如果你不记得了,可以回去再看看。学习数据结构与算法,最重要的就是理解每一种算法背后的思想,多看,有助于锻炼我们的逻辑思维分析能力。

我们这一篇的主角是:插入排序。它是时间复杂度O(n^2)家族的第二个排序算法。

#考考你:
1.你知道插入排序的核心思想吗?
2.你能用java实现插入排序吗?

3.案例

3.1.插入排序思想

假设有一个待排序序列:[4, 5, 6, 3, 2, 1]。我们需要按照升序进行排序,排序后的序列是这 样的:[1, 2, 3, 4, 5, 6]。

如何通过插入排序实现呢?

插入排序核心思想:

将待排序序列,分成两个区间:有序区间无序区间。循环遍历无序区间,依次将无序区间的元素,插入到有序区间的合适位置,所谓合适位置:就是要保证插入元素后,有序区间始终有序。

这里的关键词有:

1.待排序序列,分成:有序区间、无序区间
2.将无序区间数据,插入到有序区间的合适位置
3.有序区间始终保证有序,如下图:

3.2.插入排序代码实现

3.2.1.排序代码

/**
* 插入排序
* @param array:待排序数组
* @param n:待排序数组大小
*/
public static void sort(Integer [] array,int n) {
  // 如果排序数组规模小于等于1,直接返回
  if (n <= 1) {
      return;
  }

  // 将数据分为两个区域:
  // 有序数据区域:array[0]
  // 无序数据区域:array[1]...array[n-1]
  // 循环遍历无序区域的数据,插入到有序数据区域
  for(int i = 1; i < n; i++){
     // 临时存储待插入目标元素
     int tmp = array[i];
     // 有序区域最后一个元素下标
     int j = i - 1;
     // 从后往前查找插入位置,并移动数据
     for(; j >= 0;j--){
       if(array[j] > tmp){
          // 向后移动数据
          array[j+1] = array[j];
        }else{
            break;
         }
      }

      // 插入数据
      System.out.println("第【" + i + "】次插入排序");
      array[j+1] = tmp;
     }
}

3.2.2.测试代码

/**
 * 插入排序:
 * 1.时间复杂度:
 *      O(n^2)
 * 2.空间复杂度:
 *      O(1)是原地排序算法
 * 3.算法稳定性:
 *     是稳定排序算法
*/
public static void main(String[] args) {
 // 初始化测试数组
 Integer[] array = {4,5,6,3,2,1};
 // 排序前
 System.out.println("1.排序前数组:" + Arrays.deepToString(array));

 // 排序
 System.out.println("2.开始排序-------------------------------start");
 sort(array,array.length);

 // 排序后
 System.out.println("3.排序后数组:" + Arrays.deepToString(array));

}

测试结果:

D:\02teach\01soft\jdk8\bin\java 
com.anan.algorithm.sort.InsertSort
1.排序前数组:[6, 5, 4, 3, 2, 1]
2.开始排序-------------------------------start
第【1】次插入排序
第【2】次插入排序
第【3】次插入排序
第【4】次插入排序
第【5】次插入排序
3.排序后数组:[1, 2, 3, 4, 5, 6]

Process finished with exit code 0

4.讨论分享

#考考你答案:
1.你知道插入排序的核心思想吗?
  1.1.待排序序列,分成:有序区间、无序区间
  1.2.循环遍历无序区间元素,插入到有序区间的合适位置
  1.3.插入元素后,始终保证有序区间有序
  
2.你能用java实现插入排序吗?
  2.1.参考【3.2】节案例实现

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部