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;

}