排序（sort）：就是将無序的資料按照特定的規則排成有序資料（升序、降序）。
這篇文章我們來了解一下Java中常見的三種排序方式，即冒泡排序、二分查找、插入排序。
既然要排序，那麼就要考慮時間複雜度和空間複雜度這兩個因素，我們可以在System.currentTimeMillis()裡面檢視。
一、冒泡排序
1.冒泡排序思路
冒泡排序就像燒開的水一樣，裡面大的泡泡往上浮。那麼要進行冒泡排序就要從前往後周遊整個數組的元素，即從第一個元素開始周遊，将第一個元素和下一個元素進行比較，如果第一個元素大于下一個元素，則和下一個元素交換位置，繼續和下一個元素進行比較，直至小于下一個元素，進而進行循環。總的來說，就是将一個亂序的數組排成一個升序的數組。
2.冒泡排序的圖解（大數上浮法）
3.冒泡排序的具體分析
a = [2,98,-20,57,5,-7,88]
原順序：2 , 98 , -20 , 57 , 5 , -7 , 88
第一次：2 , -20 , 57 , 5 , -7 , 88 , 98
第二次：-20 , 2 , 5 , -7 , 57 , 88 , 98
第三次：-20 , 2 , -7 , 5 , 57 , 88 , 98
第四次：-20 , -7 , 2 , 5 , 57 , 88 , 98
4.冒泡排序的代碼示例
package com.simple.ex.day09;
public class Sort01 {
public static void main(String[] args) {
int[] a = {2,98,-20,57,5,-7,88};
System.out.println("排序前：");
for (int i : a) {
System.out.print(i + ", ");
}
bubbleSort(a);
System.out.println("\n排序後：") ;
for (int i : a) {
System.out.print(i + ",");
}
}
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 開始每一次兩兩比較
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[j] ^ arr[i];
arr[j] = arr[j] ^ arr[i];
}
}
程式運作結果如下：
/***
* 排序前：
* 2, 98, -20, 57, 5, -7, 88,
* 排序後：
* -20, -7, 2, 5, 57, 88, 98,
*/
二、選擇排序
1.選擇排序的思路
選擇排序即在一個亂序數組中，假設第一個元素是最小值，将第一個元素和之後的元素進行比較，直至找到真正的最小值，交換這兩個元素的位置即可。
2.選擇排序的圖解
3.選擇排序的具體分析
a = [2,98,-20,57,5,-7,88]
原順序：2 , 98 , -20 , 57 , 5 , -7 , 88
第一次：-20 , 98 , 2 , 57 , 5 , -7 , 88
第二次：-20 , -7 , 2 , 57 , 5 , 98 , 88
第三次：-20 , -7 , 2 , 57 , 5 , 98 , 88 //和第二次一樣，排序了，但未找到真正的最小值
第四次：-20 , -7 , 2 , 5 , 57 , 98 , 88
第五次：-20 , -7 , 2 , 5 , 57 , 98 , 88 //和第四次一樣，排序了，但未找到真正的最小值
第六次：-20 , -7 , 2 , 5 , 57 , 88 , 98
4.選擇排序的代碼示例
package com.simple.ex.day09;
public class Sort02 {
public static void main(String[] args) {
int[] a = {2, 98, -20, 57, 5, -7, 88};
System.out.println("排序前：");
for (int i : a) {
System.out.print(i + ", ");
}
selectSort(a);
System.out.println("\n排序後：");
for (int i : a) {
System.out.print(i + ", ");
}
}
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// j對應的下标才是最小值
min = j;
}
}
// 假設失敗，真正的最小值是min
if (min != i) {
swap(arr, min, i);
}
}
}
private static void swap(int[] arr, int i, int j) {
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[j] ^ arr[i];
arr[j] = arr[j] ^ arr[i];
}
}
程式運作結果如下：
/***
* 排序前：
* 2, 98, -20, 57, 5, -7, 88,
* 排序後：
* -20, -7, 2, 5, 57, 88, 98,
*/
三、插入排序
1.插入排序的思路
插入排序即把第一個元素看作有序數組，從第二個元素開始依次插入到這個有序數組中，插入時這個數組必須保持有序。
2.插入排序的圖解
3.插入排序的具體分析
a = [2,98,-20,57,5,-7,88]
原順序：2 , 98 , -20 , 57 , 5 , -7 , 88
第一次：2 ， 98 ， -20 ， 57 ， 5 ， -7 ， 88
第二次：-20 ， 2 ， 98 ， 57 ， 5 ， -7 ， 88
第三次：-20 ， 2 ， 57 ， 98 ， 5 ， -7 ， 88
第四次：-20 ， 2 ， 5 ， 57 ， 98 ， -7 ， 88
第五次：-20 ， -7 ， 2 ， 5 ， 57 ， 98 ， 88
第六次：-20 ， -7 ， 2 ， 5 ， 57 ， 88 ， 98
4.插入排序的代碼示例
package com.simple.ex.day09;
public class Sort03 {
public static void main(String[] args) {
int[] a = {2,98,-20,57,5,-7,88};
System.out.println("排序前：");
for (int i : a) {
System.out.print(i + ", ");
}
insertSort(a);
System.out.println("\n排序後：") ;
for (int i : a) {
System.out.print(i + ",");
}
}
public static void insertSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 取下一個元素，倒着插入，保證插入時數組一直有序
for (int j = i + 1; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[j] ^ arr[i];
arr[j] = arr[j] ^ arr[i];
}
}
程式運作結果如下：
/***
* 排序前：
* 2, 98, -20, 57, 5, -7, 88,
* 排序後：
* -20, -7, 2, 5, 57, 88, 98,
*/