直接插入排序演算法:ArrayList實現和數組實現

轉載請註明出處，謝謝！

直接插入排序演算法思想：

• 排序區間R[1..n]；
• 在排序的過程中，整個排序區間被分為兩個子區間： 有序區R[ 1 ... i-1 ]和無序區R[ i ... n ]；
• 共進行n－1趟排序，每趟排序都是把無序區的第一條記錄Ri插到有序區的合適位置上。

插入排序

• 直接插入排序
• 折半插入排序
• 二路插入排序
• 希爾排序

演算法說明

• 對於隨機排列的長度為\(N\)且主鍵不重覆的數組：
  • 平均情況下需要\(~\frac{N^2}{4}\)次比較及\(~\frac{N^2}{4}\)次交換。
  • 最壞情況下需要\(~\frac{N^2}{2}\)次比較及\(~\frac{N^2}{2}\)次交換。
  • 最好情況下需要\(N-1\)次比較及\(0\)次交換。

ArrayList實現：

import java.util.ArrayList;
import java.util.Random;

public class Charupaixu {

ArrayList<Integer> al;

public Charupaixu(int num, int bound) {
    al = new ArrayList<>(num);
    // 創建一個隨機數生成器
    Random rand = new Random();
    // 添加1-100的隨機整數
    for (int i = 0; i < num; i++) {
        al.add(new Integer(Math.abs(rand.nextInt(bound))+1));
    }
    System.out.println("The ArrayList Sort Before:\n" + al);
}

public void ZJCRSortIt() {
    System.out.println("Sorting :");
    Integer tempInt;

    for (int i = 1; i < al.size(); i++) {
        // 將a[i]插入到a[i-1] a[i-2] a[i-3] ... 中
        for (int j = i; j > 0 && (al.get(j) < al.get(j - 1)); j--) {
            tempInt = al.remove(j);
            al.add(j - 1, tempInt);
            System.out.println(al);
        }
    }
}

public static void main(String[] args) {
    Charupaixu cr = new Charupaixu(10, 100);
    cr.ZJCRSortIt();
}

}

Output：

The ArrayList Sort Before:
[10, 75, 61, 50, 17, 60, 19, 7, 73, 87]
Sorting :
[10, 75, 61, 50, 17, 60, 19, 7, 73, 87]
[10, 61, 75, 50, 17, 60, 19, 7, 73, 87]
[10, 50, 61, 75, 17, 60, 19, 7, 73, 87]
[10, 17, 50, 61, 75, 60, 19, 7, 73, 87]
[10, 17, 50, 60, 61, 75, 19, 7, 73, 87]
[10, 17, 19, 50, 60, 61, 75, 7, 73, 87]
[7, 10, 17, 19, 50, 60, 61, 75, 73, 87]
[7, 10, 17, 19, 50, 60, 61, 73, 75, 87]
[7, 10, 17, 19, 50, 60, 61, 73, 75, 87]

數組實現：

int[] a={ 50, 15, 18, 8, 40, 51, 60, 1, 1, 20, 15 };
        System.out.println("The ArrayList Before Sort is:");
        for (int k = 0; k < a.length; k++) {
            System.out.print(a[k]+", ");
        }

        System.out.println("\nSorting：");
        
        for(int i = 1;i<a.length;i++){
            
            int temp = a[i];
            int j;
            //在內層for迴圈外面聲明迴圈變數j，j能取到j不滿足迴圈條件的那個值。
            
            for (j = i; (j >0) && (a[j-1] > temp); j--) {
                a[j]=a[j-1];
            }
            
            a[j]=temp;
            
            for (int k = 0; k < a.length; k++) {
                System.out.print(a[k]+", ");
            }
            
            System.out.println();
        }
        
        
Output：

The ArrayList Before Sort is:
50, 15, 18, 8, 40, 51, 60, 1, 1, 20, 15, 
Sorting：
15, 50, 18, 8, 40, 51, 60, 1, 1, 20, 15, 
15, 18, 50, 8, 40, 51, 60, 1, 1, 20, 15, 
8, 15, 18, 50, 40, 51, 60, 1, 1, 20, 15, 
8, 15, 18, 40, 50, 51, 60, 1, 1, 20, 15, 
8, 15, 18, 40, 50, 51, 60, 1, 1, 20, 15, 
8, 15, 18, 40, 50, 51, 60, 1, 1, 20, 15, 
1, 8, 15, 18, 40, 50, 51, 60, 1, 20, 15, 
1, 1, 8, 15, 18, 40, 50, 51, 60, 20, 15, 
1, 1, 8, 15, 18, 20, 40, 50, 51, 60, 15, 
1, 1, 8, 15, 15, 18, 20, 40, 50, 51, 60, 

——@guoyangde http://www.cnblogs.com/LittleTreasureBox/p/8904016.html