一、寫在前頭
總的來說：
快速排序是用得比較廣泛的一個排序，也是經常出現的一個排序，應該重點掌握～
二、八大排序總結
2.1冒泡排序
思路：
- 倆倆交換，大的放在後面，第一次排序後最大值已在數組末尾。
- 因為倆倆交換，需要n-1趟排序，比如10個數，需要9趟排序
代碼實現要點：
- 兩個for循環，外層循環控制排序的趟數，內層循環控制比較的次數每趟過後，比較的次數都應該要減1
- 優化：如果一趟排序後也沒有交換位置，那麼該數組已有序～
//外層循環是排序的趟數
for (int i = 0; i < arrays.length -1 ; i++) {
//每比較一趟就重新初始化為0
isChange = 0;
//內層循環是當前趟數需要比較的次數
for (int j = 0; j < arrays.length - i - 1; j++) {
//前一位與後一位與前一位比較，如果前一位比後一位要大，那麼交換
if (arrays[j] > arrays[j + 1]) {
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
//如果進到這裡面了，說明發生置換了
isChange = 1;
}
}
//如果比較完一趟沒有發生置換，那麼說明已經排好序了，不需要再執行下去了
if (isChange == 0) {
break;
}
}
System.out.println("公眾號Java3y" + arrays);
2.2選擇排序
思路：
- 找到數組中最大的元素，與數組最後一位元素交換
- 當只有一個數時，則不需要選擇了，因此需要n-1趟排序，比如10個數，需要9趟排序
代碼實現要點：
- 兩個for循環，外層循環控制排序的趟數，內層循環找到當前趟數的最大值，隨後與當前趟數組最後的一位元素交換
//外層循環控制需要排序的趟數
for (int i = 0; i < arrays.length - 1; i++) {
//新的趟數、將角標重新賦值為0
pos = 0;
//內層循環控制遍歷數組的個數並得到最大數的角標
for (int j = 0; j < arrays.length - i; j++) {
if (arrays[j] > arrays[pos]) {
pos = j;
}
}
//交換
temp = arrays[pos];
arrays[pos] = arrays[arrays.length - 1 - i];
arrays[arrays.length - 1 - i] = temp;
}
System.out.println("公眾號Java3y" + arrays);
複製代碼
2.3插入排序
思路：
- 將一個元素插入到已有序的數組中，在初始時未知是否存在有序的數據，因此將元素第一個元素看成是有序的
- 與有序的數組進行比較，比它大則直接放入，比它小則移動數組元素的位置，找到個合適的位置插入
- 當只有一個數時，則不需要插入了，因此需要n-1趟排序，比如10個數，需要9趟排序
代碼實現：
- 一個for循環內嵌一個while循環實現，外層for循環控制需要排序的趟數，while循環找到合適的插入位置(並且插入的位置不能小於0)
//臨時變量
int temp;
//外層循環控制需要排序的趟數(從1開始因為將第0位看成了有序數據)
for (int i = 1; i < arrays.length; i++) {
temp = arrays[i];
//如果前一位(已排序的數據)比當前數據要大，那麼就進入循環比較[參考第二趟排序]
int j = i - 1;
while (j >= 0 && arrays[j] > temp) {
//往後退一個位置，讓當前數據與之前前位進行比較
arrays[j + 1] = arrays[j];
//不斷往前，直到退出循環
j--;
}
//退出了循環說明找到了合適的位置了，將當前數據插入合適的位置中
arrays[j + 1] = temp;
}
System.out.println("公眾號Java3y" + arrays);
複製代碼
2.4快速排序
思路：
- 在數組中找一個元素(節點)，比它小的放在節點的左邊，比它大的放在節點右邊。一趟下來，比節點小的在左邊，比節點大的在右邊。
- 不斷執行這個操作....
代碼實現：
- 快速排序用遞歸比較好寫【如果不太熟悉遞歸的同學可到：遞歸就這麼簡單】。支點取中間，使用L和R表示數組的最小和最大位置
- 不斷進行比較，直到找到比支點小(大)的數，隨後交換，不斷減小範圍～
- 遞歸L到支點前一個元素(j)(執行相同的操作,同上)
- 遞歸支點後一個元素(i)到R元素(執行相同的操作,同上)
/**
* 快速排序
*
* @param arr
* @param L 指向數組第一個元素
* @param R 指向數組最後一個元素
*/
public static void quickSort(int[] arr, int L, int R) {
int i = L;
int j = R;
//支點
int pivot = arr[(L + R) / 2];
//左右兩端進行掃描，只要兩端還沒有交替，就一直掃描
while (i <= j) {
//尋找直到比支點大的數
while (pivot > arr[i])
i++;
//尋找直到比支點小的數
while (pivot < arr[j])
j--;
//此時已經分別找到了比支點小的數(右邊)、比支點大的數(左邊)，它們進行交換
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
//上面一個while保證了第一趟排序支點的左邊比支點小，支點的右邊比支點大了。
//“左邊”再做排序，直到左邊剩下一個數(遞歸出口)
if (L < j)
quickSort(arr, L, j);
//“右邊”再做排序，直到右邊剩下一個數(遞歸出口)
if (i < R)
quickSort(arr, i, R);
}
複製代碼
2.5歸併排序
思路：
- 將兩個已排好序的數組合併成一個有序的數組。
- 將元素分隔開來，看成是有序的數組，進行比較合併
- 不斷拆分和合並，直到只有一個元素
代碼實現：
- 在第一趟排序時實質是兩個元素(看成是兩個已有序的數組)來進行合併，不斷執行這樣的操作，最終數組有序
- 拆分左邊，右邊，合併...
public static void main(String[] args) {
int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};
mergeSort(arrays, 0, arrays.length - 1);
System.out.println("公眾號：Java3y" + arrays);
}
/**
* 歸併排序
*
* @param arrays
* @param L 指向數組第一個元素
* @param R 指向數組最後一個元素
*/
public static void mergeSort(int[] arrays, int L, int R) {
//如果只有一個元素，那就不用排序了
if (L == R) {
return;
} else {
//取中間的數，進行拆分
int M = (L + R) / 2;
//左邊的數不斷進行拆分
mergeSort(arrays, L, M);
//右邊的數不斷進行拆分
mergeSort(arrays, M + 1, R);
//合併
merge(arrays, L, M + 1, R);
}
}
/**
* 合併數組
*
* @param arrays
* @param L 指向數組第一個元素
* @param M 指向數組分隔的元素
* @param R 指向數組最後的元素
*/
public static void merge(int[] arrays, int L, int M, int R) {
//左邊的數組的大小
int[] leftArray = new int[M - L];
//右邊的數組大小
int[] rightArray = new int[R - M + 1];
//往這兩個數組填充數據
for (int i = L; i < M; i++) {
leftArray[i - L] = arrays[i];
}
for (int i = M; i <= R; i++) {
rightArray[i - M] = arrays[i];
}
int i = 0, j = 0;
// arrays數組的第一個元素
int k = L;
//比較這兩個數組的值，哪個小，就往數組上放
while (i < leftArray.length && j < rightArray.length) {
//誰比較小，誰將元素放入大數組中,移動指針，繼續比較下一個
if (leftArray[i] < rightArray[j]) {
arrays[k] = leftArray[i];
i++;
k++;
} else {
arrays[k] = rightArray[j];
j++;
k++;
}
}
//如果左邊的數組還沒比較完，右邊的數都已經完了，那麼將左邊的數抄到大數組中(剩下的都是大數字)
while (i < leftArray.length) {
arrays[k] = leftArray[i];
i++;
k++;
}
//如果右邊的數組還沒比較完，左邊的數都已經完了，那麼將右邊的數抄到大數組中(剩下的都是大數字)
while (j < rightArray.length) {
arrays[k] = rightArray[j];
k++;
j++;
}
}
2.6堆排序
思路：
- 堆排序使用到了完全二叉樹的一個特性【不瞭解二叉樹的同學可到：二叉樹就這麼簡單學習一波】，根節點比左孩子和右孩子都要大，完成一次建堆的操作實質上是比較根節點和左孩子、右孩子的大小，大的交換到根節點上，直至最大的節點在樹頂
- 隨後與數組最後一位元素進行交換
- ......
代碼實現：
- 只要左子樹或右子樹大於當前根節點，則替換。替換後會導致下面的子樹發生了變化，因此同樣需要進行比較，直至各個節點實現父>子這麼一個條件
public static void main(String[] args) {
int[] arrays = {6, 3, 8, 7, 5, 1, 2, 23, 4321, 432, 3,2,34234,2134,1234,5,132423, 234, 4, 2, 4, 1, 5, 2, 5};
for (int i = 0; i < arrays.length; i++) {
//每完成一次建堆就可以排除一個元素了
maxHeapify(arrays, arrays.length - i);
//交換
int temp = arrays[0];
arrays[0] = arrays[(arrays.length - 1) - i];
arrays[(arrays.length - 1) - i] = temp;
}
System.out.println("公眾號：Java3y" + arrays);
}
/**
* 完成一次建堆，最大值在堆的頂部(根節點)
*/
public static void maxHeapify(int[] arrays, int size) {
for (int i = size - 1; i >= 0; i--) {
heapify(arrays, i, size);
}
}
/**
* 建堆
*
* @param arrays 看作是完全二叉樹
* @param currentRootNode 當前父節點位置
* @param size 節點總數
*/
public static void heapify(int[] arrays, int currentRootNode, int size) {
if (currentRootNode < size) {
//左子樹和右字數的位置
int left = 2 * currentRootNode + 1;
int right = 2 * currentRootNode + 2;
//把當前父節點位置看成是最大的
int max = currentRootNode;
if (left < size) {
//如果比當前根元素要大，記錄它的位置
if (arrays[max] < arrays[left]) {
max = left;
}
}
if (right < size) {
//如果比當前根元素要大，記錄它的位置
if (arrays[max] < arrays[right]) {
max = right;
}
}
//如果最大的不是根元素位置，那麼就交換
if (max != currentRootNode) {
int temp = arrays[max];
arrays[max] = arrays[currentRootNode];
arrays[currentRootNode] = temp;
//繼續比較，直到完成一次建堆
heapify(arrays, max, size);
}
}
}
2.7希爾排序
思路：
- 希爾排序實質上就是插入排序的增強版，希爾排序將數組分隔成n組來進行插入排序，**直至該數組宏觀上有序，**最後再進行插入排序時就不用移動那麼多次位置了～
代碼思路：
- 希爾增量一般是gap = gap / 2，只是比普通版插入排序多了這麼一個for循環罷了，難度並不大
/**
* 希爾排序
*
* @param arrays
*/
public static void shellSort(int[] arrays) {
//增量每次都/2
for (int step = arrays.length / 2; step > 0; step /= 2) {
//從增量那組開始進行插入排序，直至完畢
for (int i = step; i < arrays.length; i++) {
int j = i;
int temp = arrays[j];
// j - step 就是代表與它同組隔壁的元素
while (j - step >= 0 && arrays[j - step] > temp) {
arrays[j] = arrays[j - step];
j = j - step;
}
arrays[j] = temp;
}
}
}
2.8基數排序
思路：
- 基數排序(桶排序)：將數字切割成個、十、百、千位放入到不同的桶子裡，放一次就按桶子順序回收一次，直至最大位數的數字放完～那麼該數組就有序了
代碼實現：
- 先找到數組的最大值，然後根據最大值/10來作為循環的條件(只要>0，那麼就說明還有位數)
- 將個位、十位、...分配到桶子上，每分配一次就回收一次
public static void main(String[] args) {
int[] arrays = {6, 4322, 432, 344, 55, 234, 45, 243, 5, 2, 4, 5, 6, 7, 3245, 345, 345, 234, 68, 65};
radixSort(arrays);
System.out.println("公眾號：Java3y" + arrays);
}
public static void radixSort(int[] arrays) {
int max = findMax(arrays, 0, arrays.length - 1);
//需要遍歷的次數由數組最大值的位數來決定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arrays.length][10];
//獲取每一位數字(個、十、百、千位...分配到桶子裡)
for (int j = 0; j < arrays.length; j++) {
int num = (arrays[j] / i) % 10;
//將其放入桶子裡
buckets[j][num] = arrays[j];
}
//回收桶子裡的元素
int k = 0;
//有10個桶子
for (int j = 0; j < 10; j++) {
//對每個桶子裡的元素進行回收
for (int l = 0; l < arrays.length ; l++) {
//如果桶子裡面有元素就回收(數據初始化會為0)
if (buckets[l][j] != 0) {
arrays[k++] = buckets[l][j];
}
}
}
}
}
/**
* 遞歸，找出數組最大的值
*
* @param arrays 數組
* @param L 左邊界，第一個數
* @param R 右邊界，數組的長度
* @return
*/
public static int findMax(int[] arrays, int L, int R) {
//如果該數組只有一個數，那麼最大的就是該數組第一個值了
if (L == R) {
return arrays[L];
} else {
int a = arrays[L];
int b = findMax(arrays, L + 1, R);//找出整體的最大值
if (a > b) {
return a;
} else {
return b;
}
}
}
三、總結
對於排序的時間複雜度和穩定性網上的圖也很多很多，我就隨便找一張了(侵刪)
另外，這一週我還順帶整理一些之前零碎的Java面試資料，一併送給大家。
獲取方式：轉發＋關注後臺私信“Java面試”即可！
分享到:
閱讀更多 Java之高級架構 的文章
