我所理解的快速排序算法
快速排序是在實踐中最快的已知排序算法，它的平均運行時間是O（NlogN）。該算法之所以特別快，主要是由于非常精練和高度優化的內部循環。在隊列中尋找合適的樞點元素，并按樞點元素劃分序列，是快速排序算法的關鍵。
為簡單起見，我這里數組的第一個元素作為樞點元素，重新排列數組，使得樞點元素之前的元素都小于樞點元素，而樞點元素之后的元素都大于或等于樞點元素。
在這里我提供算法的兩種實現：
第一種：
template <class T>
int Parttion(T a[], int low, int high)
{
T x = a[low];
while (low < high)
{
while (low < high && a[high] >= x)
high--;
a[low] = a[high];
while (low < high && a[low] < x)
low++;
a[high] = a[low];
}
a[low] = x;
return low;
}
第二種：
template <class T>
int Parttion(T a[], int low, int high)
{
T x = a[low];
int i = low;
for (int j=low+1; j<=high; j++)
{
if (a[j] <= x)
{
i++;
if (i != j)
Swap(a[i], a[j]);
}
}
Swap(a[low], a[i]);
return i;
}
template <class T>
void Swap(T & a, T & b)
{
T t = a;
a = b;
b = t;
}
快速排序的驅動程序：
template <class T>
void QuickSort(T a[], int len)
{
Qsort(a, 0, len-1);
}
template <class T>
void Qsort(T a[], int low, int high)
{
if (low < high)
{
int k = Parttion(a, low, high);
Qsort(a, low, k-1);
Qsort(a, k+1, high);
}
}