快排的c++模板类实现

2018-03-18

引言

很久没写快速排序了，没事的时候尝试着回忆了一下，顺便结合泛型编程的思想，将代码改成了void * ，满足所有数据类型的要求。

基本思想

快速排序最大的问题就是在不额外赋值空间的情况下，怎么做到在不变的空间内，按照快排的思想，将base基点左侧都放上比它小的值，base基点右侧都放上比它大的值。

很多时候base基点直接选择的是第一个元素，也是为了方便我们的排序。

但为了防止特殊情况出现，导致快排效率不高，base基点的选择最好是随机的，但只要将随机选中的base和第一个位置的元素交换位置就可以同样达到我们想要的效果。所以思想的讲解主要从base基点作为第一个元素来讲解。

交换策略

为了时刻保证base基点左侧都放上比它小的值，base基点右侧都放上比它大的值。建立左右两个指针l, r，保证始终 l < base , r > base。那么在一轮迭代过程中，先从右侧开始找到第一个小于base位置上的数进行交换，否则r-1。那么交换过去之后就以同样的思想跟左侧的元素进行比较。

这样就能始终满足[l,r]的区间不断缩小，且保证了非[l,r]区间范围内的点都是满足要求的，且base总是处于[l,r]的边界上。

那么代码就很容易实现了，我先实现了个简单地对整数排序的方法：

void swap(int *a , int x , int y){
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}
void quick_sort(int * a , int lf , int rg)
{
    if(rg <= lf) return;
    int base = lf;
    int l = lf , r = rg;
    while(l < r){
        while(r > base && a[r] >= a[base]) r--;
        swap(a , r , base);
        base = r;
        while(l < base && a[l] <= a[base]) l++;
        swap(a , l , base);
        base = l;
    }
    quick_sort(a, lf, base);
    quick_sort(a, base+1 , rg);
}
int main()
{
    int a[10] = {5, 7, 8, 4, 10, 2, 3, 1 , 6, 9};
    quick_sort(a, 0 , 9);
    for(int i=0 ; i<10 ; i++) cout<<a[i]<<endl;
	return 0;
}

泛型编程

但是很明显这个代码只能对整数有用，那我之后出现了字符串，甚至是自定义的结构体之类的该怎么办呢，怎么把通用性改成和algorithm包中的sort函数一样优秀呢。那么就需要引入void * 参数，以及函数指针。

void 在c++代表一个可以替代任何对象的指针，类似java中的Object，有点所有对象的父类的感觉。所以void 作为参数，那么这个函数就能传入任何参数。

然后引入函数指针，对于排序来说，最重要的是比较两两的大小，那么就引入comparator函数指针来对对象进行比较。对于不同的对象可以有不同的比较方式，所以对不同的对象排序，我们只需要扩展写一份简单的比较函数，而不用在实现整个排序了。

1
2

void quick_sort(void * a , int lf , int rg, size_t data_len, int comparator(void *, void *))
    // a代表数组的指针，lf代表首个位置，rg代表最后一个位置（包括自己），data_len 表示一个元素的字节长度，comparator是个比较函数的指针

因为void 的特殊性，对于void a来说，你可以通过a来获取这个位置的地址，但你不能通过 a + data_len 来得到下一个位置的地址, 而必须转化成具体数据类型的指针才能这样取址，需要注意的是比如 int b , b+1，其实是在b的地址上加了4个字节，因为一个int 32位4个字节，double b b+1，其实是在b的地址上加了8个字节，因为一个double 64位8个字节，转化成不同的类型都是不一样的。

我在此推荐的是转化成 char ，因为一个char就一个字节。正好和data_len的长度一一对应，用int ，还需要除以4。

然后交换值的swap函数因为都是void *，是直接对内存地址进行操作，所以要用memcpy来进行赋值。

void swap(void * a , int x , int y , size_t data_len)
{
    void * temp = (void *)(new char[data_len]);
    memcpy(temp, (char *)a+x*data_len, data_len);
    memcpy((char *)a+x*data_len , (char *)a+y*data_len , data_len);
    memcpy((char *)a+y*data_len, temp, data_len);
}

将上述的快速排序函数修改后就是

