给你一个字符串数组 names ，和一个由 互不相同 的正整数组成的数组 heights。两个数组的长度均为 n 。
对于每个下标 i， names[i] 和 heights[i] 表示第 i 个人的名字和身高。
请按身高 降序 顺序返回对应的名字数组 names 。
# 解题思路
快速排序模板
# 提交结果
# 代码
class Solution { | |
public String[] sortPeople(String[] names, int[] heights) { | |
quickSort(names, heights,0,heights.length-1); | |
return names; | |
} | |
private void quickSort(String[] names, int[] heights, int lo, int hi){ | |
if(lo >= hi) return; | |
int povit = heights[lo]; | |
String ts = names[lo]; | |
int i = lo; | |
int j = hi; | |
while(i < j) { | |
// 从右边找第一个 > povit | |
while(i < j && heights[j] <= povit) --j; | |
heights[i] = heights[j]; | |
names[i] = names[j]; | |
// 从左边开始找第一个 < povit | |
while(i < j && heights[i] >= povit) ++i; | |
heights[j] = heights[i]; | |
names[j] = names[i]; | |
} | |
heights[i] = povit; | |
names[i] = ts; | |
quickSort(names, heights, lo, i-1); | |
quickSort(names, heights, i+1, hi); | |
} | |
} |
