java中的排序算法

基本的三種排序算法，用java代碼實現(xiàn)，代碼里有原理和時間復雜度的說明，不多說，直接上代碼

public static void main(String[] args) {
int [] array = new int []{5,2,4,6,1,3}; //待排序的數(shù)組
System.out.println("Before Sort:" + Arrays.toString(array));
insertSort(array);
System.out.println("After Sort:" + Arrays.toString(array));

}

/**
* 冒泡排序的原理：每次在無序隊列里將相鄰兩個數(shù)依次進行比較，將小數(shù)調換到前面，
* 逐次比較，直至將最大的數(shù)移到最后。最將剩下的N-1個數(shù)繼續(xù)比較，將次大數(shù)移至倒數(shù)第二位。
* 依此規(guī)律，直至比較結束。
* 時間復雜度：O(N2):(n-1)*(n-2)....=n*(n-1)/2次比較,
* 交換次數(shù)最多為 n*(n-1)/2
* @param testArray
* @return
*/
public static void bubbleSort(int [] testArray){
int size = testArray.length;
for (int i = 0; i < size -1; i++) {
for (int j = 0; j < size - 1 - i; j++) {
//比較相鄰兩個數(shù)，將較大的數(shù) 移動到后方
if(testArray[j] > testArray[j + 1]){
swap(testArray,j,j+1);
}
}
}
}

/**
* 選擇排序的原理：每次循環(huán)的時候在無序隊列中“選擇”出最小值，放到有序隊列的最前
* 時間復雜度：O(N2):(n-1)*(n-2)....=n*(n-1)/2次比較,
* 交換次數(shù)最多為n-1
* @param testArray
*/
public static void selectSort(int [] testArray){
int size = testArray.length;
int min ;
for (int i = 0; i < size; i++) {
min = i; //默認當前循環(huán)的第一個為最小
for (int j = i + 1; j < size; j++) {
if(testArray[j] < testArray[min]){
min = j; //更新最小數(shù)
}
}
//一次循環(huán)完畢之后，交換最小數(shù)和第一個數(shù)的位置
if(min != i){
swap(testArray,min,i);
}
}
}

/**
* 插入排序的原理：始終定義第一個元素為有序的，將元素逐個插入到有序排列之中，
* 其特點是要不斷的 移動數(shù)據(jù)，空出一個適當?shù)奈恢?，把待插入的元素放到里面去?
* 時間復雜度：O(N2) 最理性情況為 O(N)
* @param testArray
*/
public static void insertSort(int [] testArray){
for(int i = 1; i < testArray.length; i++){
int temp = testArray[i];//被標記的值或者說是當前需要插入的值
int index = i;
//如果輪循值大于被標記值則往后移
while( index > 0 && temp < testArray[index - 1]){
testArray[index] = testArray[index - 1];
index -- ;
}
//將被標記值插入最終移出的空位置
testArray[index] = temp;
}
}

/**
* 交換數(shù)組中的兩個元素
* @param array
* @param x
* @param y
*/
private static void swap(int[] array,int x,int y){
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}