剑指offer（扩展）快排P80

剑指offer（扩展）快排 P80

1. 快速排序 （递归实现） void quickSort(int nums[], int start, int end) { if (nums == NULL || start > end || start < 0) return; int flag = nums[start], i = start, j = end; while (i < j) { while (nums[j] >= flag && i < j) --j; // 一定是 先 从右往左找 nums[i] = nums[j]; while(nums[i] <= flag && i < j) ++i; nums[j] = nums[i]; } nums[i] = flag; // 确定当前基准值的位置 i quickSort(nums, start, i - 1); quickSort(nums, i + 1, end); } 2. 给公司员工年龄排序 P81 void ageSort(int nums[], int len) { if (nums == NULL || len < 1) return; const int range_of_age_up = 100; // 年龄上界 const int range_of_age_down = 0; // 年龄下界 int *hash = new int[range_of_age_up + 1]; // hash表存对应年龄出现次数 memset(hash, 0, sizeof(hash) * (range_of_age_up + 1) ); // 注意长度！ for (int i = 0; i < len; ++i) { if (nums[i] < range_of_age_down || nums[i] > range_of_age_up) { // 异常 throw "sorry , out of range !"; } ++hash[nums[i]]; } int index = 0; // 排序后的数组索引 for (int i = 0; i <= range_of_age_up; ++i) // 统计每个年龄 i出现的次数hash[j] for (int j = 0; j < hash[i]; ++j) // 那么连着hash[j]个元素就是年龄i nums[index++] = i; }