算法說明
通常人們整理橋牌的方法是一張一張的來，將每一張牌插入到其他已經(jīng)有序的牌中的適當(dāng)位置。
在計算機的實現(xiàn)中，為了給要插入的元素騰出空間，我們需要將其與所有的元素在插入之前都向右移動一位。
算法復(fù)雜度
對于隨機排列的長度為N且主鍵不重復(fù)的數(shù)組，平均情況下插入排序需要~ N2/4次比較以及~ N2/4次交換。最壞情況下需要~ N2/2次比較和~ N2/2次交換，最好情況下需要N-1次比較和0次交換。
源代碼
package edu.princeton.cs.algs4;
import java.util.Comparator;
public class Insertion {
private Insertion() { }
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
assert isSorted(a, 0, i);
}
assert isSorted(a);
}
/**
* Rearranges the subarray a[lo..hi) in ascending order, using the natural order.
* @param a the array to be sorted
* @param lo left endpoint (inclusive)
* @param hi right endpoint (exclusive)
*/
public static void sort(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i < hi; i++) {
for (int j = i; j > lo && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
}
assert isSorted(a, lo, hi);
}
/**
* Rearranges the array in ascending order, using a comparator.
* @param a the array
* @param comparator the comparator specifying the order
*/
public static void sort(Object[] a, Comparator comparator) {
int n = a.length;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && less(a[j], a[j-1], comparator); j--) {
exch(a, j, j-1);
}
assert isSorted(a, 0, i, comparator);
}
assert isSorted(a, comparator);
}
/**
* Rearranges the subarray a[lo..hi) in ascending order, using a comparator.
* @param a the array
* @param lo left endpoint (inclusive)
* @param hi right endpoint (exclusive)
* @param comparator the comparator specifying the order
*/
public static void sort(Object[] a, int lo, int hi, Comparator comparator) {
for (int i = lo + 1; i < hi; i++) {
for (int j = i; j > lo && less(a[j], a[j-1], comparator); j--) {
exch(a, j, j-1);
}
}
assert isSorted(a, lo, hi, comparator);
}
// return a permutation that gives the elements in a[] in ascending order
// do not change the original array a[]
/**
* Returns a permutation that gives the elements in the array in ascending order.
* @param a the array
* @return a permutation {@code p[]} such that {@code a[p[0]]}, {@code a[p[1]]},
* ..., {@code a[p[n-1]]} are in ascending order
*/
public static int[] indexSort(Comparable[] a) {
int n = a.length;
int[] index = new int[n];
for (int i = 0; i < n; i++)
index[i] = i;
for (int i = 1; i < n; i++)
for (int j = i; j > 0 && less(a[index[j]], a[index[j-1]]); j--)
exch(index, j, j-1);
return index;
}
/***************************************************************************
* Helper sorting functions.
***************************************************************************/
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
// is v < w ?
private static boolean less(Object v, Object w, Comparator comparator) {
return comparator.compare(v, w) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
// exchange a[i] and a[j] (for indirect sort)
private static void exch(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
/***************************************************************************
* Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length);
}
// is the array a[lo..hi) sorted
private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i < hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
private static boolean isSorted(Object[] a, Comparator comparator) {
return isSorted(a, 0, a.length, comparator);
}
// is the array a[lo..hi) sorted
private static boolean isSorted(Object[] a, int lo, int hi, Comparator comparator) {
for (int i = lo + 1; i < hi; i++)
if (less(a[i], a[i-1], comparator)) return false;
return true;
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}
/**
* Reads in a sequence of strings from standard input; insertion sorts them;
* and prints them to standard output in ascending order.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
Insertion.sort(a);
show(a);
}
}
算法分析
程序輸入來自tiny.txt，內(nèi)容為
S O R T E X A M P L E
程序入口:
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
Insertion.sort(a);
show(a);
}
邏輯分析:
public static void sort(Comparable[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
// 第一次循環(huán)拿第二個數(shù)和第一個數(shù)比較
for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
//第二次循環(huán)拿第三個數(shù)和第二個數(shù)比較，再與第一個數(shù)比較
exch(a, j, j-1);
// 第三次循環(huán)拿第四個數(shù)和第三個數(shù)比較再與第二個數(shù)比較再與第一個數(shù)比較
// 最壞的情況就是每次都要交換，最好的情況就是每次都不用交換
}
assert isSorted(a, 0, i);
}
assert isSorted(a);
}
算法特點
- 倒置指數(shù)組中的兩個順序顛倒的元素。
- 如果數(shù)組中倒置的數(shù)量小于數(shù)組大小的某個倍數(shù)，那么我們說這個數(shù)組是部分有序的。
- 幾種典型的部分有序數(shù)組：
- 數(shù)組中的每個元素距離它的最終位置都不遠(yuǎn)。
- 一個有序的大數(shù)組接一個小數(shù)組。
- 數(shù)組中只有幾個元素的位置不正確。
- 以上數(shù)組，插入排序很有效，而選擇排序則不然。事實上，當(dāng)?shù)怪玫臄?shù)量很少時，插入排序可能是最好的算法。
