（55）按身高排序

文章目录

每日一言
1. 题目
2. 解题思路
- 2.1 使用冒泡排序
- 2.2 使用qsort函数
3. 代码
- 3.1 使用冒泡排序
- 3.2 使用qsort函数
结语

每日一言

无论种子散落在何处，都会长出一棵树，向着天空，挣扎生长。

1. 题目

题目链接：按身高排序

给你一个字符串数组 names ，和一个由互不相同的正整数组成的数组 heights 。两个数组的长度均为 n 。

对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。

请按身高降序顺序返回对应的名字数组 names 。

示例 1：
输入：names = [“Mary”,“John”,“Emma”], heights = [180,165,170]
输出：[“Mary”,“Emma”,“John”]
解释：Mary 最高，接着是 Emma 和 John 。
示例 2：
输入：names = [“Alice”,“Bob”,“Bob”], heights = [155,185,150]
输出：[“Bob”,“Alice”,“Bob”]
解释：第一个 Bob 最高，然后是 Alice 和第二个 Bob 。

提示：

n == names.length == heights.length
1 <= n <= 103
1 <= names[i].length <= 20
1 <= heights[i] <= 105
names[i] 由大小写英文字母组成
heights 中的所有值互不相同

2. 解题思路

2.1 使用冒泡排序

冒泡排序的核心思想是通过反复比较相邻元素的大小，将较大（或较小）的元素逐渐交换到数组的末尾。

通过两层嵌套的循环，外层循环控制每一轮的排序次数，内层循环通过比较相邻元素的身高大小来判断是否需要交换。

如果发现前面的元素身高比后面的元素身高小，则进行交换。为了保持姓名与身高的对应关系，同时也对保存人名的数组进行相应的交换操作。

通过引入一个临时变量 tmp，可以完成两个整型元素的交换，通过指针 char* name 的交换，可以实现两个字符串指针的交换。

最后，在排序完成后，将排序后的数组大小赋值给 returnSize。

函数返回保存排序后的人名的字符串数组的指针 names。

2.2 使用qsort函数

首先，定义了一个结构体 Person，包含两个成员变量 heights 和 name，分别表示身高和名字。

定义一个比较函数 cmpare，该函数是为了配合标准库函数 qsort 进行排序操作。比较函数通过比较两个 Person 结构体的身高来进行排序，按照身高从大到小的顺序进行比较。

在 sortPeople 函数中，首先通过 malloc 动态分配了一个大小为 namesSize 的 Person 结构体数组 person。

然后将传入的人名和身高分别保存到 person 结构体数组中对应的元素中，这样就建立了名字和身高的对应关系。

用 C 语言标准库函数 qsort，对 person 数组进行排序，使用自定义的比较函数 cmpare 进行比较。

完成排序后，将排序后的人名从 person 结构体数组中拷贝回原来的 names 数组中，这样就得到了排序后的名字数组。

别忘了释放掉person占用的空间。

最后，将排序后的数组大小赋值给 returnSize，并返回排序后的 names 数组。

3. 代码

3.1 使用冒泡排序

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char** sortPeople(char** names, int namesSize, int* heights, int heightsSize, int* returnSize) {
    for(int i=0;i<namesSize-1;i++) {
        for(int j = 0;j<namesSize-i-1;j++) {
            if(heights[j]<heights[j+1]) {
                int tmp = heights[j];
                heights[j] = heights[j+1];
                heights[j+1] = tmp;

                char *name = names[j];
                names[j] = names[j+1];
                names[j+1] = name;
                
            }

        }
    }
    *returnSize = namesSize;
    return names;
}

3.2 使用qsort函数

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 typedef struct Person {
    int heights;
    char *name;   
 }Person;

//写一个比较函数，为qsort的使用做准备
int cmpare(const void*p1,const void* p2) {
    return ((Person*)p2)->heights - ((Person*)p1)->heights;
}

char** sortPeople(char** names, int namesSize, int* heights, int heightsSize, int* returnSize) {
	//申请一块空间，用来存放结构体
    Person *person = (Person*)malloc(sizeof(Person)*namesSize); 
    //将名字和身高放到结构体当中
    for(int i = 0; i < namesSize; i++) {
        person[i].name = names[i];
        person[i].heights = heights[i];
    }
    //使用qsort函数排序结构体
    qsort(person,namesSize,sizeof(Person),cmpare);

	//将排序后的结果放到names中
     for(int i = 0; i < namesSize; i++) {
        names[i] = person[i].name;
    }

	//释放动态内存管理申请的空间
    free(people)

	//返回数组大小
    *returnSize = namesSize;
    return names;
}