使用 Java 的 DSA - 插入排序
概述
插入排序是一种简单的排序算法。此排序算法是基于就地比较的算法,其中取出一个项目,搜索其合适的位置,并将该项目插入到该特定位置,从而增加排序列表。此算法不适用于大型数据集,因为其平均和最坏情况复杂度为 O(n2),其中 n 是项目数。
伪代码
procedure insertionSort( A : array of items ) int holePosition int valueToInsert for i = 1 to length(A) inclusive do: /* 选择要插入的值 */ valueToInsert = A[i] holePosition = i /*定位要插入元素的孔位置*/ while holePosition > 0 and A[i-1] > valueToInsert do: A[holePosition] = A[holePosition-1] holePosition = holePosition -1 end while /* 在洞的位置插入数字 */ A[holePosition] = valueToInsert end for end procedure
演示程序
package com.tutorialspoint.simplesort; import java.util.Arrays; public class InsertionSortDemo { public static void main(String[] args){ int[] sourceArray = {4,6,3,2,1,9,7}; System.out.println("Input Array: " + Arrays.toString(sourceArray)); printline(50); System.out.println("Output Array: " + Arrays.toString(insertionSort(sourceArray))); printline(50); } public static void printline(int count){ for(int i=0;i <count-1;i++){ System.out.print("="); } System.out.println("="); } public static int[] insertionSort(int[] intArray){ int valueToInsert; int holePosition; // 循环遍历所有数字 for(int i=1; i < intArray.length; i++){ // 选择要插入的值。 valueToInsert = intArray[i]; // 选择要插入数字的孔位置 holePosition = i; // 检查前一个数字是否大于要插入的值 while (holePosition > 0 && intArray[i-1] > valueToInsert){ intArray[holePosition] = intArray[holePosition-1]; holePosition--; System.out.println(" item moved :" + intArray[holePosition]); } if(holePosition!= i){ System.out.println(" item inserted :" + valueToInsert +", at position :" + holePosition); // 在洞的位置插入数字 intArray[holePosition] = valueToInsert; } System.out.println("iteration "+(i) +"#: " + Arrays.toString(intArray)); } return intArray; } }
如果我们编译并运行上述程序,则会产生以下结果 −
Input Array: [4, 6, 3, 2, 1, 9, 7] ================================================== iteration 1#: [4, 6, 3, 2, 1, 9, 7] item moved :6 item moved :4 item inserted :3, at position :0 iteration 2#: [3, 4, 6, 2, 1, 9, 7] item moved :6 item moved :4 item moved :3 item inserted :2, at position :0 iteration 3#: [2, 3, 4, 6, 1, 9, 7] item moved :6 item moved :4 item moved :3 item moved :2 item inserted :1, at position :0 iteration 4#: [1, 2, 3, 4, 6, 9, 7] iteration 5#: [1, 2, 3, 4, 6, 9, 7] item moved :9 item moved :6 item inserted :7, at position :4 iteration 6#: [1, 2, 3, 4, 7, 6, 9] Output Array: [1, 2, 3, 4, 7, 6, 9] ==================================================