快速排序（Quick Sort）：

快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对着两部分记录继续进行排序，以达到整个序列有序的目的。

例题：假设现在我们要对数组{50, 10, 90, 30, 70, 40, 80, 60, 20}进行排序。算法实现如下：

#include   
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; 
} 

#include 
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   
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); 
} 

#include 
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来求解。