快速排序及其應用

快速排序（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; 
} 

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

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

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

}