《啊哈！演算法》第一章排序（Java實現）
《啊哈！演算法》第一章排序（Java實現）
前言
上一年學演算法是看視訊學習然後刷題，並沒有感受到演算法的樂趣，朋友說問了畢業的學姐，學姐說是自己對演算法感興趣一點一點琢磨的，看來興趣真的很重要，我就摒棄了原來的死板的學習方法，自己主動去鑽研。
朋友給我推薦了這本講演算法的書《啊哈！演算法》，書裏面用詳細的語言和動畫去解釋演算法的每一個步驟，很清晰，比較遺憾的就是書裡的程式碼是用C語言實現的，而我只學過Java和Python，沒有學過C語言。因此剛開始看作者講的演算法思路很清晰，但是看到舉例的程式碼之後就懵了，看不懂C寫不出Java，但後來適應了一下，演算法要的是思路，語言只是去解釋並實現思路，並且程式語言是相通的，看着C的程式碼也會給我Java程式碼提供思路，從一開始的無從下手到現在理解掌握並熟練敲完第一章的排序程式碼，這個過程樂趣無窮！
如果你也是演算法小白，對演算法的程式碼難以理解，請繼續看下去吧！在這裏我將用樸實無華的大白話向你解釋每一句程式碼！
如果恰巧你也在看這本書，把我的文章當做書本編注來看也不錯哦！我會按照書裡的目錄，每一篇文章總結書裡的一章內容。
廢話不多說了，開始吧！
桶排序
這裏是一個簡單版的桶排序，真正的桶排序要更復雜一些，但目前足夠我們用了。
題目如下：
期末考試完了老師要將同學們的分數按照從高到低排序。小哼的班上只有 5個同學，這 5個同學分別考了 5分、3分、 5分、2分和8分，考得真是慘不忍睹（滿分是 10分）。接下來將分數進行從大到小排序， 排序後是 8 5 5 3 2。你有沒有什麼好方法編寫一段程式，讓計算機隨機讀入 5個數然後將這 5個數從大到小輸出？請先想一想，至少想5分鐘再往下看吧(__) 。
思路解析：
題目可以用下面 下麪的一句話進行概括：
給你5個0~10的亂序數位，將這5個數字按照從大到小的順序進行輸出
明確題目之後，我們該怎麼做呢？
- 首先我們建立一個長度爲11的陣列
int a[] = a[11];
現在我們有了 11 個變數，編號爲 a[0]~a[10]。
- 可以發現數組的下標 0~10 正好對應我們的得分範圍 0~10 ，我們可以用陣列下標來標記分數，用陣列的值表示得分的人數，操作如下：
將 a[0]~a[10]都初始化爲0，表示這些分數都還沒有人得過。
for(int i = 0; i < a.length; i++;){ // 遍歷陣列 a.length = 11 （陣列的長度）
a[i] = 0; // 初始化爲0（即賦值爲0）
}
舉個例子：a[0] 等於 0 就表示目前還沒有人得過 0 分，同理 a[1] 等於 0 就表示目前還沒有人得過 1 分…… a[10] 等於 0 就表示目前還沒有人得過 10 分。
- 接下來對題目所給的5個得分進行處理，得分爲 8 就在 a[8] 的基礎上加 1，得分爲 5 就在 a[5] 的基礎上加 1……注意啦！第三個人的分數也是 5分，所以 a[5] 的值需要在此基礎上再增加 1，即是將 a[5] 的值從 1 改爲 2，表示 5 分出現過了兩次。
Scanner sc = new Scanner(System.in);
for(int i = 0; i < 5; i++){
int t = sc.nextInt();
a[t]++;
}
處理完 5 個得分之後，結果如下：
- 最後，我們只需要將出現過的分數列印出來就可以了，出現幾次就列印幾次。
for(int i = 0; i < a.length; i++){
for(int j = 0; j < a[i]; j++){
System.out.print(i+" ")
}
}
具體如下：
輸出結果爲：2 3 5 5 8
完整程式碼如下：
import java.util.Scanner;
public class T1 {
public static void main(String[] args) {
int a[] = new int[11];
for(int i = 0; i < a.length; i++) { // 遍歷陣列 a.length = 11 （陣列的長度）
a[i]=0; // 初始化爲0（即賦值爲0）
}
// 輸入需要排序的數位個數
System.out.println("請輸入需要排序的數位個數：");
Scanner s1 = new Scanner(System.in);
int n = s1.nextInt();
// 輸入需要排序的數位
System.out.println("請輸入需要排序的數位：");
Scanner s2 = new Scanner(System.in);
for(int i = 0; i < n; i++) { // 回圈讀入需要排序的數位
int t = s2.nextInt();
a[t]++; // 數組裏下標爲t的值+1，表示數位等於該下標的個數已經有一個了
}
for(int i = 0; i < a.length; i++) {
// 外層回圈遍歷陣列
for(int j = 1; j <= a[i]; j++) {
// 將出現過的分數列印出來，出現幾次就列印幾次。
System.out.print(i+" ");
}
}
}
}
(這裏我沒有選擇隨機生成數位，而是根據提示進行輸入，感興趣的也可以改成隨機生成數位）
執行結果如圖所示：
小總結：
這個演算法就好比有 11 個桶，編號從 0~10。每出現一個數，就在對應編號的桶中放一個 小旗子，最後只要數一數數每個桶中有幾個小旗子就 OK 了。
例如： 2 號桶中有 1 個小旗子，表示 2 出現了一次；3號桶中有 1 個小旗子，表示 3 出現了一次；5 號桶中有 2 個小旗子，表示 5 出現了兩次；8 號桶中有 1 個小旗子，表示 8 出現了一次。
桶排序的升序排序
可以發現上述程式碼實現的是將 5 個數按照從小到大的順序輸出，即 升序排序。
完整程式碼同上（再次展示一下）：
import java.util.Scanner;
public class T1 {
public static void main(String[] args) {
int a[] = new int[11];
for(int i = 0; i < a.length; i++) { // 遍歷陣列 a.length = 11 （陣列的長度）
a[i]=0; // 初始化爲0（即賦值爲0）
}
// 輸入需要排序的數位個數
System.out.println("請輸入需要排序的數位個數：");
Scanner s1 = new Scanner(System.in);
int n = s1.nextInt();
// 輸入需要排序的數位
System.out.println("請輸入需要排序的數位：");
Scanner s2 = new Scanner(System.in);
for(int i = 0; i < n; i++) { // 回圈讀入需要排序的數位
int t = s2.nextInt();
a[t]++; // 數組裏下標爲t的值+1，表示數位等於該下標的個數已經有一個了
}
for(int i = 0; i < a.length; i++) {
// 外層回圈遍歷陣列
for(int j = 1; j <= a[i]; j++) {
// 將出現過的分數列印出來，出現幾次就列印幾次。
System.out.print(i+" ");
}
}
}
}
執行結果如圖所示：
桶排序的降序排序
那麼利用桶排序進行升序排序寫完了，但是題目要求的是將 5 個數字按照從大到小的順序輸出，這該怎麼辦呢？別急，我們只需要改動一個條件即可。
如果你仔細觀察了可以發現，桶排序中決定輸出順序的關鍵就在於最後一個雙重回圈的外層回圈，外層回圈的作用是按照從0到10的順序遍歷陣列，而我們的內層回圈就是根據外層回圈讀到的下標來判斷輸出哪個數位。現在外層是升序遍歷，但是我們需要的是降序遍歷，因此只需要改動一下外層回圈的條件即可。
改動程式碼如下：
// 升序
for(int i = 0; i < a.length; i++){ // 升序從陣列的開端開始
for(int j = 0; j <= a[i]; j++){
System.out.print(i+" ");
}
}
// 降序
for(int i = a.length-1; i >= 0; i--){
// 降序從陣列的末尾開始，需要注意的是 陣列的下標最大值=陣列的長度 - 1
for(int j = 0; j <= a[i]; j++){
System.out.print(i+" ");
}
}
完整程式碼如下：
import java.util.Scanner;
public class T1 {
public static void main(String[] args) {
int a[] = new int[11];
for(int i = 0; i < a.length; i++) { // 遍歷陣列 a.length = 11 （陣列的長度）
a[i]=0; // 初始化爲0（即賦值爲0）
}
// 輸入需要排序的數位個數
System.out.println("請輸入需要排序的數位個數：");
Scanner s1 = new Scanner(System.in);
int n = s1.nextInt();
// 輸入需要排序的數位
System.out.println("請輸入需要排序的數位：");
Scanner s2 = new Scanner(System.in);
for(int i = 0; i < n; i++) { // 回圈讀入需要排序的數位
int t = s2.nextInt();
a[t]++; // 數組裏下標爲t的值+1，表示數位等於該下標的個數已經有一個了
}
for(int i = a.length - 1; i >= 0; i--) {
// 外層回圈遍歷陣列
for(int j = 1; j <= a[i]; j++) {
// 將出現過的分數列印出來，出現幾次就列印幾次。
System.out.print(i+" ");
}
}
}
}
執行結果如圖所示：
時間複雜度
最後來說下時間複雜度的問題。
程式碼中第一個 for 回圈（初始化陣列的值爲0）一共回圈了 m 次（m爲桶的個數）， 第 2 個 for 回圈(回圈讀入排序的數位）一共回圈了 n 次（n爲待排序數的個數），最後一個 for 的雙重回圈一共回圈了 m+n 次。 所以整個排序演算法一共執行了 m+n+m+n次。我們用大寫字母 O來表示時間複雜度，因此該演算法的時間複雜度是 O(m+n+m+n) 即 O(2*(m+n)) 。我們在說時間複雜度的時候可以忽略較小的常數，最終桶排序的時間複雜度爲 O(m+n) 。還有一點，在表示時間複雜度的時候，n 和 m 通常用大寫字母即 O(M+N)。
注意：
需要說明的一點是：我們目前學習的簡化版桶排序演算法，其本質上還不能算是一個真正意義上的排序演算法。爲什麼呢？舉個例子：當我們的桶排序演算法遇到下面 下麪的例子就沒轍了。
現在有 5 個人的名字和分數：huhu 5 分、haha 3 分、xixi 5 分、hengheng 2 分、lala 8 分。請按照分數從高到低，輸出他們的名字。
即應該輸出：lala 、huhu 、xixi 、haha 、hengheng。
發現問題了沒有？如果使用我們剛纔簡化版的桶排序演算法僅僅是把分數進行了排序。最終輸出的也僅僅是分數，但沒有對人本身進行排序。也就是說，我們現在並不知道排序後的分數原本對應着哪一個人！不要着急，往下看——氣泡排序。
氣泡排序
氣泡排序的基本思想：每次比較兩個相鄰的元素，如果它們的順序錯誤就把它們交換過來。
舉個例子：
將 12 35 99 18 76 這 5 個數進行從大到小的排序
既然是從小到大排序，那肯定就是越小越靠後了。
首先比較第 1 位和第 2 位數位的大小，現在第 1 位是 12，第 2 位是 35。發現 12 比 35 要小，因爲我們希望越小越靠後嘛，因此需要交換這兩個數位的位置。交換之後這 5 個數字的順序是 35 12 99 18 76。同理繼續比較第 2 位和第 3 位數位的大小……直到第 4 位和第 5 位比較結束後， 5個數的順序是 35 99 18 76 12。
經過 4 次比較後我們發現小的一個數已經就位（已經在後一位，請注意 12 這個數 的移動過程），是不是很神奇？我們現在再來回憶一下剛纔比較的過程。每次都是比較相鄰的兩個數，如果後面的數比前面的數大，則交換這兩個數的位置。一直比較下去直到後兩個數比較完畢後，小的數就在最後一個了，就如同是一個氣泡，一步一步往後「翻滾」，直到最後一位。所以這個排序的方法有一個很好聽的名字 —— 氣泡排序，如下圖所示：
但其實到現在我們的排序只將 5 個數中最小的一個數字歸位了。每將一個數字歸位我們將其稱爲「一趟」。之後我們繼續重複剛纔的過程，將剩下的 4個數一一歸位。
「氣泡排序」的原理是：每一趟只能確定將一個數字歸位。即第一趟只能確定將末位上的 數（即第 5 位）歸位，第二趟只能將倒數第 2 位上的數（即第 4位元）歸位，第三趟只能將倒數第 3 位上的數（即第 3位）歸位……直到將每一個數都歸位。
小總結
如果有 n 個數進行排序，只需將 n - 1 個數歸位，也就是說要進行 n -1 趟操作。 而 「 每一趟 」 都需要從第 1 位開始進行相鄰兩個數位的比較，將較小的一個數字放在後面，比較完畢後向後挪一位繼續比較下面 下麪兩個相鄰數位的大小，重複此步驟，直到最後一個尚未歸位的數位，已經歸位的數位則無需再進行比較。
瞭解完氣泡排序是什麼，我們就開始實操吧！
氣泡排序的升序排序
題目同上：
期末考試完了老師要將同學們的分數按照從高到低排序。小哼的班上只有 5 個同學，這 5 個同學分別考了 5分、3分、 5分、2分和8分，考得真是慘不忍睹（滿分是 10 分）。接下來將分數進行從大到小排序， 排序後是 8 5 5 3 2。你有沒有什麼好方法編寫一段程式，讓計算機隨機讀入 5 個數然後將這 5個數從大到小輸出？請先想一想，至少想 5 分鐘再往下看吧(__) 。
思路解析：
題目可以用下面 下麪的一句話進行概括：
給你 5 個 0~10 的亂序數位，將這 5 個數字按照從大到小的順序進行輸出
明確題目之後，我們該怎麼做呢？
- 建立一個長度爲 5 的陣列，將需要排序的數位存到數組裏
int a[] = new int[5]; // 建立長度爲5的陣列
Scanner sc = new Scanner(System.in); // 輸入需要排序的數位
for(int i = 0; i < a.length; i++){ // 回圈讀入需要排序的數位
a[i] = sc.nextInt();
}
- 根據氣泡排序原理開始對數位進行排序
// 氣泡排序核心程式碼
// 如果有n個數，外層回圈只需要回圈n-1次，可以理解爲n個數之間的間隔數
for(int i = 0; i < a.length-1; i++) {
// j 是 i 的鄰居，是第二個數
for(int j = i+1; j < a.length-i; j++) {
// 兩個數比大小，位置錯了就換回來
if(a[i] > a[j]) {
// 交換值的方式一：中間變數法
// int t = a[j];
// a[j] = a[i];
// a[i] = t;
// 交換值的方式二：互斥或運算交換兩個數的值
a[i] = a[i]^a[j];
a[j] = a[j]^a[i];
a[i] = a[i]^a[j];
// 交換值的方式三：兩值之和
// int t = a[i] + a[j];
// a[i] = t - a[i];
// a[j] = t - a[j];
}
}
}
- 遍歷輸出陣列
// 遍歷輸出陣列方法一：直接輸出數位
for(int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
// 遍歷輸出陣列方法二：以陣列的形式輸出
System.out.print(Arrays.toString(a));
輸入： 5 3 5 2 8
第一種輸出方式： 2 3 5 5 8
第二種輸出方式： [2,3,3,5,8]
執行結果如圖所示：
氣泡排序的降序排序
那麼利用氣泡排序進行升序排序寫完了，但是題目要求的是將 5 個數字按照從大到小的順序輸出，這該怎麼辦呢？別急，我們只需要改動一個條件即可。
如果你仔細觀察了可以發現，氣泡排序中決定輸出順序的關鍵就在於氣泡排序核心程式碼的雙重回圈裡的 if 條件判斷，我們現在的 if 條件判斷是 a[i] > a[j]，即如果 a[i] > a[j]，前一個數字大於後一個數字的話，就將這兩個數位調換順序，順序調換之後，小數在前，大數在後，即升序排序。但是我們需要的是降序排序，因此只需要改動一下 if 條件判斷即可。
改動程式碼如下：
// 升序
for(int i = 0; i < a.length-1; i++) {
// j 是 i 的鄰居，是第二個數
for(int j = i+1; j < a.length-i; j++) {
// 兩個數比大小，位置錯了就換回來
if(a[i] > a[j]) {
//升序是判斷第一個數是否大於第二個數，如果大於，就把第一個數和第二個數對調位置
// 交換值的方式二：互斥或運算交換兩個數的值
a[i] = a[i]^a[j];
a[j] = a[j]^a[i];
a[i] = a[i]^a[j];
}
}
// 降序
for(int i = 0; i < a.length-1; i++) {
// j 是 i 的鄰居，是第二個數
for(int j = i+1; j < a.length-i; j++) {
// 兩個數比大小，位置錯了就換回來
if(a[i] < a[j]) {
//降序是判斷第一個數是否小於第二個數，如果小於，就把第一個數和第二個數對調位置
// 交換值的方式二：互斥或運算交換兩個數的值
a[i] = a[i]^a[j];
a[j] = a[j]^a[i];
a[i] = a[i]^a[j];
}
}
完整程式碼如下：
import java.util.Arrays;
import java.util.Scanner;
public class T2 {
public static void main(String[] args) {
// 氣泡排序
// 輸入需要排序的數位個數
System.out.println("請輸入需要排序的數位個數：");
Scanner s1 = new Scanner(System.in);
int n = s1.nextInt();
int a[] = new int[n];
// 輸入需要排序的數位
System.out.println("請輸入需要排序的數位：");
Scanner s2 = new Scanner(System.in);
for(int i = 0; i < a.length; i++) {
// 回圈把輸入的數讀到陣列中
a[i] = s2.nextInt();
}
// 氣泡排序核心程式碼
// 如果有n個數，外層回圈只需要回圈n-1次，可以理解爲n個數之間的間隔數
for(int i = 0; i < a.length; i++) {
// j 是 i 的鄰居，是第二個數
for(int j = i+1; j < a.length; j++) {
// 兩個數比大小，位置錯了就換回來
if(a[i] > a[j]) {
// 交換值的方式一：中間變數，雙斜線
// int t = a[j];
// a[j] = a[i];
// a[i] = t;
// 交換值的方式二：互斥或運算交換兩個數的值
a[i] = a[i]^a[j];
a[j] = a[j]^a[i];
a[i] = a[i]^a[j];
// 交換值的方式三：兩值之和
// int t = a[i] + a[j];
// a[i] = t - a[i];
// a[j] = t - a[j];
}
}
}
// 遍歷輸出陣列方法一
// for(int i = 0; i < a.length; i++) {
// System.out.print(a[i]+" ");
// }
// 遍歷輸出陣列方法二
System.out.print(Arrays.toString(a));
}
}
輸入： 5 3 5 2 8
第一種輸出方式： 8 5 5 3 2
第二種輸出方式： [8,5,5,3,2]
執行結果如圖所示：
時間複雜度
最後來說下時間複雜度的問題。
氣泡排序的時間複雜度是 O(N2)，這是一個非常高的時間複雜度。
注意
氣泡排序解決了桶排序浪費空間的問題，但在演算法的執行效率上卻犧牲了很多，它的時間複雜度達到了 O(N2)。 假如我 們的計算機每秒鐘可以執行 10 億次，那麼對 1 億個數進行排序，桶排序只需要 0.1 秒，而氣泡排序則需要 1 千萬秒，達到 115 天之久。
快速排序
舉個例子：
對 6 1 2 7 9 3 4 5 10 8 這 10 個數進行排序
首先在這個序列中隨便找一個數作爲基準數（不要被這個名詞嚇到了，這就是一個用來參照的數，待會兒你就知道它用來做啥了）。爲了方便，就讓第一個數 6 作爲基準數吧。接下來，需要將這個序列中所有比基準數大的數放在 6 的右邊，比基準數小的數放在 6 的左邊，類似下面 下麪這種排列：
3 1 2 5 4 6 9 7 10 8
在初始狀態下，數位 6 在序列的第 1位。我們的目標是將 6 挪到序列中間的某個位置， 假設這個位置是 k。現在就需要尋找這個 k，並且以第 k位爲分界點，左邊的數都小於等於 6， 右邊的數都大於等於 6。 想一想，你有辦法可以做到這點嗎？ 給你一個提示吧。請回憶一下氣泡排序是如何通過「交換」一步步讓每個數歸位的。此時你也可以通過 「 交換 」 的方法來達到目的。具體是如何一步步交換呢？怎樣交換才既方便又節省時間呢？
方法其實很簡單：
分別從初始序列 「 6 1 2 7 9 3 4 5 10 8 」 兩端開始 「 探測 」 。先從右往左找一個小於6的數，再從左往右找一個大於 6的數，然後交換它們。這裏可以用兩個變數 i 和 j，分別指向序列左邊和右邊。我們爲這兩個變數起個好聽的名字 「 哨兵 i 」 和 「 哨兵 j 」。剛開始的時候讓哨兵 i 指向序列的左邊（即 i = 1），指向數位 6。讓哨兵 j 指向序列的右邊（即 j = 10），指向數位 8。例：
如下圖所示：
- 首先哨兵 j 開始出動。因爲此處設定的基準數是左邊的數，所以需要讓哨兵 j 先出動， 這一點非常重要（請自己想一想爲什麼）。哨兵 j 一步一步地向左挪動（即 j–），直到找到 一個小於 6 的數停下來。接下來哨兵 i 再一步一步向右挪動（即 i++），直到找到一個大於 6 的數停下來。最後哨兵 j 停在了數位 5面前，哨兵 i 停在了數位 7 面前。
如下圖所示：
2. 現在交換哨兵 i 和哨兵 j 所指向的元素的值。交換之後的序列如下：
6 1 2 5 9 3 4 7 10 8
如下圖所示：
3. 到此，第一次交換結束。接下來哨兵 j 繼續向左挪動（再次友情提醒，每次必須是哨兵 j 先出發）。它發現了 4（比基準數 6 要小，滿足要求）之後停了下來。哨兵 i 也繼續向右挪動，他發現了 9（比基準數 6 要大，滿足要求）之後停了下來。此時再次進行交換，交換之後的序列如下：
6 1 2 5 4 3 9 7 10 8
如下圖所示：
4. 第二次交換結束，「 探測 」 繼續。哨兵 j 繼續向左挪動，他發現了 3（比基準數 6 要小， 滿足要求）之後又停了下來。哨兵 i 繼續向右移動，糟啦！此時哨兵 i 和哨兵 j 相遇了，哨兵 i 和哨兵 j 都走到 3 面前。說明此時以 6 爲基準數的 「 探測 」 結束。我們將基準數 6 和 3進行交換。交換之後的序列如下：
3 1 2 5 4 6 9 7 10 8
到此第一輪 「 探測 」 真正結束。此時以基準數 6 爲分界點，6 左邊的數都小於等於 6，6 右邊的數都大於等於 6。
回顧一下剛纔的過程，其實哨兵 j 的使命就是要找小於基準數的數， 而哨兵 i 的使命就是要找大於基準數的數，直到 i 和 j碰頭爲止。 OK，解釋完畢。現在基準數 6 已經歸位，它正好處在序列的第 6 位。此時我們已經將原來的序列，以 6 爲分界點拆分成了兩個序列，左邊的序列是 「 3 1 2 5 4 」，右邊的序列是 「 9 7 10 8 」。
可以看到 6 左邊和右邊的序列目前都還是很混亂的，我們可以按照上面的方法繼續分別處理這兩個序列，現在先來處理 6左邊的序列吧。 左邊的序列是 「 3 1 2 5 4 」，將這個序列按照上述方法以 3 爲基準數進行調整，使得 3 左邊的數都小於等於 3，3 右邊的數都大於等於 3。
哨兵 j （指向 4） 先走，遇到 2 （比基準數 3 要小， 滿足要求）之後停了下來，哨兵 i （指向 3）此時等於基準數 3， 滿足要求，此時進行交換，調整完畢之後的序列的順序如下：
2 1 3 5 4
OK，現在 3 已經歸位。接下來需要處理 3 左邊的序列 「 2 1 」 和右邊的序列 「 5 4 」。對 序列 「 2 1 」 以 2 爲基準數進行調整，處理完畢之後的序列爲 「 1 2 」，到此 2 已經歸位。序列 「1」只有一個數，也不需要進行任何處理。至此我們對序列 「 2 1 」 已全部處理完畢，得到的序列是「1 2」。序列 「 5 4 」 的處理也仿照此方法，最後得到的序列如下：
1 2 3 4 5 6 9 7 10 8
對於序列 「 9 7 10 8 」 也模擬剛纔的過程，直到不可拆分出新的子序列爲止。最終將會得到這樣的序列：
1 2 3 4 5 6 7 8 9 10
到此，排序完全結束。可以發現，快速排序的每一輪處理其實就是將這一輪的基準數歸位，直到所有的數都歸位爲止，排序就結束了。整個演算法的處理過程如下圖所示：
小總結
快速排序是改進的氣泡排序，快速排序相比氣泡排序，每次交換是跳躍式的。
快速排序每次排序的時候設定一個基準點，將小於等於基準點的數全部放到基準點的左邊，將大於等於基準點的數全部放到基準點的右邊。這樣在每次交換的時候就不會像氣泡排序一樣只能在相鄰的數之間進行交換，交換的距離就大得多了。因此總的比較和交換次數就少了，速度就提高了。
當然在壞的情況下，仍可能是相鄰的兩個數進行了交換。因此快速排序的最差時間複雜度和氣泡排序是一樣的，都是 O(N2)，它的平均時間複雜度爲 O (NlogN)。
快速排序是基於一 種叫做 「 二分 」 的思想。 之後再聊。
瞭解完氣泡排序是什麼，我們就開始實操吧！
升序排序
上題：
期末考試完了老師要將同學們的分數按照從高到低排序。小哼的班上只有 5 個同學，這 5 個同學分別考了 5分、3分、 5分、2分和8分，考得真是慘不忍睹（滿分是 10 分）。接下來將分數進行從大到小排序， 排序後是 8 5 5 3 2。你有沒有什麼好方法編寫一段程式，讓計算機隨機讀入 5 個數然後將這 5個數從大到小輸出？請先想一想，至少想 5 分鐘再往下看吧(__) 。
思路解析：
題目可以用下面 下麪的一句話進行概括：
給你 5 個 0~10 的亂序數位，將這 5 個數字按照從大到小的順序進行輸出
明確題目之後，我們該怎麼做呢？
- 建立一個長度爲 5 的陣列，並將需要排序的數位回圈讀入陣列，然後呼叫快速排序的函數（自己寫的）進行排序，最後輸出結果
// 輸入需要排序的數位個數
System.out.println("請輸入需要排序的數位個數：");
Scanner s1 = new Scanner(System.in);
int n = s1.nextInt();
int a[] = new int[n];
// 輸入需要排序的數位
System.out.println("請輸入需要排序的數位：");
Scanner s2 = new Scanner(System.in);
for(int i = 0; i < a.length; i++) {
// 回圈把輸入的數讀到陣列中
a[i] = s2.nextInt();
}
quicksort(a,0,a.length-1); // 呼叫快速排序的函數（自己寫的）進行排序
System.out.println(Arrays.toString(a)); // 輸出結果
因爲需要不斷的回圈並利用上次操作完的數據運算元字，所以我們建立一個函數名爲 quicksort 進行遞回，根據快速排序的原理講述可知，我們需要向函數傳入的參數有：陣列 a[ ] 、陣列的開端和末尾，如下：
public static void quicksort(int a[],int begin,int end){
......
}
函數的具體實現如下：
- 首先選定一端作爲分割點，爲基準數
// refer就是用來參考的基準數
int refer = a[begin];
// begin即左指針最初的位置,指向需要排序的數位的開端數位
int left = begin; // 左指針，即哨兵i
// begin即右指針最初的位置，指向需要排序的數位的末尾數位
int right = end; // 右指針，即哨兵j
- 然後使用這兩枚指針，分別從左往右，從右往左進行查詢
從左往右查詢大於基準數的值，並記錄下這個值的下標
從右往左查詢小於基準數的值，並記錄下這個值的下標
根據下標交換對應的兩個值，然後繼續尋找
// 回圈進行的條件就是左指針的下標小於右指針的下標
// 如果不符合上面的條件就說明左指針和右指針相遇了，然後跳出回圈
// 因此回圈進行的條件也可以寫成 left != right
while(left < right) { // 因爲不清楚需要回圈多少次，所以使用 while 回圈
// 快速排序（降序）：左指針找比基準數小的數位，右指針找比基準數大的數位，
// 兩個指針都找到符合要求的數位以後，左、右指針指向的數位對調，
// 這樣就可以大數在前，小數在後，矯正一次順序了
// 一定要先讓右指針走
// 如果右指針指向的數位大於基準數，並且左指針也沒有和右指針相遇，右指針就繼續向左走
while(a[right] <= refer && left < right) {
right--;
}
// 如果左指針指向的數位小於基準數，並且左指針也沒有和右指針相遇，左指針就繼續向右走
while(a[left] >= refer && left < right) {
left++;
}
// 如果右指針指向的數位大於基準數，左指針指向的數位小於基準數，
// 並且左指針也沒有和右指針相遇，則左、右指針指向的數位對調，
if(left<right) {
// 交換值的方式一：中間變數，雙斜線
int t = a[left];
a[left] = a[right];
a[right] = t;
// 交換值的方式二：互斥或運算交換兩個數的值
// a[left] = a[left]^a[right];
// a[right] = a[right]^a[left];
// a[left] = a[left]^a[right];
//
// 交換值的方式三：兩值之和
// int t = a[left] + a[right];
// a[left] = t - a[left];
// a[right] = t - a[right];
}
}
- 當兩指針相遇時，記錄相遇地點下標，交換相遇地點下標和基準數下標，
此時基準數左邊的值均爲小於基準數的值，基準數右邊均爲大於基準數的值
// 第一次基準數排序完畢以後，即左指針和右指針相遇，
// 然後基準數和陣列最開始的數位對換
a[begin] = a[left];
// 且把基準數換成左、右指針相遇的數位，
a[left] = refer;
- 然後對兩部分分別重複進行上述操作，直到排序完成
// 遞回
// 第一次基準數左邊的數位繼續重複上面排序的步驟
quicksort(a,begin,left-1);
// 第一次基準數右邊的數位繼續重複上面排序的步驟
quicksort(a,left+1,end);
完整程式碼如下：
import java.util.Arrays;
import java.util.Scanner;
public class T3 {
public static void main(String[] args) {
// 快速排序（升序排序）
// 輸入需要排序的數位個數
System.out.println("請輸入需要排序的數位個數：");
Scanner s1 = new Scanner(System.in);
int n = s1.nextInt();
int a[] = new int[n];
// 輸入需要排序的數位
System.out.println("請輸入需要排序的數位：");
Scanner s2 = new Scanner(System.in);
for(int i = 0; i < a.length; i++) {
// 回圈把輸入的數讀到陣列中
a[i] = s2.nextInt();
}
quicksort(a,0,a.length-1);
System.out.println(Arrays.toString(a));
}
public static void quicksort(int[] a,int begin,int end) {
// 防止輸入異常報錯，且如果陣列只有一個數就直接返回無需再進行排序
if(begin >= end) {
return;
}
// refer就是用來參考的基準數
int refer = a[begin];
int left = begin;
int right = end;
// 回圈進行的條件就是左指針的下標小於右指針的下標
// 如果不符合上面的條件就說明左指針和右指針相遇了，然後跳出回圈
// 因此回圈進行的條件也可以寫成 left != right
while(left < right) {
// 快速排序(升序排序):左指針找比基準數大的數位，右指針找比基準數小的數位，
// 兩個指針都找到符合要求的數位以後，左、右指針指向的數位對調，
// 這樣就可以大數在後，小數在前，矯正一次順序了
// 一定要先讓右指針走
// 如果右指針指向的數位大於基準數，並且左指針也沒有和右指針相遇，右指針就繼續向左走
while(a[right] >= refer && left < right) {
right--;
}
// 如果左指針指向的數位小於基準數，並且左指針也沒有和右指針相遇，左指針就繼續向右走
while(a[left] <= refer && left < right) {
left++;
}
// 如果右指針指向的數位小於基準數且左指針指向的數位大於基準數，
// 並且左指針也沒有和右指針相遇，則左、右指針指向的數位對調，
if(left<right) {
// 交換值的方式一：中間變數，雙斜線
int t = a[left];
a[left] = a[right];
a[right] = t;
// 交換值的方式二：互斥或運算交換兩個數的值
// a[left] = a[left]^a[right];
// a[right] = a[right]^a[left];
// a[left] = a[left]^a[right];
//
// 交換值的方式三：兩值之和
// int t = a[left] + a[right];
// a[left] = t - a[left];
// a[right] = t - a[right];
}
}
// 第一次基準數排序完畢以後，即左指針和右指針相遇，
// 然後基準數和陣列最開始的數位對換
a[begin] = a[left];
// 且把基準數換成左、右指針相遇的數位，
a[left] = refer;
// 遞回
// 第一次基準數左邊的數位繼續重複上面排序的步驟
quicksort(a,begin,left-1);
// 第一次基準數右邊的數位繼續重複上面排序的步驟
quicksort(a,left+1,end);
}
}
執行結果如下圖所示：
降序排序
那麼利用快速排序進行升序排序寫完了，但是題目要求的是將 5 個數字按照從大到小的順序輸出，這該怎麼辦呢？別急，我們只需要改動一個條件即可。
如果你仔細觀察了可以發現，快速排序中決定輸出順序的關鍵就在於左、右指針繼續前行的while回圈裡的條件，升序排序裡，左指針（哨兵 i ）負責找到比基準數大的數位，右指針（哨兵 j ）負責找到比基準數小的數位，左、右找到符合要求的數位之後將數位進行對調，這樣基準數的左邊都是比基準數小的數位，基準數的右邊都是比基準數大的數位，重複操作以後，數位就是升序排序。
但是我們需要的是降序排序，因此只需要改動一下左、右指針繼續前行的while回圈裡的條件即可，讓左指針（哨兵 i ）負責找到比基準數小的數位，右指針（哨兵 j ）負責找到比基準數大的數位，左、右找到符合要求的數位之後將數位進行對調，這樣基準數的左邊都是比基準數大的數位，基準數的右邊都是比基準數小的數位，重複操作以後，數位就是降序排序啦！
改動程式碼如下：
// 一定要先讓右指針走
// 如果右指針指向的數位小於基準數，並且左指針也沒有和右指針相遇，右指針就繼續向左走
while(a[right] <= refer && left < right) {
right--;
}
// 如果左指針指向的數位大於基準數，並且左指針也沒有和右指針相遇，左指針就繼續向右走
while(a[left] >= refer && left < right) {
left++;
}
一定要注意：
這兩個 while 回圈負責的是左、右指針可以繼續前行而不是停下來交換值！！！
完整程式碼如下：
import java.util.Arrays;
import java.util.Scanner;
public class T3 {
public static void main(String[] args) {
// 快速排序
// 輸入需要排序的數位個數
System.out.println("請輸入需要排序的數位個數：");
Scanner s1 = new Scanner(System.in);
int n = s1.nextInt();
int a[] = new int[n];
// 輸入需要排序的數位
System.out.println("請輸入需要排序的數位：");
Scanner s2 = new Scanner(System.in);
for(int i = 0; i < a.length; i++) {
// 回圈把輸入的數讀到陣列中
a[i] = s2.nextInt();
}
quicksort(a,0,a.length-1);
System.out.println(Arrays.toString(a));
}
public static void quicksort(int[] a,int begin,int end) {
// 防止輸入異常報錯，且如果陣列只有一個數就直接返回無需再進行排序
if(begin >= end) {
return;
}
// refer就是用來參考的基準數
int refer = a[begin];
int left = begin;
int right = end;
// 回圈進行的條件就是左指針的下標小於右指針的下標
// 如果不符合上面的條件就說明左指針和右指針相遇了，然後跳出回圈
// 因此回圈進行的條件也可以寫成 left != right
while(left < right) {
// 快速排序（降序）：左指針找比基準數小的數位，右指針找比基準數大的數位，
// 兩個指針都找到符合要求的數位以後，左、右指針指向的數位對調，
// 這樣就可以大數在前，小數在後，矯正一次順序了
// 一定要先讓右指針走
// 如果右指針指向的數位小於基準數，並且左指針也沒有和右指針相遇，右指針就繼續向左走
while(a[right] <= refer && left < right) {
right--;
}
// 如果左指針指向的數位大於基準數，並且左指針也沒有和右指針相遇，左指針就繼續向右走
while(a[left] >= refer && left < right) {
left++;
}
// 如果右指針指向的數位大於基準數，左指針指向的數位小於基準數，
// 並且左指針也沒有和右指針相遇，則左、右指針指向的數位對調，
if(left<right) {
// 交換值的方式一：中間變數，雙斜線
int t = a[left];
a[left] = a[right];
a[right] = t;
// 交換值的方式二：互斥或運算交換兩個數的值
// a[left] = a[left]^a[right];
// a[right] = a[right]^a[left];
// a[left] = a[left]^a[right];
//
// 交換值的方式三：兩值之和
// int t = a[left] + a[right];
// a[left] = t - a[left];
// a[right] = t - a[right];
}
}
// 第一次基準數排序完畢以後，即左指針和右指針相遇，
// 然後基準數和陣列最開始的數位對換
a[begin] = a[left];
// 且把基準數換成左、右指針相遇的數位，
a[left] = refer;
// 遞回
// 第一次基準數左邊的數位繼續重複上面排序的步驟
quicksort(a,begin,left-1);
// 第一次基準數右邊的數位繼續重複上面排序的步驟
quicksort(a,left+1,end);
}
}
執行結果如圖所示：
小總結：
快速排序就是一個優於氣泡排序的高階氣泡排序。
小哼買書
題目如圖所示：
要求：程式執行的時間限製爲 1秒。
解決這個問題的方法大致有兩種：
- 先將這 n個圖書的 ISBN號去重，再進 行從小到大排序並輸出
- 先從小到大排序，輸出的時候再去重
方法一：先去重後排序 - - 桶排序
先來看第一種方法。通過第一節的學習我們發現，桶排序稍加改動正好可以起到去重的 效果，因此我們可以使用桶排序的方法來解決此問題。
完整程式碼如下：
import java.util.Arrays;
import java.util.Scanner;
public class T4 {
public static void main(String[] args) {
// 小哼買書，利用桶排序去重
// 輸入參與調查的同學人數
System.out.println("請輸入參與調查的同學：");
Scanner sc1 = new Scanner(System.in);
int n = sc1.nextInt();
// 建立一個數組
int a[] = new int[1001];
for(int i = 0; i <= 1000; i++) {
a[i] = 0; // 初始化
}
// 輸入同學想要的所有的圖書的ISBN號
System.out.println("請輸入所有的圖書ISBN號：");
Scanner sc2 = new Scanner(System.in);
for(int i = 0; i < 10; i++) { // 回圈讀入所有圖書的ISBN號
int t = sc2.nextInt(); // 把每一個ISBN號讀到變數t中
a[t]++; // 標記出現過的ISBN號
}
int m = 0;
for(int i = 0; i <= 1000; i++) {
if(a[i] >= 1) {
m++; // 統計ISBN號的數量（無重複）
}
}
System.out.println(""); // 空行
System.out.println(m); // 輸出ISBN號的數量（無重複）
for(int i = 0; i <= 1000; i++) { // 依次判斷1~1000這個1000個桶
if(a[i] >= 1) { // 如果這個ISBN號出現過則列印出來
System.out.print(i+" ");
}
}
}
}
執行結果如圖所示：
方法二：先排序後去重 - - 氣泡排序、桶排序
第二種方法我們需要先排序再去重,排序我們可以用氣泡排序或者快速排序。
20 40 32 67 40 20 89 300 400 15
將這 10 個數從小到大排序之後爲 15 20 20 32 40 40 67 89 300 400。
接下來，我們需要在輸出的時候去掉重複的。因爲我們已經排好序，所有相同的數都會緊挨在一起，所以我們只需要在輸出的時候，預先判斷一下當前這個數 a[ i ] 與前面一個數 a[i - 1]是否相同。如果相同則表示這個數之前已經輸出過了，不用再次輸出；不同則表示這個數是第一次出現， 需要輸出這個數。
氣泡排序
完整程式碼如下：
import java.util.Scanner;
public class T5 {
/**
* @param args
*/
public static void main(String[] args) {
// 氣泡排序
// 輸入需要排序的數位個數
System.out.println("請輸入需要排序的數位個數：");
Scanner s1 = new Scanner(System.in);
int n = s1.nextInt();
int a[] = new int[1001];
// 輸入需要排序的數位
System.out.println("請輸入需要排序的數位：");
Scanner s2 = new Scanner(System.in);
for(int i = 0; i < n; i++) {
// 回圈把輸入的數讀到陣列中
a[i] = s2.nextInt();
}
// 冒泡核心程式碼
for(int i = 0; i < a.length; i++) {
for(int j = i+1; j < a.length; j++) {
if(a[i]>a[j]) {
// 交換值的方式一：中間變數，雙斜線
// int t = a[j];
// a[j] = a[i];
// a[i] = t;
// 交換值的方式二：互斥或運算交換兩個數的值
a[i] = a[i]^a[j];
a[j] = a[j]^a[i];
a[i] = a[i]^a[j];
// 交換值的方式三：兩值之和
// int t = a[i] + a[j];
// a[i] = t - a[i];
// a[j] = t - a[j];
}
}
}
int m = 0;
for(int i = 1; i < a.length; i++) {
if(a[i] != a[i-1]) {
m++;
}
}
System.out.println(" ");
System.out.println(m);
// 比較相鄰數位是否相等
for(int i = 1; i < a.length; i++) {
if(a[i] != a[i-1]) {
System.out.print(a[i]+" ");
}
}
}
}
執行結果如圖所示：
桶排序
完整程式碼如下：
import java.util.Arrays;
import java.util.Scanner;
public class T6 {
public static void main(String[] args) {
// 快速排序
System.out.println("請輸入參與調查的同學：");
Scanner sc1 = new Scanner(System.in);
int n = sc1.nextInt();
System.out.println("請輸入所有的圖書ISBN號：");
Scanner sc2 = new Scanner(System.in);
int a[] = new int[n];
for(int i = 0; i < a.length; i++) {
a[i] = sc2.nextInt();
}
quicksort(a,0,a.length-1);
int m = 1;
for(int i = 1; i < a.length; i++) {
if(a[i] != a[i-1]) {
m++;
}
}
System.out.println(" ");
System.out.println(m);
System.out.print(a[0]+" ");
for(int i = 1; i < a.length; i++) {
if(a[i] != a[i-1]) {
System.out.print(a[i]+" ");
}
}
// System.out.println(Arrays.toString(a));
}
public static void quicksort(int a[],int begin,int end) {
if(begin >= end)
return;
int refer = a[begin];
int left = begin;
int right = end;
while(left < right) {
while(a[right] >= refer && left < right) {
right--;
}
while(a[left] <= refer && left < right) {
left++;
}
if(left < right) {
// 交換值的方式一：中間變數，雙斜線
int t = a[left];
a[left] = a[right];
a[right] = t;
// 交換值的方式二：互斥或運算交換兩個數的值
// a[left] = a[left]^a[right];
// a[right] = a[right]^a[left];
// a[left] = a[left]^a[right];
//
// 交換值的方式三：兩值之和
// int t = a[left] + a[right];
// a[left] = t - a[left];
// a[right] = t - a[right];
}
}
a[begin]=a[left];
a[left]=refer;
quicksort(a,begin,left-1);
quicksort(a,left+1,end);
}
}
執行結果如圖所示：
啊呼~終於寫完了，內容很多，如果你能看到這裏，絕對是真愛了，我們一起繼續努力吧！