(二) 数据结构 - 插入排序
插入排序
这是基于就地比较的排序算法。在此，将始终维护一个子列表。例如，数组的下部保持被排序。要“插入”此排序子列表中的元素，必须找到其适当的位置，然后将其插入到该位置。因此，名称，插入排序。
依次搜索该数组，然后将未排序的项目移动并插入到已排序的子列表中（在同一数组中）。该算法不适用于大型数据集，因为其平均和最坏情况下的复杂度均为Ο(n^2)，其中n是项数。
但是在近乎有序的数组中，效率是相当的高～～！
核心思想
我们以未排序的数组为例。
插入排序比较前两个元素。
它发现14和33都已经按升序排列。目前，已排序的子列表中有14个。
插入排序前进，将33与27进行比较。
并发现33位置不正确。
它将33与27交换。它还将检查已排序子列表的所有元素。在这里，我们看到排序后的子列表只有一个元素14，而27大于14。因此，排序后的子列表在交换后仍保持排序。
到目前为止，我们在排序后的子列表中有14和27。接下来，将33与10进行比较。
这些值不是按排序的顺序。
但是，交换使27和10未排序。
因此，我们也交换它们。
我们再次交换它们。到第三次迭代结束时，我们有了一个包含4个项目的排序子列表。
我们再次交换它们。到第三次迭代结束时，我们有了一个包含4个项目的排序子列表。
该过程一直进行到所有未排序的值都包含在已排序的子列表中为止。
代码开发
实现思路
Step 1-如果它是第一个元素，则它已经排序。返回1;
Step 2-选择下一个元素
Step 3-与排序的子列表中的所有元素进行比较
Step 4-移动排序的子列表中大于待排序的值
Step 5-插入值
Step 6-重复直到列表被排序
伪代码
package com.paal.demo.c01SortingBasic;
import com.paal.demo.Sort;
import com.paal.demo.utils.SortTestHelper;
/**
* <p/>
* <li>title: 基础排序-插入排序</li>
* <li>@author: li.pan</li>
* <li>Date: 2019/11/4 1:13 下午</li>
* <li>Version: V1.0</li>
* <li>Description: </li>
*/
public class InsertionSort implements Sort {
@Override
public void sort(Integer[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
// 寻找元素arr[i]合适的插入位置
// 写法1 子列表的数据一一比较交换
// for (int j = i; j > 0; j--)
// if (arr[j] < arr[j - 1])
// SortTestHelper.swap(arr, j, j - 1);
// else
// break;
// 写法2 j-- 维护子列表
for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
SortTestHelper.swap(arr, j, j - 1);
// 写法3
// Integer e = arr[i];
// int j = i;
// for (; j > 0 && arr[j - 1] > e; j--)
// arr[j] = arr[j - 1];
// arr[j] = e;
}
}
}
/**
* 插入排序测试
*/
@Test
public void insertionSortTest() {
Integer[] integers0 = SortTestHelper.generateRandomArray(100, 0, 1000000);
Integer[] integers1 = SortTestHelper.generateRandomArray(10000, 0, 1000000);
Integer[] integers2 = SortTestHelper.generateRandomArray(100000, 0, 1000000);
System.out.println("------------------------------随机数组--------------------------------");
System.out.println("选择排序测试1数据量为100耗时: "+SortTestHelper.testSort(integers0, new SelectionSort()));
System.out.println("选择排序测试2数据量为10000耗时: "+SortTestHelper.testSort(integers1, new SelectionSort()));
System.out.println("选择排序测试3数据量为100000耗时: "+SortTestHelper.testSort(integers2, new SelectionSort()));
System.out.println("插入排序测试1数据量为100耗时: "+SortTestHelper.testSort(integers0, new InsertionSort()));
System.out.println("插入排序测试2数据量为10000耗时: "+SortTestHelper.testSort(integers1, new InsertionSort()));
System.out.println("插入排序测试3数据量为100000耗时: "+SortTestHelper.testSort(integers2, new InsertionSort()));
}
执行结果
------------------------------随机数组--------------------------------
选择排序测试1数据量为100耗排序时长为: 0.001s
选择排序测试2数据量为10000排序时长为: 0.09s
选择排序测试3数据量为100000排序时长为: 8.524s
插入排序测试1数据量为100排序时长为: 0.0s
插入排序测试2数据量为10000排序时长为: 0.001s
插入排序测试3数据量为100000排序时长为: 0.004s
正文到此结束
