排序是基礎(chǔ)的算法問題，常見的排序有插入排序、冒泡排序、快速排序等，它們分別有不同的計(jì)算復(fù)雜度。插入排序和冒泡排序的復(fù)雜度為O(n^2),而快速排序的復(fù)雜度為O(nlogn)。因此，快速排序是最常用的排序方法之一，因?yàn)樗膹?fù)雜度更。然而，對(duì)簡(jiǎn)單的排序方法的理解，還是有必要的。
插入排序 (Insert Sort)
插入排序的原理是將亂序的數(shù)據(jù)依次插入有序的數(shù)組中，其中每個(gè)數(shù)據(jù)的插入，都需要遍歷一次已排好序的數(shù)組，因此會(huì)用到兩層循環(huán)嵌套，復(fù)雜度為O(n^2)
插入排序?qū)崿F(xiàn)方法
public class InsertSort {
public static int[] isort(int[] num) {
for (int i = 1; i < num.length; i++) {
int tmp = num[i];
int j;
for (j = i - 1; j >= 0 && tmp < num[j]; j--) {
num[j+1] = num[j];
}
num[j+1] = tmp;
}
return num;
}
}
冒泡排序 (Bubble Sort)
冒泡排序的原理是把亂序數(shù)據(jù)的最大值（或最小值）依次排到數(shù)組邊緣，其中每個(gè)最大值（或最小值）的排出，都要遍歷一次未排好序的數(shù)組，因此也會(huì)用到兩層循環(huán)嵌套，復(fù)雜度為O(n^2)
冒泡排序?qū)崿F(xiàn)方法
public class BubbleSort {
public static ArrayList<Integer> bsort(ArrayList<Integer> num) {
for (int i = 0; i < num.size() - 1; i++) {
for (int j = num.size() - 1; j > i; j--) {
if (num.get(j) < num.get(j-1)) {
int tmp = num.get(j);
num.set(j, num.get(j-1));
num.set(j-1, tmp);
}
}
}
return num;
}
}
快速排序 (Quick Sort)
快速排序是目前最常用的排序方法之一，因其計(jì)算效率高，復(fù)雜度只有O(nlogn)。它采用了很多巧妙的方法，例如雙指針、遞歸等，其原位排序的特性又極大節(jié)省了運(yùn)算所需的內(nèi)存空間
快速排序?qū)崿F(xiàn)方法
public class Sorter {
public static void qsort(Integer head, Integer tail, ArrayList<Integer> input) {
if (head >= tail || input.isEmpty() || input.size() <= 1) {
return;
}
int i = head;
int j = tail;
// 1.任意取一個(gè)數(shù)，這里取數(shù)組中位數(shù)下標(biāo)的對(duì)應(yīng)值
Integer pivot = input.get((i + j) / 2);
System.out.print("before qsort:");
for (int k = head; k <= tail; k++) {
System.out.print(input.get(k)+" ");
}
System.out.print("\n");
// 2.排序，將小于pivot的值放在左邊，大于pivot的值放在右邊
while (i <= j) {
while (input.get(i) < pivot) {
// 無需變換位置，光標(biāo)移到后一個(gè)位置
i++;
}
while (input.get(j) > pivot) {
// 無需變換位置，光標(biāo)移到前一個(gè)位置
j--;
}
if (i < j) {
// 數(shù)據(jù)交換，然后繼續(xù)移動(dòng)光標(biāo)
Integer tmp = input.get(i);
input.set(i, input.get(j));
input.set(j, tmp);
i++;
j--;
}
// 必須用else if而不能用if，交換后重新進(jìn)入循環(huán)，否則可能會(huì)出現(xiàn)剩下的值卡在中間無法排序的現(xiàn)象
else if (i == j) {
System.out.println("i == j");
i++; // 剩下一個(gè)恰好等于pivot的數(shù)
}
}
// 3.分塊,繼續(xù)排序
System.out.print("after qsort:");
for (int k = head; k <= tail; k++) {
System.out.print(input.get(k)+" ");
}
System.out.print("\n\n");
// 遞歸繼續(xù)排序
qsort(head, j, input);
qsort(i, tail, input);
}
}
測(cè)試
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(9);
list.add(7);
list.add(8);
list.add(5);
list.add(7);
list.add(10);
list.add(2);
list.add(4);
list.add(3);
list.add(1);
Sorter.qsort(0, list.size()-1, list);
System.out.print(list);
}
}
結(jié)果
before qsort:9 7 8 5 7 10 2 4 3 1
after qsort:1 3 4 5 2 10 7 8 7 9
before qsort:1 3 4 5 2
after qsort:1 3 2 5 4
before qsort:1 3 2
after qsort:1 2 3
before qsort:1 2
i == j
after qsort:1 2
before qsort:5 4
after qsort:4 5
before qsort:10 7 8 7 9
i == j
after qsort:7 7 8 10 9
before qsort:7 7 8
after qsort:7 7 8
before qsort:7 8
i == j
after qsort:7 8
before qsort:10 9
after qsort:9 10
[1, 2, 3, 4, 5, 7, 7, 8, 9, 10]
過程分析
主要體現(xiàn)的是分而治之的思想，用兩個(gè)指針來記錄位置，每一次迭代，都將數(shù)組分成兩塊，將小于等于所取值的數(shù)據(jù)放于左邊，大于所取值的數(shù)據(jù)放于右邊，以棧的形式記錄當(dāng)前狀態(tài)，再次遞歸排序。
上例求解的具體先后順序如圖所示：
維基上對(duì)快速排序的過程也有詳細(xì)的圖示：
Gif中表達(dá)的就是快速排序法，它取數(shù)組最后一個(gè)數(shù)據(jù)作為比較值，然后再交換到中間，大體思路是相同的
