// 快速排序：選第一個對象作為基準，按照該對象的排序碼大小，將整個對象
// 序列劃分為左右兩個字序列：
// 左側子序列中所有對象的排序碼都小于或等于基準對象的排序碼；
// 右側子序列中所有對象的排序碼都大于基準對象的排序碼；
// 基準對象則排在這兩個子序列中間，這也是該對象最終應放的位置
// 然后分別對這兩個子序列重復施行上述方法，直到所有的對象都排在相應位置上為止
#include <iostream>
 
// 一次快速排序算法
int quickPass(int arr[], int low, int high) {
 int down, up, temp;
 
 down = low;
 up = high;
 temp = arr[low];
 while(down < up) {
  while((down < up) && arr[up] >= temp) // 從右向左掃描
   up--;
  if(down < up)
   arr[down++] = arr[up]; // 在被騰空出來的單元（由down指向）中填入arr[up]
  while((down < up) && arr[down] < temp) // 從左向右掃描
   down++;
  if(down < up)
   arr[up--] = arr[down]; // 在被騰空出來的單元（由up指向）中填入arr[down]
 }
 arr[down] = temp; // 最后把基準插回到數(shù)組中間去
 return down;
}
 
// 快速排序算法
void quickSort(int arr[], int low, int high) {
 // 對序列arr[low]到arr[high]作快速排序
 int mid;
 
 if(low < high) {
  mid = quickPass(arr, low, high); // 對序列arr[low]到arr[high]作一趟快速排序
  quickSort(arr, low, mid-1); // 對左半部分作遞歸處理
  quickSort(arr, mid+1, high); // 對右半部分作遞歸處理
 }
}
 
int main(int argc, const char * argv[]) {
 // insert code here...
 int len, i;
 int arr[] = {40, 30, 60, 90, 70, 10, 20, 40};
 
 len = sizeof(arr) / sizeof(arr[0]);
 std::cout << "排序前：\n";
 for(i = 0; i < len; i++)
  std::cout << arr[i] << " ";
 std::cout << std::endl;
 
 quickSort(arr, 0, len-1); // 調(diào)用快速排序法
 
 std::cout << "排序后：\n";
 for(i = 0; i < len; i++)
  std::cout << arr[i] << " ";
 std::cout << std::endl;
 return 0;
}

// 快速排序的另一種方法:只往一邊掃描
#include <iostream>
 
// 交換兩個數(shù)
void Exchange(int &a, int &b) {
 int temp;
 
 temp = a;
 a = b;
 b = temp;
}
 
// 將序列分為左右兩部分，左部分較小，右部分較大
int Partition(int arr[], int low, int high) {
 int x, i, j;
 
 x = arr[high]; // 以high位置的數(shù)作為基準
 i = low - 1;
   // 進行數(shù)據(jù)分類：左部分較小，右部分較大
 for(j = low; j < high; j++)
  if(arr[j] <= x) { // 往右掃描找小于或者等于基準的數(shù)
   i = i + 1;
   Exchange(arr[i], arr[j]); // 交換
  }
 Exchange(arr[i+1], arr[high]); // 把基準放到中間
 return i+1;
}
 
// 快速排序算法
void quickSort(int arr[], int low, int high) {
 int q;
 
 if(low < high) {
  q = Partition(arr, low, high);
  quickSort(arr, low, q-1);
  quickSort(arr, q+1, high);
 }
}
 
int main(int argc, const char * argv[]) {
 int len, i;
 int arr[] = {40, 30, 60, 90, 70, 10, 20, 40};
 
 len = sizeof(arr) / sizeof(arr[0]);
 std::cout << "排序前：\n";
 for(i = 0; i < len; i++)
  std::cout << arr[i] << " ";
 std::cout << std::endl;
 quickSort(arr, 0, len-1); // 調(diào)用快速排序法
 
 std::cout << "排序后：\n";
 for(i = 0; i < len; i++)
  std::cout << arr[i] << " ";
 std::cout << std::endl;
 return 0;
}