Day_43插入排序

一. 关于插入排序

1. 排序的定义

2. 插入排序

二. 插入排序的实现过程

三. 代码实现过程

1. 插入排序核心代码

四. 代码展示

五. 数据测试

六. 总结

一. 关于插入排序

1. 排序的定义

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便，通常希望计算机中的表是按关键字有序的。排序的确切定义如下：

输入：n个记录 $R_{1},R_{2}...R_{n}$ ，对应的关键字为 $k_{1},k_{2}...k_{n}$ 。

输出:输入序列的一个重排 $R_{1}^{'},R_{2}^{'}...R_{n}^{'}$ 使得 $k_{1}^{'}\leqslant k_{2}^{'}\leqslant ...\leqslant k_{n}^{'}$ ; (其中“≤”可以换成其他的比较大小的符号)。

算法的稳定性。若待排序表中有两个元素 $R_{i}$ 和 $R_{j}$ 其对应的关键字相同即 $key_{i}=key_{j}$ ，且在排序前 $R_{i}$ 在 $R_{j}$ 的前面，若使用某一排序算法排序后， $R_{i}$ 仍然在 $R_{j}$ 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。需要注意的是，算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。对于不稳定的排序算法，只需举出一组关键字的实例，说明它的不稳定性即可。

在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类：①内部排序，是指在排序期间元素全部存放在内存中的排序；②外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。当然，并非所有的内部排序算法都要基于比较操作，事实上，基数排序就不基于比较。

每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性能而言，很难提出一种被认为是最好的算法。通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序和基数排序五大类。内部排序算法的性能取决于算法的时间复杂度和空间复杂度，而时间复杂度一般是由比较和移动的次数决定的。

2. 插入排序

插入排序是最简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法：直接插入算法，折半插入算法和希尔排序算法。

二. 插入排序的实现过程

根据上面的插入排序思想，不难得出一种最简单也最直观的直接插入排序算法。

1）查找出 $L(i)$ 在 $L[1,...i-1]$ 中的插入位置 $k$

2)将 $L[k,...i-1]$ 中的所有元素依次向后移动一个位置

3)将 $L(i)$ 复制到 $L(k)$

为了实现对 $L[1,...n]$ 的排序，可以将 $L(2)-L(n)$ 依次插入前面已排好序的子序列，初始 $L(1)$ 可以视为是一个已排好序的子序列。上述操作执行n-1次就能得到一个有序的表。插入排序在实现上通常采用就地模式(时间复杂度为O(1))，因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

三. 代码实现过程

1. 插入排序核心代码

