Xcode(C++) 快速排序实现
//
// main.cpp
// QuickSort
//
// Created by mac on 12-10-3.
// Copyright (c) 2012年 Roc. All rights reserved.
//
#include <iostream>
using namespace std;
template <class T>
void qSort(T* a,size_t low, size_t high);//主调用函数,利用分治法
template <class T>
size_t partition(T* base ,size_t low ,size_t high);//依据基准记录进行分区
template <class T>
size_t selectPivotKey(T* base ,size_t low ,size_t high);//返回挑选基准的记录,常用的是三值法,这里就用最左边的那个了,简化起见
template <class T>
void qSort(T* base,size_t low, size_t high){
if (low< high) {
size_t pivotKey = partition(base, low, high);
qSort(base, low, pivotKey-1);
qSort(base, pivotKey+1, high);
}//if
}
template <class T>
size_t partition(T* base ,size_t low ,size_t high){
T* temp =new T();
int pivotkey = selectPivotKey(base, low, high);
*(temp)= base[pivotkey];
while (low<high) {
while(low<high && base[high]<= *(temp)) high--;
if (pivotkey!=low)
base[low]= base[high];
else base[pivotkey]= base[high]; //这里是和课本不同之处
while(low<high && *(temp)<=base[low]) { low++;
}
base[high]=base[low];
}//while
base[low]=*(temp);
delete temp;
return low;
}
template <class T>
size_t selectPivotKey(T* base ,size_t low ,size_t high) {
return low;
}
int main(int argc,const char * argv[])
{
int a[]={15,9,8,1,4,11,7,12,13,6,5,3,16,2,10,14};
qSort(a, 0,sizeof(a)/sizeof(int)-1);
for (int i=0; i<sizeof(a)/sizeof(int); i++) {//sizeof(a)/sizeof(int)
cout<<a[i]<<",";
}
// insert code here...
std::cout <<"\n快速排序测试!"<<endl;
return 0;
}
