冒泡排序
是一種比較并交換排序方式。兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序的記錄為止。
private void sort(int[] arr){
for (int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
if (arr[i] > arr[j]){
swap(arr,i,j );
}
}
}
}
protected void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private void sort2(int[] arr){
for (int i = 0; i < arr.length; i++) {
for (int j = arr.length - 2; j >= i ; j--) {
if (arr[j] > arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
選擇排序
每一趟從待排序的記錄中選出最小的元素，順序放在已排好序的序列起始位置，直到全部記錄排序完畢。
public void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int index = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[index] > arr[j]){
index = j;
}
}
swap(arr,index,i);
}
}
直接插入排序
將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)。
public void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i -1]){
int tmp = arr[i];
int j;
for (j = i-1; j >=0 && arr[j] > tmp ; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = tmp;
}
}
}
希爾排序
又稱為縮小增量排序。把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。
public void sort(int[] arr) {
//增量插入排序
int increment = arr.length;
do {
increment = increment / 3 + 1;
for (int i = increment; i < arr.length; i+=increment) {
if (arr[i] < arr[i - increment]){
int tmp = arr[i];
int j;
for (j = i - increment; j >= 0 && arr[j] > tmp; j-=increment) {
arr[j + increment] = arr[j];
}
arr[j+increment] = tmp;
}
}
}while (increment > 1);
}
堆排序
將待排序序列構(gòu)造成一個大頂堆，此時，整個序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。如此反復(fù)執(zhí)行，便得到一個有序序列。
public void sort(int[] arr) {
int n = (arr.length - 1)/2;
for (int i = n; i >= 0 ; i--) {
maxHeap(arr,i,arr.length - 1);
}
for (int i = arr.length - 1; i >= 0; i--) {
swap(arr,0,i);
maxHeap(arr,0,i);
}
}
private void maxHeap(int[] arr, int i, int count) {
int j = 2 * i + 1;
int tmp = arr[i];
while (j < count){
if (j + 1 < count && arr[j] < arr[j + 1]){
j++;
}
if (arr[j] <= tmp){
break;
}
arr[i] = arr[j];
i = j;
j = 2 * i + 1;
}
arr[i] = tmp;
}
歸并排序
將待排序的數(shù)列分成若干個長度為1的子數(shù)列，然后將這些數(shù)列兩兩合并；得到若干個長度為2的有序數(shù)列，再將這些數(shù)列兩兩合并；得到若干個長度為4的有序數(shù)列，再將它們兩兩合并；直接合并成一個數(shù)列為止。
public void sort(int[] arr) {
int[] tmp = new int[arr.length];
mergeSort(arr,tmp,0,arr.length - 1);
}
private void mergeSort(int[] arr,int[] tmp, int start, int end) {
if (start < end){
int middle = (start + end)/2;
mergeSort(arr,tmp,start,middle);
mergeSort(arr,tmp,middle + 1,end);
merge(arr,tmp,start,middle,end);
}
}
private void merge(int[] arr,int[] tmp,int start, int middle, int end) {
int m = middle + 1;
int s = start;
int k = 0;
while (start <= middle && m <= end){
if (arr[start] < arr[m]){
tmp[k++] = arr[start++];
}else {
tmp[k++] = arr[m++];
}
}
while (start <= middle){
tmp[k++] = arr[start++];
}
while (m <= end){
tmp[k++] = arr[m++];
}
for (int i = 0; i < k; i++) {
arr[s + i] = tmp[i];
}
}
快速排序
選擇一個基準(zhǔn)數(shù)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分；其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小。然后，再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
public void sort(int[] arr) {
quickSort(arr,0,arr.length-1);
}
private void quickSort(int[] arr, int start, int end) {
if (start < end){
int index = quickSortPartition(arr,start,end);
quickSort(arr,start,index);
quickSort(arr,index + 1,end);
}
}
private int quickSortPartition(int[] arr, int start, int end) {
int sentry = arr[start];
while (start < end){
//從右邊開始
while (start < end && arr[end] >= sentry){
end--;
}
if (start < end){
arr[start] = arr[end];
start++;
}
while (start < end && arr[start] <= sentry){
start++;
}
if (start < end){
arr[end] = arr[start];
end--;
}
}
arr[start] = sentry;
return start;
}
算法復(fù)雜度