void quick_sort(void * a , int lf , int rg, size_t data_len, int comparator(void *, void *))
{
    if(rg <= lf) return;
    int base = lf;
    int l = lf , r = rg;
    while(l<r){
        while(r>base && comparator((char *)a+r*data_len , (char *)a+base*data_len) >= 0) r--;
        swap(a , r , base , data_len);
        base = r;
        while(l<base && comparator((char *)a+l*data_len , (char *)a+base*data_len) <= 0) l++;
        swap(a , l , base , data_len);
        base = l;
    }
    quick_sort(a, lf, base , data_len , comparator);
    quick_sort(a, base+1 , rg , data_len , comparator);
}

我在此定义了两种数据，整数和字符串进行排序。

// 整数的排序规则
int int_cmp(void * a , void * b){
    int * x = (int *) a;
    int * y = (int *) b;
    if(*x > *y) return 1;
    else if(*x == *y) return 0;
    else return -1;
}
// 字符串的排序规则
int str_cmp(void * a , void * b){
    char * x = (char *) a;
    char * y = (char *) b;
    return strcmp(x, y);
}

最后main 函数实现就是

int main()
{
    int a[10] = {5, 7, 8, 4, 10, 2, 3, 1 , 6, 9};
    quick_sort(a, 0 , 9, sizeof(int) , int_cmp);
    for(int i=0 ; i<10 ; i++) cout<<a[i]<<endl;
    char b[10][10] = {"abc\0", "def\0" , "aaa\0", "ab\0", "bac\0", "badc\0", "aacd\0", "abdc\0","bcdd\0", "caddd\0"};
    quick_sort(b, 0, 9, sizeof(b[0]), str_cmp);
    for(int i=0 ; i<10 ; i++) cout<<b[i]<<endl;
    return 0;
}

自定义数据类型排序

可能这样还不够体现出这样编程的好处。那么现在我自定义一个数据结构进行排序。最后写一份总结性的代码

#include "stdio.h"
#include "string.h"
#include <iostream>
using namespace std;
struct A{
    int b;
    char c[10];
    A(){}
    A(int b, char * c){
        this->b = b;
        strcpy(this->c , c);
    }
};
int A_cmp(void * a , void * b){
    A * x = (struct A*) a;
    A * y = (struct A*) b;
    if (x->b < y->b) return -1;
    else if(x->b == y->b){
        int cmp =strcmp(x->c, y->c) ;
        if(cmp < 0) return -1;
        else if(cmp == 0) return 0;
        else return 1;
    }
    else return 1;
}
void swap(void * a , int x , int y , size_t data_len)
{
    void * temp = (void *)(new char[data_len]);
    memcpy(temp, (char *)a+x*data_len, data_len);
    memcpy((char *)a+x*data_len , (char *)a+y*data_len , data_len);
    memcpy((char *)a+y*data_len, temp, data_len);
}
void quick_sort(void * a , int lf , int rg, size_t data_len, int comparator(void *, void *)) // data_len 表示一个元素的字节长度
{
    if(rg <= lf) return;
    int base = lf;
    int l = lf , r = rg;
    while(l<r){
        while(r>base && comparator((char *)a+r*data_len , (char *)a+base*data_len) >= 0) r--;
        swap(a , r , base , data_len);
        base = r;
        while(l<base && comparator((char *)a+l*data_len , (char *)a+base*data_len) <= 0) l++;
        swap(a , l , base , data_len);
        base = l;
    }
    quick_sort(a, lf, base , data_len , comparator);
    quick_sort(a, base+1 , rg , data_len , comparator);
}
int main()
{
    A a[10] = {
        A(5, "abc"), A(3, "abc"), A(5, "aac"), A(5, "abc"), A(4, "abb"),
        A(1, "adc"), A(2, "babc"), A(2, "baac"), A(1, "abbc"), A(4, "babc")
    };
    quick_sort(a, 0, 9, sizeof(struct A), A_cmp);
    for(int i=0 ; i<10 ; i++){
        cout<<a[i].b<<" : "<<a[i].c<<endl;
    }
    return 0;
}
/*
output:
1 : abbc
1 : adc
2 : baac
2 : babc
3 : abc
4 : abb
4 : babc
5 : aac
5 : abc
5 : abc
*/