代码就一部分，关键就是理解从i=2...n开始判断，寻找在已排好序的数组里面i的位置，并且将之前大于i的数字向后面移位，直到空出一个位置，将节点i填入即可。注意这里我们添加了哨兵位，即这个位置上面的数是所有需要排序里面最小的，若节点i一直比较到哨兵位之后，自动结束循环。

    /************************ Insertion sort. data[0] does not store a valid data. data[0].key should* be smaller than any valid key.**********************/public void insertionSort() {DataNode tempNode;int j;for (int i = 2; i < length; i++) {tempNode = data[i];//Find the position to insert.//At the same time, move other nodes.for (j = i - 1; data[j].key > tempNode.key; j--) {data[j + 1] = data[j];} // Of for j//Insert.data[j + 1] = tempNode;System.out.println("Round " + (i - 1));System.out.println(this);} // Of for i}// Of insertionSort

四. 代码展示

主类：

package Day_43;import Day_41.DataArray;public class demo1 {/************************ The entrance of the program.** @param args Not used now.**********************/public static void main(String args[]) {
//        System.out.println("\r\n-------sequentialSearchTest-------");int []paraKeyArray;paraKeyArray=new int[]{11,2,3};String[] paraContentArray = new String[]{"121","21","324"};DataArray test=new DataArray(paraKeyArray,paraContentArray);//        test.insertionSort();
//        System.out.println("Result\r\n" + test);test.insertionSortTest();}// Of main
}

调用类：(这里我包括了所有关于查找排序的代码，这样符合封装的思想)

package Day_41;
/*** Data array for searching and sorting algorithms.** @author Jian An 2569222191@qq.com.*/
public class DataArray {/*** An inner class for data nodes. The text book usually use an int value to* represent the data. I would like to use a key-value pair instead.*/class DataNode {/*** The key.*/int key;/*** The data content.*/String content;/*** ********************* The first constructor.* *********************/DataNode(int paraKey, String paraContent) {key = paraKey;content = paraContent;}// Of the first constructor/*** ********************* Overrides the method claimed in Object, the superclass of any class.* *********************/public String toString() {return "(" + key + ", " + content + ") ";}// Of toString}// Of class DataNode/*** The data array.*/DataNode[] data;/*** The length of the data array.*/int length;/*** ********************* The first constructor.** @param paraKeyArray     The array of the keys.* @param paraContentArray The array of contents.*                         *********************/public DataArray(int[] paraKeyArray, String[] paraContentArray) {length = paraKeyArray.length;data = new DataNode[length];for (int i = 0; i < length; i++) {data[i] = new DataNode(paraKeyArray[i], paraContentArray[i]);} // Of for i}// Of the first constructor/*** ********************* Overrides the method claimed in Object, the superclass of any class.* *********************/public String toString() {String resultString = "I am a data array with " + length + " items.\r\n";for (int i = 0; i < length; i++) {resultString += data[i] + " ";} // Of for ireturn resultString;}// Of toString/*** ********************* Sequential search. Attention: It is assume that the index 0 is NOT used.** @param paraKey The given key.* @return The content of the key.* *********************/public String sequentialSearch(int paraKey) {data[0].key = paraKey;int i;// Note that we do not judge i >= 0 since data[0].key = paraKey.// In this way the runtime is saved about 1/2.// This for statement is equivalent to//for (i = length - 1; data[i].key != paraKey; i--);for (i = length - 1; data[i].key != paraKey; i--) {;}//Of for ireturn data[i].content;}// Of sequentialSearch/*** ********************* Test the method.* *********************/public static void sequentialSearchTest() {int[] tempUnsortedKeys = {-1, 5, 3, 6, 10, 7, 1, 9};String[] tempContents = {"null", "if", "then", "else", "switch", "case", "for", "while"};DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);System.out.println(tempDataArray);System.out.println("Search result of 10 is: " + tempDataArray.sequentialSearch(10));System.out.println("Search result of 5 is: " + tempDataArray.sequentialSearch(5));System.out.println("Search result of 4 is: " + tempDataArray.sequentialSearch(4));}// Of sequentialSearchTest/*** ********************* Binary search. Attention: It is assume that keys are sorted in ascending* order.** @param paraKey The given key.* @return The content of the key.* *********************/public String binarySearch(int paraKey) {int tempLeft = 0;int tempRight = length - 1;int tempMiddle = (tempLeft + tempRight) / 2;while (tempLeft <= tempRight) {tempMiddle = (tempLeft + tempRight) / 2;if (data[tempMiddle].key == paraKey) {return data[tempMiddle].content;} else if (data[tempMiddle].key <= paraKey) {tempLeft = tempMiddle + 1;} else {tempRight = tempMiddle - 1;}} // Of while// Not found.return "null";}// Of binarySearch/*** ********************* Test the method.* *********************/public static void binarySearchTest() {int[] tempSortedKeys = {1, 3, 5, 6, 7, 9, 10};String[] tempContents = {"if", "then", "else", "switch", "case", "for", "while"};DataArray tempDataArray = new DataArray(tempSortedKeys, tempContents);System.out.println(tempDataArray);System.out.println("Search result of 10 is: " + tempDataArray.binarySearch(10));System.out.println("Search result of 5 is: " + tempDataArray.binarySearch(5));System.out.println("Search result of 4 is: " + tempDataArray.binarySearch(4));}// Of binarySearchTest//    ----------------------------------------------------
//    ----------------------------------------------------
//    ----------------------------------------------------/************************ The second constructor. For Hash code only. It is assumed that* paraKeyArray.length <= paraLength.** @param paraKeyArray     The array of the keys.* @param paraContentArray The array of contents.* @param paraLength       The space for the Hash table.**********************/public DataArray(int[] paraKeyArray, String[] paraContentArray, int paraLength) {// Step 1. Initialize.length = paraLength;data = new DataNode[length];for (int i = 0; i < length; i++) {data[i] = null;} // Of for i// Step 2. Fill the data.int tempPosition;for (int i = 0; i < paraKeyArray.length; i++) {// Hash.tempPosition = paraKeyArray[i] % paraLength;// Find an empty positionwhile (data[tempPosition] != null) {tempPosition = (tempPosition + 1) % paraLength;System.out.println("Collision, move forward for key " + paraKeyArray[i]);} // Of whiledata[tempPosition] = new DataNode(paraKeyArray[i], paraContentArray[i]);} // Of for i}// Of the second constructor/************************ Hash search.** @param paraKey The given key.* @return The content of the key.**********************/public String hashSearch(int paraKey) {int tempPosition = paraKey % length;while (data[tempPosition] != null) {if (data[tempPosition].key == paraKey) {return data[tempPosition].content;} // Of ifSystem.out.println("Not this one for " + paraKey);tempPosition = (tempPosition + 1) % length;} // Of whilereturn "null";}// Of hashSearch/************************ Test the method.**********************/public static void hashSearchTest() {int[] tempUnsortedKeys = { 16, 33, 38, 69, 57, 95, 86 };String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents, 19);System.out.println(tempDataArray);System.out.println("Search result of 95 is: " + tempDataArray.hashSearch(95));System.out.println("Search result of 38 is: " + tempDataArray.hashSearch(38));System.out.println("Search result of 57 is: " + tempDataArray.hashSearch(57));System.out.println("Search result of 4 is: " + tempDataArray.hashSearch(4));}// Of hashSearchTest//    ----------------------------------------------------
//    ----------------------------------------------------
//    ----------------------------------------------------/************************ Insertion sort. data[0] does not store a valid data. data[0].key should* be smaller than any valid key.**********************/public void insertionSort() {DataNode tempNode;int j;for (int i = 2; i < length; i++) {tempNode = data[i];//Find the position to insert.//At the same time, move other nodes.for (j = i - 1; data[j].key > tempNode.key; j--) {data[j + 1] = data[j];} // Of for j//Insert.data[j + 1] = tempNode;System.out.println("Round " + (i - 1));System.out.println(this);} // Of for i}// Of insertionSort/************************ Test the method.**********************/public static void insertionSortTest() {int[] tempUnsortedKeys = { -100, 5, 3, 6, 10, 7, 1, 9 };String[] tempContents = { "null", "if", "then", "else", "switch", "case", "for", "while" };DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);System.out.println(tempDataArray);tempDataArray.insertionSort();System.out.println("Result\r\n" + tempDataArray);}// Of insertionSortTest}// Of class DataArray