スナップアルゴリズム(C++版)
2588 ワード
#include <iostream>
using namespace std;
/** Quick Sort
*
* split: cmp && swap
* left
* right
*
*/
template <typename T>
int split(T* a, int low, int high) {
T tm = a[high];
while(low < high) {
while(a[low] <= tm && low < high){
low ++;
}
swap(a[low], a[high]); /// swap
while (tm <= a[high] && low < high){
high --;
}
swap(a[low], a[high]); ///swap
}
return low;
}
template <typename T>
void quickSort(T* a, int low, int high) {
if(low < high) {
int key = split(a, low, high);
cout << "key:" << key <<endl;
quickSort(a,low, key-1);
quickSort(a,key+1, high);
}
}