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