人人都來寫算法 之 快速排序

中午吃飯比較早，利用20分鐘把快速排序寫了下，以說明算法為主，采用int數組存儲數據。後續可以在以下兩點優化程序：

1. 采用模板編程，支持通用數據類型；

2. 采用函數指針或者函數對象決定排序方式。

#include <iostream>

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<<data[i]<<endl;
    }
    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<<data[i]<<endl; 
    } 
    getchar(); 
}