我所理解的快速排序算法
快速排序是在实践中最快的已知排序算法，它的平均运行时间是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);
}
}
补充一个五数(你可以设置任意大于2的整数)中值分割法选取枢纽元.
Mark Allen Weiss在其著作<<数据结构与算法分析--c语言描述>>中对枢纽元的选取进行了分析.他认为使用第一个元素作为枢纽元是绝对糟糕的主义----我前面就是这样做的,呵呵.比较安全的做法是随机选取枢纽元,但是随机数的生成太"昂贵"了,会使效率降低.比较实用的是多元中值分割法(书上举了三数中值分割法的例子),枢纽元的最好位置是数组的中值,这样把数组分成两个相等的部分是最佳的.但是要寻找数组的中值可不是一件容易的事,我们只好折中一下,使用左端,右端和中心位置的三个元素的中值作为枢纽元.
对于很小的数组(N<=20),快速排序不如插入排序好.所以我们可以设置一个长度上限max,当数组的长度大于max时,递归快速排序,否则使用插入排序.
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)
{
const int max = 5;//确定是否采用插入排序的数组长度上限
if (high-low >= max)
{
int k = Parttion(a, low, high);
Qsort(a, low, k-1);
Qsort(a, k+1, high);
}
else //如果数组的元素很少（小于5个 ），使用折半插入排序
HalfInsertSort(a+low, high-low+1);
}
template <class T>
void Swap(T &a, T &b)
{
T temp = a;
a = b;
b = temp;
}
template <class T>
T Median(T a[], int low, int high)//取中间元素的值作为枢纽元素，同时对两端的元素排序
{
int mid = (low + high) / 2;
if (a[low] > a[mid])
Swap(a[low], a[mid]);
if (a[low] > a[high])
Swap(a[low], a[high]);
if (a[mid] > a[high])
Swap(a[mid], a[high]);
Swap(a[mid], a[low+1]);//把枢纽元素放到数组的第2个位置
return a[low+1];
}
template <class T>
int Parttion(T a[], int low, int high)//根据枢纽元素分割数组
{
T pivot = Median(a, low, high);
int i = low + 1;
int j = high;
while (i < j)
{
while (a[++i] < pivot) {}
while (a[--j] > pivot) {}
if (i < j)
Swap(a[i], a[j]);
}
Swap(a[j], a[low+1]);
return j;
}
template <class T>
void HalfInsertSort(T a[], int len)//折半插入排序
{
int i, j;
int low, high, mid;
T temp;
for (i=1; i<len; i++)
{
temp = a[i];
low = 0;
high = i - 1;
while (low <= high) //在a[low。。。high]中折半查找有序插入的位置
{
mid = (low + high) / 2;
if (a[mid] > temp)
high = mid - 1;
else
low = mid + 1;
} //while
for (j=i-1; j>high; j--)//元素后移
a[j+1] = a[j];
a[high+1] = temp; //插入
}//for
}
评论