希爾排序法基本思想是：取一個間隔，將長序列分成若干短的子序列，對每個子序列進行直接插入排序；然後逐漸縮小間隔，重複以上過程，直到間隔為 1。前面我們學習了兩種插入排序法，但當要排序的陣列長度越長且數值越不成順序，比較和交換的次數就越多，效率越低。因此 D.L.Shell 在 1959 年提出了縮小增量排序法（又稱希爾排序法），較好地克服了直接插入排序法的不足。
8 7 4 3 6 1 // 待排序數值，以一半長度為間隔 3
3 7 4 8 6 1 // 第一次，取得 3，小於前面的 8，交換位置
3 6 4 8 7 1 // 第二次，取得 6，小於前面的 7，交換位置
3 6 1 8 7 4 // 第三次，取得 1，小於前面的 4，交換位置
1 6 3 4 7 8 // 第四次，縮小間隔為 2，取得 1 小於 3 交換，7 大於 3 不變，8 大於 6 不變，4 小於 8 交換
1 3 4 6 7 8 // 第五次，縮小間隔為 1，進行直接插入排序完成void shellSort() {
int N = 13; // N 為前後記錄位置的增量
for (int gap = N / 2; gap > 0; gap = gap / 2) { // 每次縮小增量
for (int i = gap; i < N; i++) { // 從增量大小開始比較
int temp = a[i]; // 將後一個備份
int j;
for (j = i; j >= gap && temp < a[j - gap]; j -= gap) { // 與同一子序列的數逐個比較
a[j] = a[j - gap]; // 假如小於，就後移
}
a[j] = temp; // 找到合適的插入點，放入其中
}
}
}快速排序法是目前最快的一種排序方法。基本思想是：通過一趟排序將待排序記錄分割為獨立的兩部分，其中一部分記錄的數值均比另一部分小，然後繼續分別對這兩部分進行排序，直到整個序列有序為止。
任取待排序列的某個記錄（通常取第一個數）作為基準，按照該數值大小，將整個序列分成兩個序列——左側的所有記錄數值都比基準小（或相等），右側的都比基準大，基準則放在兩個子序列之間。分別對左右子序列重複上述過程，直到最後所有記錄都放在相應位置。
7 8 4 3 6 1 // 待排序數值
1 8 4 3 6 7 // 第一次，以 7 為基準，1 為 right 值，7 > 1 交換
1 4 3 6 7 8 // 第二次，8 為 left 值，7 < 8 放到最後
1 4 3 6 7 8 // 第三次，left 取得 4，小於 7 放前面
1 4 6 3 7 8 // 第四次，right 取 6，小於 7 放前面
1 4 6 3 7 8 // 第五次，left=right=3，小於 7 放前面
1 4 3 6 7 8 // 7 放入合適位置，第一趟排序完成
// 後續以 1 為基準繼續排序... 直到成功void quickSort(int a[], int low, int high) {
if (high - low <= 0) return; // 元素少於兩個則返回
if (high - low == 1) { // 兩個元素直接比較
if (a[high] < a[low]) swap(a[low], a[high]);
return;
}
int mid = (low + high) / 2;
int pivot = a[mid];
swap(a[mid], a[low]); // 交換 pivot 及低端元素
int scanUp = low + 1;
int scanDown = high;
do {
while (scanUp <= scanDown && a[scanUp] <= pivot) scanUp++;
while (pivot < a[scanDown]) scanDown--;
if (scanUp < scanDown) swap(a[scanUp], a[scanDown]);
} while (scanUp < scanDown);
a[low] = a[scanDown];
a[scanDown] = pivot; // 將 pivot 放到正確位置，分開兩個子表
if (low < scanDown - 1) quickSort(a, low, scanDown - 1); // 遞歸排序低端子表
if (scanDown + 1 < high) quickSort(a, scanDown + 1, high); // 遞歸排序高端子表
}關於排序的問題已經夠多了，就到這裡吧。假如大家有興趣，可以再看相關書籍深入研究。
