道尔道闸配件:InsertionSort
来源:百度文库 编辑:九乡新闻网 时间:2024/10/06 15:01:01
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);
}
}
public class InsertionSort {
public static void insertionSort(char[] chars) {
int n = chars.length;
// n times. out loop
for (int i=0; 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);
}
}