道尔道闸配件:InsertionSort

package harry.algorithms;

public class InsertionSort {

    public static void insertionSort(char[] chars) {
        int n = chars.length;
        // n times. out loop
        for (int i=0; i            char cur = chars[i];
            int j = i-1;
            /**
             * swap cur to left element if the left is small than cur.
             * n-1 times. inner loop
             */
            while (j>=0 && chars[j]> cur) {
                chars[j+1] = chars[j];
                chars[j] = cur;
                j--;
            }
        }
        //the worst situation:
        //if it's sorted by desc,in the inner loop, it will execute compare operation of : sum(i) , 1<=i<=n-1, sum(i) = n(n-1)/2.
        //T(n) = O(n) = n^2.
        //and there have two times move operation with each compare operation.
        //sum(i+2) , i<=i<=n-1,  sum(i+2) = (n+4)(n-1)/2
        //T(n) = O(n) = n^2.

        //best situation:
        //if the array of chars is already sorted asc,then the inner loop don't need execute move operation, just one time compare
        //operation for each out loop. so the total compare operation : n
        //no move operation: 0
        //T(n) = O(n) = n

        //average situation:
        //
        //the probability of i in n is 1/n
        //E = sum((1/n)*i ) = (n-1)/2
        //E is math expectation
        //1. substitution the E in the formula of worst situation of compare operation: n(n-1)/2
        //result is : (n^2-4n+3)/8
        //T(n) = O(n) = n^2
        //2. move operation:
        //substitution E in move operation : (n+4)(n-1)/2
        //result is : (n^2+4n-21)/8
        //T(n) = O(n) = n^2
        

        //in almost we say T(0) and O(n) similar equal.
    }

    public static void main(String[] args){
        char[] cs = {'c','f','a','h','d','1','5','9','0'};
        insertionSort(cs);
        System.out.println(cs);

    }

}