1. 冒泡排序

冒泡排序(Bubble Sort)，又被稱為氣泡排序或泡沫排序。

它是一種較簡單的排序算法。它會遍歷若干次要排序的數列，每次遍歷時，它都會從前往后依次的比較相鄰兩個數的大小；如果前者比后者大，則交換它們的位置。這樣，一次遍歷之后，最大的元素就在數列的末尾！ 采用相同的方法再次遍歷時，第二大的元素就被排列在最大元素之前。重復此操作，直到整個數列都有序為止！

相鄰元素兩兩比較，大的往后放，第一次完畢，最大值出現在了最大索引處

/** 冒泡排序基本概念是：* 依次比較相鄰的兩個數，將小數放在前面，大數放在后面。* 即在第一趟：首先比較第1個和第2個數，將小數放前，大數放后。* 然后比較第2個數和第3個數，將小數放前，大數放后，如此繼續，* 直至比較最后兩個數，將小數放前，大數放后。至此第一趟結束，* 將最大的數放到了最后。在第二趟：仍從第一對數開始比較* （因為可能由于第2個數和第3個數的交換，使得第1個數不再小于第2個數），* 將小數放前，大數放后，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），* 第二趟結束，在倒數第二的位置上得到一個新的最大數* （其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。 */ public void bubbleSort(int[] arr){for (int i = 0; i < arr.length-1; i++) {for (int j = 0; j < arr.length-1-i; j++) {if (array[j] > array[j+1]){int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}} }

下面以數列{20,40,30,10,60,50}為例，演示它的冒泡排序過程

我們先分析第1趟排序
當i=5,j=0時，a[0]

1.1 冒泡排序的時間復雜度和穩定性

1.1.1 冒泡排序時間復雜度

冒泡排序的時間復雜度是O(N2)。
假設被排序的數列中有N個數。遍歷一趟的時間復雜度是O(N)，需要遍歷多少次呢？N-1次！因此，冒泡排序的時間復雜度是O(N2)。

1.1.2 冒泡排序穩定性

冒泡排序是穩定的算法，它滿足穩定算法的定義。
算法穩定性 – 假設在數列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。則這個排序算法是穩定的！

public class BubbleSort {/** 冒泡排序** 參數說明：* a -- 待排序的數組* n -- 數組的長度*/public static void bubbleSort1(int[] a, int n) {int i,j;for (i=n-1; i>0; i--) {// 將a[0...i]中最大的數據放在末尾for (j=0; j<i; j++) {if (a[j] > a[j+1]) {// 交換a[j]和a[j+1]int tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;}}}}/** 冒泡排序(改進版)** 參數說明：* a -- 待排序的數組* n -- 數組的長度*/public static void bubbleSort2(int[] a, int n) {int i,j;int flag; // 標記for (i=n-1; i>0; i--) {flag = 0; // 初始化標記為0// 將a[0...i]中最大的數據放在末尾for (j=0; j<i; j++) {if (a[j] > a[j+1]) {// 交換a[j]和a[j+1]int tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;flag = 1; // 若發生交換，則設標記為1}}if (flag==0)break; // 若沒發生交換，則說明數列已有序。}}public static void main(String[] args) {int i;int[] a = {20,40,30,10,60,50};System.out.printf("before sort:");for (i=0; i<a.length; i++)System.out.printf("%d ", a[i]);System.out.printf("\n");bubbleSort1(a, a.length);//bubbleSort2(a, a.length);System.out.printf("after sort:");for (i=0; i<a.length; i++)System.out.printf("%d ", a[i]);System.out.printf("\n");} }

2. 選擇排序

從0索引開始，依次和后面元素比較，小的往前放，第一次完畢，最小值出現在了最小索引處

/** 選擇排序基本思路：* 把第一個元素依次和后面的所有元素進行比較。* 第一次結束后，就會有最小值出現在最前面。* 依次類推*/ public void selectSort(int[] arr){for (int i = 0; i < arr.length-1; i++) {for (int j = i+1; j < arr.length; j++) {if (arr[j] < arr[i]){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}} }

3. 插入排序

排序思想：第二個數據依次往前比較，如果發現比自己大，該數據往后瞬移，否則該數據插入找到數據的后面

/** 插入排序基本思想* 將n個元素的數列分為已有序和無序兩個部分，如插入排序過程示例下所示： 　　* {{a1}，{a2，a3，a4，…，an}} 　　* {{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}} 　* {{a1(n-1），a2(n-1) ，…},{an(n-1)}} 　　* 每次處理就是將無序數列的第一個元素與有序數列的元素從后往前逐個進行比較，* 找出插入位置，將該元素插入到有序數列的合適位置中。*/ public class AlogrithmApp {/*** @param number* @return 1 到nubmer的和*/public static int sum(int number) {if (number < 1) {throw new RuntimeException("number must > 0");}if (number == 1) {return 1;} else {return number + sum(number - 1);}}private static int counts = 0;public static void moveNumber(int panNum, char a, char b, char c) {counts++;if (panNum != 1) {moveNumber(panNum - 1, a, c, b);moveNumber(panNum - 1, b, a, c);}}public static void move(int panNum, char a, char b, char c) {if (panNum == 1) {System.out.println("盤：" + panNum + " 從 " + a + " 柱移動 " + c + " 柱");} else {move(panNum - 1, a, c, b);System.out.println("盤：" + panNum + " 從 " + a + " 柱移動 " + c + " 柱");move(panNum - 1, b, a, c);}}/*** @param args*/public static void main(String[] args) {/*moveNumber(30, 'a', 'b', 'c');System.out.println(counts);*/int datas[] = new int[100000]; //初始化數據 initData(datas); //打印數據//printData(datas); //插入排序 quickSort(datas, 0, datas.length-1);System.out.println(System.currentTimeMillis());insertSort(datas); //排序后打印 //printData(datas);System.out.println(System.currentTimeMillis());}public static void selectSort(int[] datas) {for (int i = 0; i < datas.length - 1; i++) {int minIndex = i;// 最小數據的下標for (int j = i + 1; j < datas.length; j++) {if (datas[minIndex] > datas[j]) {minIndex = j;}}int temp = datas[i];datas[i] = datas[minIndex];datas[minIndex] = temp;}}/*** 初始化數據* * @param datas*/public static void initData(int datas[]) {for (int i = 0; i < datas.length; i++) {// 隨機1到100的值datas[i] = (int) (Math.random() * 100) + 1;}}/*** 打印數據* * @param datas*/public static void printData(int datas[]) {for (int i = 0; i < datas.length; i++) {System.out.print(datas[i] + ",");}System.out.println();}public static void bubbleSort(int datas[]) {int j = 0; // 冒泡的次數int i = 0; // 每次冒泡的比較for (j = datas.length - 1; j > 0; j--) {for (i = 0; i < j; i++) {if (datas[i] > datas[i + 1]) {int temp = datas[i];datas[i] = datas[i + 1];datas[i + 1] = temp;}}}}public static void insertSort(int datas[]) {int j = 0; // 第二個數據開始插入的下標int i = 0;// 插入的次數for (i = 1; i < datas.length; i++) {int temp = datas[i];for (j = i - 1; j >= 0; j--) {if (datas[j] > temp) {datas[j + 1] = datas[j];} else {break;}}// 判斷 j == -1 或者 就是第一個小于等于temp數據的位置datas[j + 1] = temp;}}/*** 快速排序* * @param datas*/public static void quickSort(int datas[], int start, int end) {if (start >= end) {return;} else {int middle = findMiddle(datas, start, end);quickSort(datas, start, middle - 1);quickSort(datas, middle + 1, end);}}private static int findMiddle(int datas[], int start, int end) {int temp = datas[end];// 參照物int left = start - 1;int right = end;while (true) {// 1.從左邊依次找數據，找到第一個比參照大的數據while (++left < end && datas[left] <= temp);if (left == end) {//參照物是最大值break;}// 2.從右邊依次找數據，找到第一個比參數小的數據while (--right >= start && datas[right] >= temp);// 3. 比較是否出現交叉（left 和 right）if (left < right) {// 4. 如果沒有交叉，交換左右指針位置的數據int d = datas[left];datas[left] = datas[right];datas[right] = d;} else {// 5. 如果出現交叉，交換左指針和參照物的值，結束int d = datas[left];datas[left] = datas[end];datas[end] = d;break;}}return left;}}

4. 快速排序

快速排序(Quick Sort)使用分治法策略。它的基本思想是：選擇一個基準數，通過一趟排序將要排序的數據分割成獨立的兩部分；其中一部分的所有數據都比另外一部分的所有數據都要小。然后，再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

快速排序流程：

• 從數列中挑出一個基準值。
• 將所有比基準值小的擺放在基準前面，所有比基準值大的擺在基準的后面(相同的數可以到任一邊)；在這個分區退出之后，該基準就處于數列的中間位置。
• 遞歸地把”基準值前面的子數列”和”基準值后面的子數列”進行排序。

選擇一個基準數，通過一趟排序將要排序的數據分割成獨立的兩部分；其中一部分的所有數據都比另外一部分的所有數據都要小。然后，再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

package cn.itcast;/** 快速排序：* 一趟快速排序的算法是： 　　* 1）設置兩個變量i、j，排序開始的時候：i=0，j=N-1； 　　* 2）以第一個數組元素作為關鍵數據，賦值給key，即 key=A[0]； 　　* 3）從j開始向前搜索，即由后開始向前搜索（j=j-1即j--），* 找到第一個小于key的值A[j]，A[i]與A[j]交換； 　　* 4）從i開始向后搜索，即由前開始向后搜索（i=i+1即i++），* 找到第一個大于key的A[i]，A[i]與A[j]交換； 　　* 5）重復第3、4、5步，直到 I=J； * (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。* 找到并交換的時候i， j指針位置不變。* 另外當i=j這過程一定正好是i+或j-完成的最后令循環結束。） */ public class QuickSort {public static void sort(int[] data) {quickSort(data, 0, data.length - 1);}private static void quickSort(int[] data, int i, int j) {int pivotIndex = (i + j) / 2;// swapSortTest.swap(data, pivotIndex, j);int k = partition(data, i - 1, j, data[j]);SortTest.swap(data, k, j);if ((k - i) > 1)quickSort(data, i, k - 1);if ((j - k) > 1)quickSort(data, k + 1, j);}/*** @param data* @param i* @param j* @return*/private static int partition(int[] data, int l, int r, int pivot) {do {while (data[++l] < pivot);while ((r != 0) && data[--r] > pivot);SortTest.swap(data, l, r);} while (l < r);SortTest.swap(data, l, r);return l;} } /*** 快速排序** 參數說明：* a -- 待排序的數組* l -- 數組的左邊界(例如，從起始位置開始排序，則l=0)* r -- 數組的右邊界(例如，排序截至到數組末尾，則r=a.length-1)*/ public static void quickSort(int[] a, int l, int r) {if (l < r) {int i, j, x;i = l;j = r;x = a[i];while (i < j) {while (i < j && a[j] > x)j--; // 從右向左找第一個小于x的數if (i < j)a[i++] = a[j];while (i < j && a[i] < x)i++; // 從左向右找第一個大于x的數if (i < j)a[j--] = a[i];}a[i] = x;quickSort(a, l, i - 1); /* 遞歸調用 */quickSort(a, i + 1, r); /* 遞歸調用 */} }

下面以數列a={30,40,60,10,20,50}為例，演示它的快速排序過程

上圖只是給出了第1趟快速排序的流程。在第1趟中，設置x=a[i]，即x=30。
(01) 從”右 –> 左”查找小于x的數：找到滿足條件的數a[j]=20，此時j=4；然后將a[j]賦值a[i]，此時i=0；接著從左往右遍歷。
(02) 從”左 –> 右”查找大于x的數：找到滿足條件的數a[i]=40，此時i=1；然后將a[i]賦值a[j]，此時j=4；接著從右往左遍歷。
(03) 從”右 –> 左”查找小于x的數：找到滿足條件的數a[j]=10，此時j=3；然后將a[j]賦值a[i]，此時i=1；接著從左往右遍歷。
(04) 從”左 –> 右”查找大于x的數：找到滿足條件的數a[i]=60，此時i=2；然后將a[i]賦值a[j]，此時j=3；接著從右往左遍歷。
(05) 從”右 –> 左”查找小于x的數：沒有找到滿足條件的數。當i>=j時，停止查找；然后將x賦值給a[i]。此趟遍歷結束！

按照同樣的方法，對子數列進行遞歸遍歷。最后得到有序數組！

4.1 快速排序的時間復雜度和穩定性

4.1.2 快速排序穩定性

快速排序是不穩定的算法，它不滿足穩定算法的定義。
算法穩定性 – 假設在數列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。則這個排序算法是穩定的！

4.1.3 快速排序時間復雜度

快速排序的時間復雜度在最壞情況下是O(N2)，平均的時間復雜度是O(N*lgN)。
這句話很好理解：假設被排序的數列中有N個數。遍歷一次的時間復雜度是O(N)，需要遍歷多少次呢？至少lg(N+1)次，最多N次。
(01) 為什么最少是lg(N+1)次？快速排序是采用的分治法進行遍歷的，我們將它看作一棵二叉樹，它需要遍歷的次數就是二叉樹的深度，而根據完全二叉樹的定義，它的深度至少是lg(N+1)。因此，快速排序的遍歷次數最少是lg(N+1)次。
(02) 為什么最多是N次？這個應該非常簡單，還是將快速排序看作一棵二叉樹，它的深度最大是N。因此，快讀排序的遍歷次數最多是N次。

5. 堆排序

堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特征， 使得在當前無序區中選取最大（或最小）關鍵字的記錄變得簡單

5.1 用大根堆排序的基本思想 　　

• 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區 　　
• 再將關鍵字最大的記錄R[1]（即堆頂）和無序區的最后一個 記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，
  且滿足R[1..n-1].keys≤R[n].key 　　
• 由于交換后新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。
  然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最后一個記錄R[n-1]交換，
  由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，
  且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。 　
  直到無序區只有一個元素為止。 　　

5.2 大根堆排序算法的基本操作

• 初始化操作：將R[1..n]構造為初始堆
• 每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最后一個記錄交換， 然后將新的無序區調整為堆（亦稱重建堆）

package cn.itcast;public class HeapSort {public static void sort(int[] data) {MaxHeap h = new MaxHeap();h.init(data);for (int i = 0; i < data.length; i++)h.remove();System.arraycopy(h.queue, 1, data, 0, data.length);}private static class MaxHeap {void init(int[] data) {this.queue = new int[data.length + 1];for (int i = 0; i < data.length; i++) {queue[++size] = data[i];fixUp(size);}}private int size = 0;private int[] queue;public int get() {return queue[1];}public void remove() {SortTest.swap(queue, 1, size--);fixDown(1);}// fixdownprivate void fixDown(int k) {int j;while ((j = k << 1) <= size) {if (j < size && queue[j] < queue[j + 1])j++;if (queue[k] > queue[j]) // 不用交換break;SortTest.swap(queue, j, k);k = j;}}private void fixUp(int k) {while (k > 1) {int j = k >> 1;if (queue[j] > queue[k])break;SortTest.swap(queue, j, k);k = j;}}} }

6. 歸并排序

package cn.itcast;/** 歸并操作(merge)，也叫歸并算法，指的是將兩個已經排序的序列合并成一個序列的操作。 　　* 如設有數列{6，202，100，301，38，8，1} 　　* 初始狀態： [6] [202] [100] [301] [38] [8] [1] 比較次數 　　* i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]　3 　　* i=2 [ 6 100 202 301 ] [ 1 8 38 ]　4 　　* i=3　[ 1 6 8 38 100 202 301 ] 4 */ public class MergeSort {public static void sort(int[] data) {int[] temp = new int[data.length];mergeSort(data, temp, 0, data.length - 1);}private static void mergeSort(int[] data, int[] temp, int l, int r) {int mid = (l + r) / 2;if (l == r)return;mergeSort(data, temp, l, mid);mergeSort(data, temp, mid + 1, r);for (int i = l; i <= r; i++) {temp[i] = data[i];}int i1 = l;int i2 = mid + 1;for (int cur = l; cur <= r; cur++) {if (i1 == mid + 1)data[cur] = temp[i2++];else if (i2 > r)data[cur] = temp[i1++];else if (temp[i1] < temp[i2])data[cur] = temp[i1++];elsedata[cur] = temp[i2++];}} }

7. 希爾排序

package cn.itcast;/** 希爾排序：先取一個小于n的整數d1作為第一個增量，* 把文件的全部記錄分成（n除以d1）個組。所有距離為d1的倍數的記錄放在同一個組中。* 先在各組內進行直接插入排序；然后，取第二個增量d2<d1重復上述的分組和排序，* 直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。 */ public class ShellSort {public static void sort(int[] data) {for (int i = data.length / 2; i > 2; i /= 2) {for (int j = 0; j < i; j++) {insertSort(data, j, i);}}insertSort(data, 0, 1);}/*** @param data* @param j* @param i*/private static void insertSort(int[] data, int start, int inc) {for (int i = start + inc; i < data.length; i += inc) {for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {SortTest.swap(data, j, j - inc);}}} } /** 屬于插入類排序,是將整個無序列分割成若干小的子序列分別進行插入排序 　　 * 排序過程：先取一個正整數d1<n，把所有序號相隔d1的數組元素放一組，* 組內進行直接插入排序；然后取d2<d1，重復上述分組和排序操作；直至di=1， 即所有記錄放進一個組中排序為止 　　 * 初始：d=5 　　49 38 65 97 76 13 27 49 55 04 　　 * 49 13 　　|-------------------| 　　 * 38 27 |-------------------| 　　 * 65 49 　　|-------------------| 　　 * 97 55 |-------------------| 　　 * 76 04 　　|-------------------| 　　 * 一趟結果 　　13 27 49 55 04 49 38 65 97 76 　　 * d=3 　　 13 27 49 55 04 49 38 65 97 76 　　 * 13 55 38 76 |------------|------------|------------| 　　 * 27 04 65 |------------|------------| 　　 * 49 49 97 |------------|------------| 　　* 二趟結果 13 04 49* 38 27 49 55 65 97 76 　　 * d=1 　　13 04 49 38 27 49 55 65 97 76* 　　 |----|----|----|----|----|----|----|----|----| 　　 三趟結果 　　* 04 13 27 38 49 49 55 65 76 97*/ package cn.itcast;import java.util.Arrays;public class SortTest {public static void main(String[] args) {int[] arr = { 2, 5, 3, 1, 4 };System.out.println("排序前：" + Arrays.toString(arr));// InsertSort.sort(arr);// BubbleSort.sort(arr);// SelectionSort.sort(arr);// ShellSort.sort(arr);// QuickSort.sort(arr);// MergeSort.sort(arr);// HeapSort.sort(arr);System.out.println("排序后：" + Arrays.toString(arr));}/** 交換數組中的兩個元素*/public static void swap(int[] data, int i, int j) {int temp = data[i];data[i] = data[j];data[j] = temp;} }

7. 面試中的排序算法總結

總結

以上是生活随笔為你收集整理的Java数据结构与算法：排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。