内容发布更新时间 : 2024/5/2 10:12:19星期一 下面是文章的全部内容请认真阅读。
（一）目标
在实际问题的解决过程中，我们发现，很多问题都可以归结为对数据的排序和查询。而查询的效率则在很大程度上依赖于排序的效率；尤其是在数据量达到海量级的时候。因此，设计一个有效的排序算法是至关重要的。本文设计了一个通用的c++ quicksort 模板类。通过简单的提供一个data类，可以实现任意数据的快速排序算法，提高了开发效率。
（二）快速排序算法的思想
最基本的快速排序的思想是基于分治策略的：
对于输入的子序列l[p..r]，如果规模足够小则直接进行排序，否则分三步处理：
1 分解(divide)：将输入的序列l[p..r]划分成两个非空子序列l[p..q]和l[q+1..r]， 使l[p..q]中任一元素的值不大于l[q+1..r]中任一元素的值。
2 递归求解(conquer)：通过递归调用快速排序算法分别对l[p..q]和l[q+1..r]进行排序。
3 合并(merge)：由于对分解出的两个子序列的排序是就地进行的， 所以在l[p..q]和l[q+1..r]都排好序后不需要执行任何计算l[p..r]就已排好序。
（三）准备工作和源代码 1 使用vc6建立console工程
2 加入下面的模板类（快速排序的模板类。）：
template
public:
quicksorttemp() { }
~quicksorttemp() { } public:
// 快速排序的实现，array是要排序数据的数组，nlower，nupper范围是0 ~ 数据总个数-1
static void quicksort(datatype* array, int nlower, int nupper) {
// 测试是否排序完毕 if (nlower < nupper) {
// 分解和分别进行排序
int nsplit = partition (array, nlower, nupper);//数据切分为两个部分 quicksort (array, nlower, nsplit - 1);//左半部分递归排序 quicksort (array, nsplit + 1, nupper);//右半部分递归排序 } }
// 切分数据为左右两个部分，返回中间元素x的编号
// 主要的过程就是：选择一个元素x作为分界点，将比x大的元素放到x右边，其余放到x左边。
static int partition (datatype* array, int nlower, int nupper) {
int nleft = nlower + 1;
datatype pivot = array[nlower];
int nright = nupper;
datatype swap;
while (nleft <= nright) {
while (nleft <= nright && array[nleft].compareto(pivot) <= 0) nleft = nleft + 1;
while (nleft <= nright && array[nright].compareto(pivot) > 0) nright = nright - 1;
if (nleft < nright) {
swap = array[nleft];
array[nleft] = array[nright]; array[nright] = swap; nleft = nleft + 1; nright = nright - 1; } }
swap = array[nlower];
array[nlower] = array[nright]; array[nright] = swap; return nright; } };
3 数据类接口的实现
从上面模板类的实现我们可以看出，为了使用这个模板类对某种类型的数据数组datatype * data进行排序，我们必须实现datatype的接口compareto（比较两个datatype 元素a,b的大小，a>b返回1，a==b返回0，否则返回-1）。
举个例子来说：现在要排序二维点坐标，定义大小关系是：先比较x轴坐标值大小，x相同的话，由y值大小决定大小关系。即：(1,1) == (1,1) , (2,1) > (1, 10) , (3, 5) < (4, 1)。
此外：还必须实现datatype类型的无参数的默认构造函数（因为模板类中要使用）。 定义数据类型mypoint如下： struct mypoint {
mypoint() { };
mypoint(int x, int y) {
this->x = x; this->y = y; }
int compareto(mypoint& b) {
if(this->x < b.x) return -1; else if(this->x > b.x) return 1; else {
if(this->y > b.y) return 1; else if(this->y < b.y) return -1; else return 0; } } int x; int y; };
（四）测试
下面是用于测试的主函数：
int _tmain(int argc, tchar* argv[], tchar* envp[]) {
int nretcode = 0;
//point数组
mypoint points[10] = {mypoint(1,1), mypoint(2,5), mypoint(7,11), mypoint(100,2), mypoint(1, 7), mypoint(9,32), mypoint(7, 1), mypoint(2,2), mypoint(1,1), mypoint(9,5)}; int count = 10;
//排序前
printf(\