三種快速排序算法以及快速排序的優化
一. 快速排序的基本思想
快速排序使用分治的思想，通過一趟排序將待排序列分割成兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小。之后分別對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。
二. 快速排序的三個步驟
1) 選擇基準：在待排序列中，按照某種方式挑出一個元素，作為 “基準”（pivot）；
2) 分割操作：以該基準在序列中的實際位置，把序列分成兩個子序列。此時，在基準左邊的元素都比該基準小，在基準右邊的元素都比基準大；
3) 遞歸地對兩個序列進行快速排序，直到序列為空或者只有一個元素；
三. 選擇基準元的方式
對于分治算法，當每次劃分時，算法若都能分成兩個等長的子序列時，那么分治算法效率會達到最大。也就是說，基準的選擇是很重要的。選擇基準的方式決定了兩個分割后兩個子序列的長度，進而對整個算法的效率產生決定性影響。
最理想的方法是，選擇的基準恰好能把待排序序列分成兩個等長的子序列。
方法一：固定基準元（基本的快速排序）
思想：取序列的第一個或最后一個元素作為基準元。
/// <summary>
/// 1.0 固定基準元（基本的快速排序）
/// </summary>
public static void QsortCommon(int[] arr, int low, int high)
{
if (low >= high) return; //遞歸出口
int partition = Partition(arr, low, high); //將 >= x 的元素交換到右邊區域，將 <= x 的元素交換到左邊區域
QsortCommon(arr, low, partition - 1);
QsortCommon(arr, partition + 1, high);
}
/// <summary>
/// 固定基準元，默認數組第一個數為基準元，左右分組，返回基準元的下標
/// </summary>
public static int Partition(int[] arr, int low, int high)
{
int first = low;
int last = high;
int key = arr[low]; //取第一個元素作為基準元
while (first < last)
{
while (first < last && arr[last] >= key)
last--;
arr[first] = arr[last];
while (first < last && arr[first] <= key)
first++;
arr[last] = arr[first];
}
arr[first] = key; //基準元居中
return first;
}</pre>
注意：基本的快速排序選取第一個或最后一個元素作為基準。但是，這是一直很不好的處理方法。
測試數據：
測試數據分析：如果輸入序列是隨機的，處理時間可以接受的。如果數組已經有序時，此時的分割就是一個非常不好的分割。因為每次劃分只能使待排序序列 減一，此時為最壞情況，快速排序淪為冒泡排序，時間復雜度為Θ(n^2)。而且，輸入的數據是有序或部分有序的情況是相當常見的。因此，使用第一個元素作 為基準元是非常糟糕的，為了避免這個情況，就引入了下面兩個獲取基準的方法。
方法二：隨機基準元
思想：取待排序列中任意一個元素作為基準元。
引入的原因：在待排序列是部分有序時，固定選取基準元使快排效率底下，要緩解這種情況，就引入了隨機選取基準元。
/// <summary>
/// 2.0 隨機基準元
/// </summary>
public static void QsortRandom(int[] arr, int low, int high)
{
if (low >= high) return; //遞歸出口
PartitionRandom(arr, low, high); //隨機基準元
int partition = Partition(arr, low, high); //將 >= x 的元素交換到右邊區域，將 <= x 的元素交換到左邊區域
QsortRandom(arr, low, partition - 1);
QsortRandom(arr, partition + 1, high);
}
/// <summary>
/// 隨機基準元，將確定好的基準元與第一個數交換，無返回值
/// </summary>
public static void PartitionRandom(int[] arr, int low, int high)
{
Random rd = new Random();
int randomIndex = rd.Next() % (high - low) + low;//取數組中隨機下標
Swap(arr, randomIndex, low); //與第一個數交換
}</pre>
測試數據：
測試數據分析：:這是一種相對安全的策略。由于基準元的位置是隨機的，那么產生的分割也不會總是會出現劣質的分割。在整個數組數字全相等時，仍然是 最壞情況，時間復雜度是O(n^2）。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n）。所以隨機化快速排序可以對于絕大多數輸入數據 達到O(nlogn）的期望時間復雜度。一位前輩做出了一個精辟的總結：“隨機化快速排序可以滿足一個人一輩子的人品需求。”
方法三：三數取中
引入的原因：雖然隨機選取基準時，減少出現不好分割的幾率，但是還是最壞情況下還是O(n^2），要緩解這種情況，就引入了三數取中選取基準。
分析：最佳的劃分是將待排序的序列分成等長的子序列，最佳的狀態我們可以使用序列的中間的值，也就是第N/2個數。可是，這很難算出來，并且會明顯 減慢快速排序的速度。這樣的中值的估計可以通過隨機選取三個元素并用它們的中值作為基準元而得到。事實上，隨機性并沒有多大的幫助，因此一般的做法是使用 左端、右端和中心位置上的三個元素的中值作為基準元。顯然使用三數中值分割法消除了預排序輸入的不好情形，并且減少快排大約14%的比較次數。
舉例：待排序序列為：8 1 4 9 6 3 5 2 7 0
左邊為：8，右邊為0，中間為6
我們這里取三個數排序后，中間那個數作為樞軸，則樞軸為6
注意：在選取中軸值時，可以從由左中右三個中選取擴大到五個元素中或者更多元素中選取，一般的，會有（2t＋1）平均分區法（median-of-(2t+1)，三平均分區法英文為median-of-three。
具體思想：對待排序序列中low、mid、high三個位置上數據進行排序，取他們中間的那個數據作為基準，并用0下標元素存儲基準。
即：采用三數取中，并用0下標元素存儲基準。
/// <summary>
/// 3.0 三數取中
/// </summary>
public static void QsortMedianOfThree(int[] arr, int low, int high)
{
if (low >= high) return; //遞歸出口
PartitionMedianOfThree(arr, low, high); //三數取中
int partition = Partition(arr, low, high); //將 >= x 的元素交換到右邊區域，將 <= x 的元素交換到左邊區域
QsortMedianOfThree(arr, low, partition - 1);
QsortMedianOfThree(arr, partition + 1, high);
}
/// <summary>
/// 三數取中確定基準元，將確定好的基準元與第一個數交換，無返回值
/// </summary>
public static void PartitionMedianOfThree(int[] arr, int low, int high)
{
int mid = low + (high + -low) / 2;
if (arr[mid] > arr[high])
{
Swap(arr, mid, high);
}
if (arr[low] > arr[high])
{
Swap(arr, low, high);
}
if (arr[mid] > arr[low])
{
Swap(arr, mid, low);
} //將中間大小的數與第一個數交換
}</pre>
測試數據：
測試數據分析：使用三數取中優勢還是很明顯的，但是還是處理不了重復數組。
四. 兩種優化的方法
優化一：當待排序序列的長度分割到一定大小后，使用插入排序
原因：對于很小和部分有序的數組，快排不如插排好。當待排序序列的長度分割到一定大小后，繼續分割的效率比插入排序要差，此時可以使用插排而不是快排。
截止范圍：待排序序列長度N = 10，雖然在5~20之間任一截止范圍都有可能產生類似的結果，這種做法也避免了一些有害的退化情形。
—-摘自《數據結構與算法分析》Mark Allen Weiness 著
/// <summary>
/// 4.0 三數取中+插排
/// </summary>
public static void QsortThreeInsert(int[] arr, int low, int high)
{
if (high - low + 1 < 10)
{
InsertSort(arr, low, high);
return;
} //插排，遞歸出口
PartitionMedianOfThree(arr, low, high); //三數取中
int partition = Partition(arr, low, high); //將 >= x 的元素交換到右邊區域，將 <= x 的元素交換到左邊區域
QsortMedianOfThree(arr, low, partition - 1);
QsortMedianOfThree(arr, partition + 1, high);
}
測試數據：
測試數據分析：針對隨機數組，使用三數取中選擇基準+插排，效率還是可以提高一點，真是針對已排序的數組，是沒有任何用處的。因為待排序序列是已經有序的，那么每次劃分只能使待排序序列減一。此時，插排是發揮不了作用的。所以這里看不到時間的減少。另外，三數取中選擇基準+插排還是不能處理重復數組。
優化二：在一次分割結束后，可以把與Key相等的元素聚在一起，繼續下次分割時，不用再對與key相等元素分割
舉例：
待排序序列 1 4 6 7 6 6 7 6 8 6
三數取中選取基準：下標為4的數6
轉換后，待分割序列：6 4 6 7 1 6 7 6 8 6
基準key：6
本次劃分后，未對與key元素相等處理的結果：1 4 6 6 7 6 7 6 8 6
下次的兩個子序列為：1 4 6 和 7 6 7 6 8 6
本次劃分后，對與key元素相等處理的結果：1 4 6 6 6 6 6 7 8 7
下次的兩個子序列為：1 4 和 7 8 7
經過對比，我們可以看出，在一次劃分后，把與key相等的元素聚在一起，能減少迭代次數，效率會提高不少
具體過程：在處理過程中，會有兩個步驟
第一步，在劃分過程中，把與key相等元素放入數組的兩端
第二步，劃分結束后，把與key相等的元素移到樞軸周圍
/// <summary>
/// 5.0 三數取中+插排+聚集相同元素
/// </summary>
public static void QsortThreeInsertGather(int[] arr, int low, int high)
{
if (high - low + 1 < 10)
{
InsertSort(arr, low, high);
return;
} //插排，遞歸出口
PartitionMedianOfThree(arr, low, high); //三數取中
//進行左右分組（處理相等元素）
int first = low;
int last = high;
int left = low;
int right = high;
int leftLength = 0;
int rightLength = 0;
int key = arr[first];
while (first < last)
{
while (first < last && arr[last] >= key)
{
if (arr[last] == key) //處理相等元素，將相等的元素放置數組兩端
{
Swap(arr, last, right);
right--;
rightLength++;
}
last--;
}
arr[first] = arr[last];
while (first < last && arr[first] <= key)
{
if (arr[first] == key)
{
Swap(arr, first, left);
left++;
leftLength++;
}
first++;
}
arr[last] = arr[first];
}
arr[first] = key;
//一次快排結束
//把與基準元key相同的元素移到最終位置周圍
int i = first - 1;
int j = low;
while (j < left && arr[i] != key)
{
Swap(arr, i, j);
i--;
j++;
}
i = last + 1;
j = high;
while (j > right && arr[i] != key)
{
Swap(arr, i, j);
i++;
j--;
}
QsortThreeInsertGather(arr, low, first - leftLength - 1);
QsortThreeInsertGather(arr, first + rightLength + 1, high);
}</pre> <p align="left">
測試數據:</p>
測試數據分析：三數取中+插排+聚集相等元素的組合，效果竟然好的出奇。
原因：在數組中，如果有相等的元素，那么就可以減少不少冗余的劃分。這點在重復數組中體現特別明顯啊。
其實這里，插排的作用還是不怎么大的。
以下是全部的測試程序源碼：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Threading;
namespace Sort
{
class Program
{
static void Main(string[] args)
{
//開啟10M的堆棧空間的線程
ThreadStart ts = new ThreadStart(Sort.DoQsort);
Thread thread = new Thread(ts, 10000000);
thread.Start();
}
}
class Sort
{
public static void DoQsort()
{
int[] arr = new int[100000]; //10W個空間大小的數組
//Random rd = new Random();
//for (int i = 0; i < arr.Length; i++) //隨機數組
//{
// arr[i] = rd.Next();
//}
//for (int i = 0; i < arr.Length; i++) //升序數組
//{
// arr[i] = i;
//}
//for (int i = 0; i < arr.Length; i++) //降序數組
//{
// arr[i] = arr.Length - 1 - i;
//}
for (int i = 0; i < arr.Length; i++) //重復數組
{
arr[i] = 5768461;
}
Stopwatch watch = new Stopwatch();
watch.Start(); //開始計時
//QsortCommon(arr, 0, arr.Length - 1); //固定基準元
//QsortRandom(arr, 0, arr.Length - 1); //隨機基準元
//QsortMedianOfThree(arr, 0, arr.Length - 1); //三數取中
//QsortThreeInsert(arr, 0, arr.Length - 1); //三數取中+插排
QsortThreeInsertGather(arr, 0, arr.Length - 1); //三數取中+插排+聚集相同元素
watch.Stop(); //計時結束
Console.WriteLine(watch.ElapsedMilliseconds.ToString());
}
/// <summary>
/// 1.0 固定基準元（基本的快速排序）
/// </summary>
public static void QsortCommon(int[] arr, int low, int high)
{
if (low >= high) return; //遞歸出口
int partition = Partition(arr, low, high); //將 >= x 的元素交換到右邊區域，將 <= x 的元素交換到左邊區域
QsortCommon(arr, low, partition - 1);
QsortCommon(arr, partition + 1, high);
}
/// <summary>
/// 2.0 隨機基準元
/// </summary>
public static void QsortRandom(int[] arr, int low, int high)
{
if (low >= high) return; //遞歸出口
PartitionRandom(arr, low, high); //隨機基準元
int partition = Partition(arr, low, high); //將 >= x 的元素交換到右邊區域，將 <= x 的元素交換到左邊區域
QsortRandom(arr, low, partition - 1);
QsortRandom(arr, partition + 1, high);
}
/// <summary>
/// 3.0 三數取中
/// </summary>
public static void QsortMedianOfThree(int[] arr, int low, int high)
{
if (low >= high) return; //遞歸出口
PartitionMedianOfThree(arr, low, high); //三數取中
int partition = Partition(arr, low, high); //將 >= x 的元素交換到右邊區域，將 <= x 的元素交換到左邊區域
QsortMedianOfThree(arr, low, partition - 1);
QsortMedianOfThree(arr, partition + 1, high);
}
/// <summary>
/// 4.0 三數取中+插排
/// </summary>
public static void QsortThreeInsert(int[] arr, int low, int high)
{
if (high - low + 1 < 10)
{
InsertSort(arr, low, high);
return;
} //插排，遞歸出口
PartitionMedianOfThree(arr, low, high); //三數取中
int partition = Partition(arr, low, high); //將 >= x 的元素交換到右邊區域，將 <= x 的元素交換到左邊區域
QsortMedianOfThree(arr, low, partition - 1);
QsortMedianOfThree(arr, partition + 1, high);
}
/// <summary>
/// 5.0 三數取中+插排+聚集相同元素
/// </summary>
public static void QsortThreeInsertGather(int[] arr, int low, int high)
{
if (high - low + 1 < 10)
{
InsertSort(arr, low, high);
return;
} //插排，遞歸出口
PartitionMedianOfThree(arr, low, high); //三數取中
//進行左右分組（處理相等元素）
int first = low;
int last = high;
int left = low;
int right = high;
int leftLength = 0;
int rightLength = 0;
int key = arr[first];
while (first < last)
{
while (first < last && arr[last] >= key)
{
if (arr[last] == key) //處理相等元素
{
Swap(arr, last, right);
right--;
rightLength++;
}
last--;
}
arr[first] = arr[last];
while (first < last && arr[first] <= key)
{
if (arr[first] == key)
{
Swap(arr, first, left);
left++;
leftLength++;
}
first++;
}
arr[last] = arr[first];
}
arr[first] = key;
//一次快排結束
//把與基準元key相同的元素移到最終位置周圍
int i = first - 1;
int j = low;
while (j < left && arr[i] != key)
{
Swap(arr, i, j);
i--;
j++;
}
i = last + 1;
j = high;
while (j > right && arr[i] != key)
{
Swap(arr, i, j);
i++;
j--;
}
QsortThreeInsertGather(arr, low, first - leftLength - 1);
QsortThreeInsertGather(arr, first + rightLength + 1, high);
}
/// <summary>
/// 固定基準元，默認數組第一個數為基準元，左右分組，返回基準元的下標
/// </summary>
public static int Partition(int[] arr, int low, int high)
{
int first = low;
int last = high;
int key = arr[low]; //取第一個元素作為基準元
while (first < last)
{
while (first < last && arr[last] >= key)
last--;
arr[first] = arr[last];
while (first < last && arr[first] <= key)
first++;
arr[last] = arr[first];
}
arr[first] = key; //基準元居中
return first;
}
/// <summary>
/// 隨機基準元，將確定好的基準元與第一個數交換，無返回值
/// </summary>
public static void PartitionRandom(int[] arr, int low, int high)
{
Random rd = new Random();
int randomIndex = rd.Next() % (high - low) + low;//取數組中隨機下標
Swap(arr, randomIndex, low); //與第一個數交換
}
/// <summary>
/// 三數取中確定基準元，將確定好的基準元與第一個數交換，無返回值
/// </summary>
public static void PartitionMedianOfThree(int[] arr, int low, int high)
{
int mid = low + (high + -low) / 2;
if (arr[mid] > arr[high])
{
Swap(arr, mid, high);
}
if (arr[low] > arr[high])
{
Swap(arr, low, high);
}
if (arr[mid] > arr[low])
{
Swap(arr, mid, low);
} //將中間大小的數與第一個數交換
}
/// <summary>
/// 插入排序
/// </summary>
public static void InsertSort(int[] arr, int low, int high)
{
for (int i = low + 1; i <= high; i++)
{
if (arr[i] < arr[i - 1])
{
for (int j = low; j < i; j++)
{
if (arr[j] > arr[i])
{
Swap(arr, i, j);
}
}
}
}
}
/// <summary>
/// 數組交換
/// </summary>
public static void Swap(int[] arr, int index1, int index2)
{
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
}
}</pre> 來源：叫我霍啊啊啊