Algorithm - Insertion Sort（Java）

忘是亡心i 2022-05-23 01:18 138阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

package chimomo.learning.java.algorithm.sort;
 
 import java.util.Arrays;
 
 /**
 * @author Chimomo
 *
 * 
 * Basic Thought:
 *
 * Straight Insertion Sort is following:
 * Every time take out the first element from unordered sequence,
 * insert it into ordered sequence to make it ordered
 * until all the elements in unordered sequence inserted to ordered sequence.
 * 
 *
 * 
 * Algorithm:
 *
 * 1. The first round, scan the first two elements in the sequence,
 * and insert the second element into ordered sequence orderly.
 * 2. The second round, scan the first three elements in the sequence,
 * insert the third element into the ordered sequence orderly.
 * 3. Repeat the process to n-1 round, then all the elements are sorted.
 *
 * Straight Insertion Sort is composed of two layers of nested loops.
 * The outer loop identifies and determines the element to be compared,
 * the inner loop determines the element's final position.
 * Straight Insertion Sort compares the element with its preceding element,
 * so the outer loop started from the second element.
 * Move backward the preceding element
 * when the preceding element is bigger than the to-be-compared element,
 * continue the inner loop until find the smaller preceding element,
 * and insert the to-be-compared element after the smaller preceding element.
 *
 * Noted that, we must use a storage space to store the to-be-compared element,
 * since when a round of comparison completes,
 * we need to insert the to-be-compared element to the position
 * that preceding element is smaller than the to-be-compared element.
 * Straight Insertion Sort is like arranging cards when playing poker.
 * 
 *
 * 
 * Complexity:
 *
 * The worst time complexity of Straight Insertion Sort is O(n^2).
 * The space complexity of Straight Insertion Sort is O(1).
 * 
 *
 * 
 * Stability:
 *
 * Straight Insertion Sort is stable.
 * 
 */
 public class InsertionSort {
 
 /**
 * Straight Insertion Sort
 *
 * @param a The array to be sorted
 */
 private static void insertionSort(int[] a) {
 
 // Iterate from the second element
 for (int i = 1; i < a.length; i++) {
 
 // Store to-be-compared element
 int t = a[i];
 int j = i - 1;
 
 // Find the insertion position from the current element left side
 while (a[j] > t) {
 
 // Move backward
 a[j + 1] = a[j];
 j--;
 if (j == -1) {
 break;
 }
 }
 
 // The move-forwarded elements are already moved forward,
 // it will leave a empty position,
 // this position is the insertion point of the to-be-compared element.
 a[j + 1] = t;
 
 // Print each round of sorting
 System.out.println(Arrays.toString(a));
 }
 }
 
 /**
 * Test program
 *
 * @param args The arguments
 */
 public static void main(String[] args) {
 int[] arr = {11, 16, 22, -3, 99, 0, 16, 6, -1, 99};
 
 System.out.println("Before insertion sort:");
 System.out.println(Arrays.toString(arr));
 
 System.out.println("In insertion sort:");
 InsertionSort.insertionSort(arr);
 
 System.out.println("After insertion sort:");
 System.out.println(Arrays.toString(arr));
 }
 
 }
 
 /* ------ Running Results ------
 Before insertion sort:
 [11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
 In insertion sort:
 [11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
 [11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
 [-3, 11, 16, 22, 99, 0, 16, 6, -1, 99]
 [-3, 11, 16, 22, 99, 0, 16, 6, -1, 99]
 [-3, 0, 11, 16, 22, 99, 16, 6, -1, 99]
 [-3, 0, 11, 16, 16, 22, 99, 6, -1, 99]
 [-3, 0, 6, 11, 16, 16, 22, 99, -1, 99]
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 After insertion sort:
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 
 */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter