快速排序(Quick Sort):
快速排序(Quick Sort)的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对着两部分记录继续进行排序,以达到整个序列有序的目的。
例题:假设现在我们要对数组{50, 10, 90, 30, 70, 40, 80, 60, 20}进行排序。算法实现如下:
#include <iostream> using namespace std; int Partion(int *array, int start, int end) { /* 判断参数合法性 */ if (array == NULL || start < 0 || end < 0 || start > end) { return -1; } /* 取枢纽为第一个元素,则将array[start,end]以枢纽分成两部分, 前部分小于pivotKey,后部分大于pivotKey */ int pivotKey = array[start]; int i = start, j = end; while (i < j) { while (i < j && array[j] >= pivotKey) { j--; } array[i] = array[j]; while (i < j && array[i] <= pivotKey) { i++; } array[j] = array[i]; } array[i] = pivotKey; return i; } void QuickSort(int *array, int start, int end) { /* 判断参数合法性 */ if (array == NULL || start < 0 || end < 0 || start > end) { return; } if (start < end) { int pivot = Partion(array, start, end); QuickSort(array, start, pivot - 1); QuickSort(array, pivot + 1, end); } } int main() { int array[] = {50, 10, 90, 30, 70, 40, 80, 60, 20}; QuickSort(array, 0, 8); for (int i = 0; i < 8; i++) { cout << array[i] << " "; } cout << endl; }
下面我们考虑,如果使用快速排序的基本思想来解决以下问题。
例1:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。(剑指offer,面试题29,页数:163)
如果数组中有一个数字出现的次数超过数组长度的一半,则如果将该数组排序之后,那么其array[length / 2]中的值必是该值。同样,该值是整个数组的中位数。即长度为n的数组的第n/2大的数字。
考虑快速排序算法,我们先在数组中选择一个数字,然后调整数组中数字的顺序,使得比选中的数字小的数字都排在它的左边,比选中的数字大的数字都排在它的右边。如果这个被选中的数字的下标刚好是n/2,则这个数字就是数组的中位数。
如果它的坐标大于n/2,那么中位数应该在它的左边,我们可以接着在它的左边部分的数组中查找。
如果它的左边小于n/2,那么中位数应该在它的右边,我们可以接着在它的右边部分的数组中查找。
实现上述思路:
#include <iostream> using namespace std; bool gInputInvalid = false; int Partion(int *array, int start, int end) { if (array == NULL || start < 0 || end < 0 || start > end) { return -1; } int pivotKey = array[start]; int i = start, j = end; while (i < j) { while (i < j && array[j] >= pivotKey) { j--; } array[i] = array[j]; while (i < j && array[i] <= pivotKey) { i++; } array[j] = array[i]; } array[i] = pivotKey; return i; } /* 函数名: GetMoreThanHalfNumber 函数功能: 获取数组中出现次数超过一半的数字。假设输入数组存在次数超过一半的数字,这里我们不做判断。 函数参数: int *array 数组指针 int length 长度 返回值: 返回数组中出现次数超过一半的数字。 */ int GetMoreThanHalfNumber(int *array, int length) { /* 判断参数的合法性 */ if (array == NULL || length < 0) { gInputInvalid = true; return 0; } int middle = length / 2; int start = 0; int end = length - 1; while (start <= end) { int index = Partion(array, start, end); if (index == middle) { break; } else if (index > middle) { end = index - 1; } else { start = index + 1; } } return array[middle]; } void Test(const char *testName, int *array, int length, int expectedMoreThanHalfNumber) { cout << testName << " : "; if (GetMoreThanHalfNumber(array, length) == expectedMoreThanHalfNumber) { cout << "Passed." << endl; } else { cout << "Failed." << endl; } } int main() { int array1[] = {1, 2, 3, 2, 2, 2, 5, 4, 2}; Test("Test1", array1, sizeof(array1) / sizeof(int), 2); int array2[] = {2, 2, 2, 2, 2, 1, 3, 4, 5}; Test("Test2", array2, sizeof(array2) / sizeof(int), 2); int array3[] = {1, 3, 4, 5, 2, 2, 2, 2, 2}; Test("Test3", array3, sizeof(array3) / sizeof(int), 2); int array4[] = {1}; Test("Test4", array4, 1, 1); }
例2:输入n个整数,找出其中最小的k个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。(剑指offer,面试题30,页数:167)
基于Partion函数来解决这个问题。如果基于数组的第k个数字来调整,使得比第k个数字小的所有数字位于数组的左边,比第k个数字大的所有数字都位于数组的右边。这样调整之后,位于数组中左边的k个数字就是最小的k个数字。
同理,我们相当于将上一题目中的n/2,换成k来求解。
#include <iostream> using namespace std; bool gInputInvalid = false; int Partion(int *array, int start, int end) { if (array == NULL || start < 0 || end < 0 || start > end) { return -1; } int pivotKey = array[start]; int i = start, j = end; while (i < j) { while (i < j && array[j] >= pivotKey) { j--; } array[i] = array[j]; while (i < j && array[i] <= pivotKey) { i++; } array[j] = array[i]; } array[i] = pivotKey; return i; } /* 函数名: GetKLeastestNumbers 函数功能: 获取数组中最小的k个数字 函数参数: int *array 数组指针 int length 长度 int k 数组中最小的k个数字 */ void GetKLeastestNumbers(int *array, int length, int k) { /* 判断参数的合法性 */ if (array == NULL || length < 0) { gInputInvalid = true; return; } int middle = k; int start = 0; int end = length - 1; while (start <= end) { int index = Partion(array, start, end); if (index == middle) { break; } else if (index > middle) { end = index - 1; } else { start = index + 1; } } } void Test(const char *testName, int *array, int length, int k) { cout << testName << " : " << endl; cout << "原数组:"; for (int i = 0; i < length; i++) { cout << array[i] << " "; } cout << endl; GetKLeastestNumbers(array, length, k); cout << "最小的k个数:"; for (int i = 0; i < k; i++) { cout << array[i] << " "; } cout << endl; } int main() { int array1[] = {4, 5, 1, 6, 2, 7, 3, 8}; Test("Test1", array1, sizeof(array1) / sizeof(int), 4); int array2[] = {4, 5, 1, 6, 2, 7, 3, 8}; Test("Test2", array2, sizeof(array2) / sizeof(int), 8); int array3[] = {4, 5, 1, 6, 2, 7, 3, 8}; Test("Test3", array3, sizeof(array3) / sizeof(int), 1); return 0; }