一、冒泡排序
冒泡排序是簡單的排序之一了，其大體思想就是通過與相鄰元素的比較和交換來把小的數(shù)交換到前面。這個過程類似于水泡向上升一樣，因此而得名。
舉個例子，對5,3,8,6,4這個無序序列進行冒泡排序。首先從后向前冒泡，4和6比較，把4交換到前面，序列變成5,3,8,4,6。
同理4和8交換，變成5,3,4,8,6,3和4無需交換。5和3交換，變成3,5,4,8,6,3.這樣一次冒泡就完了，把小的數(shù)3排到前面了。
對剩下的序列依次冒泡就會得到一個有序序列。冒泡排序的時間復雜度為O(n^2)。
public class SelectSort {
public static void selectSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int minIndex = 0;
for(int i=0; i minIndex = i;
for(int j=i+1; j if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) { //如果minIndex不為i，說明找到了更小的值，交換之。
swap(arr, i, minIndex);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
二、選擇排序
選擇排序的思想其實和冒泡排序有點類似，都是在一次排序后把小的元素放到前面，但是過程不同，冒泡排序是通過相鄰的比較和交換，而選擇排序是通過對整體的選擇。
舉個例子，對5,3,8,6,4這個無序序列進行簡單選擇排序，首先要選擇5以外的小數(shù)來和5交換，也就是選擇3和5交換，一次排序后就變成了3,5,8,6,4.對剩下的序列一次進行選擇和交換，終就會得到一個有序序列。
其實選擇排序可以看成冒泡排序的優(yōu)化，因為其目的相同，只是選擇排序只有在確定了小數(shù)的前提下才進行交換，大大減少了交換的次數(shù)。選擇排序的時間復雜度為O(n^2)
public class SelectSort {
public static void selectSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int minIndex = 0;
for(int i=0; i minIndex = i;
for(int j=i+1; j if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) { //如果minIndex不為i，說明找到了更小的值，交換之。
swap(arr, i, minIndex);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
三、快速排序
快速排序一聽名字就覺得很高端，在實際應用當中快速排序確實也是表現(xiàn)的排序算法。冒泡排序雖然高端，但其實其思想是來自冒泡排序，冒泡排序是通過相鄰元素的比較和交換把小的冒泡到頂端，而快速排序是比較和交換小數(shù)和大數(shù)，這樣一來不僅把小數(shù)冒泡到上面同時也把大數(shù)沉到下面。
舉個例子：對5,3,8,6,4這個無序序列進行快速排序，思路是右指針找比基準數(shù)小的，左指針找比基準數(shù)大的，交換之。
5,3,8,6,4 用5作為比較的基準，終會把5小的移動到5的左邊，比5大的移動到5的右邊。
5,3,8,6,4 首先設置i,j兩個指針分別指向兩端，j指針先掃描(思考一下為什么?)4比5小停止。然后i掃描，8比5大停止。交換i,j位置。
5,3,4,6,8 然后j指針再掃描，這時j掃描4時兩指針相遇。停止。然后交換4和基準數(shù)。
4,3,5,6,8 一次劃分后達到了左邊比5小，右邊比5大的目的。之后對左右子序列遞歸排序，終得到有序序列。
上面留下來了一個問題為什么一定要j指針先動呢?首先這也不是的，這取決于基準數(shù)的位置，因為在兩個指針相遇的時候，要交換基準數(shù)到相遇的位置。一般選取個數(shù)作為基準數(shù)，那么就是在左邊，所以相遇的數(shù)要和基準數(shù)交換，那么相遇的數(shù)一定要比基準數(shù)小。所以j指針先移動才能先找到比基準數(shù)小的數(shù)。
快速排序是不穩(wěn)定的，其時間平均時間復雜度是O(nlgn)。
public class QuickSort {
//一次劃分
public static int partition(int[] arr, int left, int right) {
int pivotKey = arr[left];
int pivotPointer = left;
while(left < right) {
while(left < right && arr[right] >= pivotKey)
right --;
while(left < right && arr[left] <= pivotKey)
left ++;
swap(arr, left, right); //把大的交換到右邊，把小的交換到左邊。
}
swap(arr, pivotPointer, left); //把pivot交換到中間
return left;
}
public static void quickSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos-1);
quickSort(arr, pivotPos+1, right);
}
public static void sort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
quickSort(arr, 0, arr.length-1);
}
public static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
其實上面的代碼還可以再優(yōu)化，上面代碼中基準數(shù)已經(jīng)在pivotKey中保存了，所以不需要每次交換都設置一個temp變量，在交換左右指針的時候只需要先后覆蓋就可以了。
這樣既能減少空間的使用還能降低賦值運算的次數(shù)。優(yōu)化代碼如下：
public class QuickSort {
public static int partition(int[] arr, int left, int right) {
int pivotKey = arr[left];
while(left < right) {
while(left < right && arr[right] >= pivotKey)
right --;
arr[left] = arr[right]; //把小的移動到左邊
while(left < right && arr[left] <= pivotKey)
left ++;
arr[right] = arr[left]; //把大的移動到右邊
}
arr[left] = pivotKey; //把pivot賦值到中間
return left;
}
public static void quickSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos-1);
quickSort(arr, pivotPos+1, right);
}
public static void sort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
quickSort(arr, 0, arr.length-1);
}
}
四、插入排序
插入排序不是通過交換位置而是通過比較找到合適的位置插入元素來達到排序的目的的。相信大家都有過打撲克牌的經(jīng)歷，特別是牌數(shù)較大的。
在分牌時可能要整理自己的牌，牌多的時候怎么整理呢?就是拿到一張牌，找到一個合適的位置插入。這個原理其實和插入排序是一樣的。
舉個例子，對5,3,8,6,4這個無序序列進行簡單插入排序，首先假設個數(shù)的位置時正確的，想一下在拿到張牌的時候，沒必要整理。
然后3要插到5前面，把5后移一位，變成3,5,8,6,4.想一下整理牌的時候應該也是這樣吧。然后8不用動，6插在8前面，8后移一位，4插在5前面，從5開始都向后移一位。
注意在插入一個數(shù)的時候要保證這個數(shù)前面的數(shù)已經(jīng)有序。簡單插入排序的時間復雜度也是O(n^2)。
public class InsertSort {
public static void insertSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
for(int i=1; i
int j = i;
int target = arr[i]; //待插入的
//后移
while(j > 0 && target < arr[j-1]) {
arr[j] = arr[j-1];
j --;
}
//插入
arr[j] = target;
}
}
}
以上就是達內(nèi)科技java培訓班的講師給大家介紹的關(guān)于java常見的排序法，大家可以在看這篇文章的同時也可以點擊我們文章下面的獲取試聽資格按鈕來獲取我們java培訓班的免費試聽資格，來免費試聽我們的java課程，和我們的講師進行面對面的交流和互動。也可以來我們的公司進行實地考察深入的了解我們達內(nèi)科技。
