人人都来写算法 之 快速排序

中午吃饭比较早，利用20分钟把快速排序写了下，以说明算法为主，采用int数组存储数据。后续可以在以下两点优化程序：

1. 采用模板编程，支持通用数据类型；

2. 采用函数指针或者函数对象决定排序方式。

#include

using std::cout;
using std::endl;

/** Quick Sort **/
void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}

int partation(int dataArray[], int leftPos, int rightPos)
{
int pivot;
int last_small;
//todo:
int midPos = (leftPos + rightPos)/2;
swap(dataArray[leftPos], dataArray[midPos]);

pivot = dataArray[leftPos];
last_small = leftPos;

for(int i=leftPos+1; i<=rightPos; ++i)
{
if(dataArray[i] < pivot)
{
last_small = last_small +1;
swap(dataArray[last_small], dataArray[i]);
}
}
swap(dataArray[leftPos], dataArray[last_small]);

return last_small;
}

void quickSort(int data[], int leftPos, int rightPos)
{
int pivot_pos;
if(leftPos < rightPos)
{
pivot_pos = partation(data, leftPos, rightPos);
quickSort(data, leftPos, pivot_pos);
quickSort(data, pivot_pos+1, rightPos);
}
}

int main()
{
const int count = 10;
int data[count] = {7,2,6,4,0,9,5,1,3,8};

quickSort(data, 0, count-1);

for(int i = 0; i< count; i++)
{
cout< }
getchar();
}

[cpp] /** Quick Sort **/
void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}

int partation(int dataArray[], int leftPos, int rightPos)
{
int pivot;
int last_small;
//todo:
int midPos = (leftPos + rightPos)/2;
swap(dataArray[leftPos], dataArray[midPos]);

pivot = dataArray[leftPos];
last_small = leftPos;

for(int i=leftPos+1; i<=rightPos; ++i)
{
if(dataArray[i] < pivot)
{
last_small = last_small +1;
swap(dataArray[last_small], dataArray[i]);
}
}
swap(dataArray[leftPos], dataArray[last_small]);

return last_small;
}

void quickSort(int data[], int leftPos, int rightPos)
{
int pivot_pos;
if(leftPos < rightPos)
{
pivot_pos = partation(data, leftPos, rightPos);
quickSort(data, leftPos, pivot_pos);
quickSort(data, pivot_pos+1, rightPos);
}
}


int main()
{
const int count = 10;
int data[count] = {7,2,6,4,0,9,5,1,3,8};

quickSort(data, 0, count-1);

for(int i = 0; i< count; i++)
{
cout< }
getchar();
}