排序是CODE經(jīng)常會用到的,在此做一個用JAVA實現(xiàn)的排序算法以供以后忘了的時候有備參考!
首先,在排序過程中,經(jīng)常會對數(shù)組中兩個元素進行交換,以下是交換算法:
public static void swap(int[] array, int i, int j) ...{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
} 1 選擇排序
選擇排序其實在前面已經(jīng)有一篇文章說明了,不過為了此處能講全排序算法,再次提及.
選擇排序在任何情況下都是O(n2)
public String[] selectionSort(int[] arrayA)...{
for (int i = 0; i < arrayA.length - 1; i++) ...{
int minIndex = i;
// Find smallest value
for (int j = i + 1; j < arrayA.length; j++) ...{
int e1 = arrayA[j];
int e2 = arrayA[minIndex];
// Compare two value
if (e1<e2) ...{
minIndex = j;
}
}
// Swap value if necessary
if (minIndex != i)...{
swap(arrayA,minIndex,j);
}
}
return arrayA;
} 2 冒泡排序
對于平均情況,冒泡排序的性能是O(n2)
public static void bubbleSort(int[] array...{
for(int i=0;i<array.length-1;i++)...{
boolean swapped=false;
for(int j=0;j<array.length;j++)...{
if(array[j]>array[j+1])...{
swap(array,i,j+1);
swapped=tree;
}
}
if(!swapped)...{
return;
}
}
}
3 插入排序
插入排序的最差情況性能是O(n2)
public static void insertionSort(int[] array)...{
for(int i=1;i<array.length;i++)...{
int itemToInsert=array[i];
int j=i-1;
while(j>=0)...{
if(itemToInsert<array[j])...{
array[j+1]=array[j];
j--;
}
else...{
break;
}
}
array[j+1]=itemToInsert;
}
} OK,就到這里了,這是常用的也是數(shù)據(jù)結(jié)構(gòu)上的三種排序算法,喝杯咖啡去
