直接插入排序之Java实现
一、方法一
1 package cn.com.zfc.lesson21.sort; 2 3 import java.util.Arrays; 4 5 /** 6 * 7 * @title InsertSort 8 * @describe 插入排序 9 * @author 张富昌 10 * @date 2016年10月1日下午5:12:41 11 */ 12 public class InsertSort_1 { 13 // 直接插入排序由 N-1 趟排序组成。 14 // 基本思想：将第一个元素看成一个有序子序列，再依次从第二个记录起诸葛插入到这个有序的子序列中。 15 // 一般地，将 elem[i] 插入到由 elem[0] ~ elem[i-1] 构成的有序子序列中 16 // 时间复杂度：O(n) ~ O(n^2) 17 18 public static void main(String[] args) { 19 // 声明整型数组 20 int[] array = new int[10]; 21 // 使用循环和随机数初始化数组 22 for (int i = 0; i < array.length; i++) { 23 array[i] = (int) Math.round(Math.random() * 100); 24 } 25 System.out.println("原始数组为："); 26 System.out.println(Arrays.toString(array)); 27 System.out.println("--------------------------------------"); 28 array = insertSort(array); 29 System.out.println("--------------------------------------"); 30 System.out.println("排序后的数组为："); 31 System.out.println(Arrays.toString(array)); 32 } 33 34 /** 35 * 36 * 功能：插入排序的基本思想是，将元素逐个添加到已经排序好的数组中去，同时要求，插入的元素必须在正确的位置，这样原来排序好的数组是仍然有序的。 37 * 38 * 参数：int[] array 39 * 40 * 返回类型：int[] 41 */ 42 public static int[] insertSort(int[] array) { 43 // 使用临时数组，替代原始数组 44 int[] arr = array; 45 // 临时变量 46 int temp; 47 for (int i = 1; i < arr.length; i++) { 48 System.out.println("第 " + i + "趟"); 49 for (int j = i; j >= 1; j--) { 50 // 较小的数排在前面 51 if (arr[j - 1] > arr[j]) { 52 temp = arr[j]; 53 arr[j] = arr[j - 1]; 54 arr[j - 1] = temp; 55 } else { 56 break; 57 } 58 } 59 System.out.println(Arrays.toString(arr)); 60 } 61 return arr; 62 } 63 }
运行结果：
二、方法二
1 package cn.com.zfc.lesson21.sort; 2 3 import java.util.Arrays; 4 5 /** 6 * 7 * @title InsertSort 8 * @describe 插入排序 9 * @author 张富昌 10 * @date 2016年10月1日下午5:12:41 11 */ 12 public class InsertSort_2 { 13 // 直接插入排序由 N-1 趟排序组成。 14 // 基本思想：将第一个元素看成一个有序子序列，再依次从第二个记录起诸葛插入到这个有序的子序列中。 15 // 一般地，将 elem[i] 插入到由 elem[0] ~ elem[i-1] 构成的有序子序列中 16 // 时间复杂度：O(n) ~ O(n^2) 17 18 public static void main(String[] args) { 19 // 声明整型数组 20 int[] array = new int[10]; 21 // 使用循环和随机数初始化数组 22 for (int i = 0; i < array.length; i++) { 23 array[i] = (int) Math.round(Math.random() * 100); 24 } 25 System.out.println(Arrays.toString(array)); 26 System.out.println("--------------------------------------"); 27 array = insertSort(array); 28 System.out.println("--------------------------------------"); 29 System.out.println("排序后的数组为："); 30 System.out.println(Arrays.toString(array)); 31 } 32 33 /** 34 * 35 * 功能：插入排序的基本思想是，将元素逐个添加到已经排序好的数组中去，同时要求，插入的元素必须在正确的位置，这样原来排序好的数组是仍然有序的。 36 * 37 * 参数：int[] array 38 * 39 * 返回类型：int[] 40 */ 41 public static int[] insertSort(int[] array) { 42 // 使用临时数组，替代原始数组 43 int[] arr = array; 44 int j, temp; 45 for (int i = 1; i < arr.length; i++) { 46 System.out.println("第 " + (i + 1) + "趟"); 47 if (arr[i - 1] > arr[i]) { 48 temp = arr[i]; 49 for (j = i - 1; j >= 0 && arr[j] > temp; j--) { 50 arr[j + 1] = arr[j]; 51 } 52 arr[j + 1] = temp; 53 } 54 System.out.println(Arrays.toString(arr)); 55 } 56 return arr; 57 } 58 }
运行结果：
