题解 | #牛牛的排序#哈希表，快速排序

牛牛的排序

http://www.nowcoder.com/practice/26a0c92e9266443887a3bf81aff8e188

描述

牛牛试图给一个长度为 n 整数数组排序，即实现一个 void sort(int *array,int n)

常规方法就不写了，其他解法和排名上都有。

这里介绍另外两种比较常用的排序算法

它就是 哈希表 和 快速排序。

一、哈希表

哈希表的作用其实就是将数值等同于数组下标所对应的元素位置+1，标志其存在，记这个数组为hash数组。

当元素存放完成后，遍历hash数组中所有大于一的元素，打印出其对应的数组下标即可（注：有时hash数组中元素可能为2，就要都打印出来）。

//哈希表
void sort(int* arr, int n) {
    int hash[101];                   //定义哈希表
    memset(hash, 0, sizeof(hash));   //清空哈希表
    for (int i = 0; i < n; i++) {    
        ++hash[arr[i]];            //将数值列入哈希表的下标
    }
    for (int i = 0; i <= 100; i++) { 
        while (hash[i] > 0) {
            *arr++ = i;            //遍历哈希表，按顺序找出存放的数值下标
            --hash[i];
        }
    }
}
int main() {

    int n = 0;
    int tem = 0;
    scanf("%d", &n);
    int arr[100] = { 0 };
    for (int i = 0; i < n; i++) {
        scanf("%d ", &arr[i]);
    }

    sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

其实hash表没什么可讲的，其实就是将数值对应hash数组的元素下标位置加1，表示这里有东西，寻找的时候，可以方便去找。

二、快速排序

快速排序通俗明了，快速！！排序！！

这其实是个库函数(想不到吧哼哼~，我也没想到)，直接调用就可以了(stdlib.h)。

它可以进行结构体、字符、整形等众多类型的排序(因为是无类型)

在Cplusplus中可以找到它

void qsort (void* base, size_t num, size_t size,int (*compar)(const void*,const void*)); //快速排序

q 表示 quickly 快速的意思

sort 表示排序的意思

合在一起就是快速排序，好记吧😄。

接下来看参数：

void* base 从那开始，一般将数组名放进去就可以了

size_t num 有多少个元素，一般用sizeof(数组名)/sizeof(首元素)。

size_t size 一个元素多少字节，一般用sizeof(首元素)。

int (*compar)(const void*,const void*) 这是一个函数指针，指示两个元素的交换类型，不然void(无类型)类型的元素交换,程序不知道交换几个字节

这个函数的格式其实是看数组的元素类型的

int cmp_int(const void * e1,const void *e2)
{
    return *(int*)e1 - *(int*)e2;
}

我解释一下这个代码,定义一个int类型的函数,参数为两个无类型(const得加),

因为是无类型，所以需要将它变成有类型。(数组定义的是int，所以这用int*)

将e1、e2强制类型转换成int*(e1、e2本来也是指针)，再返回它俩的差值即可。

Cplusplus上讲述的差不多是它俩差值(>0、=0、<0)

摘选自：qsort - C++ Reference (cplusplus.com)

这个时候调用一下就可以了

qsort(arr,sz,sizeof(arr[0]),cmp_int);

注意要调用头文件<stdlib.h>

完整代码演示

#include <stdio.h>
#include <stdlib.h>
// 快速排序
int cmp_int( void* e1, void* e2) {
    return *(int*)e1 - *(int*)e2;  //计算类型
}
int main() {
    int n = 0;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d ", &arr[i]);
    }
    int sz = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, sz, sizeof(arr[0]), cmp_int);  //快速排序函数
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}