快速排序算法之我見（附上C代碼）

因為<The C Programming Language>一書中有一個練習，需要用到快速排序，所以又復習了一下，感覺收獲頗多，故而分享之。

快速排序的核心是一種 divide and conquer 算法。可惜我們接觸的中文書籍裡面，突出強調了一趟快速排序怎麼做，而沒有重點介紹這種編程思想，可謂是本末倒置。單就一趟排序的細節來說，有很多中實現版本，每種版本都是處於不同的考慮。我們在那本藍皮的《數據結構》當中學到的快速排序是一種 in-place quick sort。這個版本對空間復雜度做了優化，使得實現當中不需要占用額外的空間，空間復雜度為O(1)。不過，細節上我覺得，沒必要設置兩個變量i,j，然後從兩頭開始比較，因為這樣和設置一個變量一樣，都需要O(n)次比較。所以，我做了一些改變。

代碼：

[cpp]
void qsort(char *listptr[], int left, int right) 
{ 
    int pivot = 0; 
 
    // First, partition operation  
    pivot = partition(lineptr, left, right); 
 
    if (left < pivot) 
    // recursively quick sort the former part if its length greater than 1  
        qsort(lineptr, left, pivot); 
    // recursively quick sort the latter part if its length greater than 1  
    if ((pivot+1) < right) 
        qsort(lineptr, pivot+1, right); 
} 
 
int partition(char *listptr[], int left, int right) 
{ 
    int pivot = left, i = left+1; 
 
    for (; i < right; i++) 
    {    
        if (listptr[i][0] < listptr[pivot][0]) { 
            swap(&listptr[i], &listptr[pivot]); 
            pivot = i; 
        }    
    }    
 
    return pivot;    
} 

void qsort(char *listptr[], int left, int right)
{
    int pivot = 0;

    // First, partition operation
    pivot = partition(lineptr, left, right);

    if (left < pivot)
    // recursively quick sort the former part if its length greater than 1
        qsort(lineptr, left, pivot);
    // recursively quick sort the latter part if its length greater than 1
    if ((pivot+1) < right)
        qsort(lineptr, pivot+1, right);
}

int partition(char *listptr[], int left, int right)
{
    int pivot = left, i = left+1;

    for (; i < right; i++)
    {  
        if (listptr[i][0] < listptr[pivot][0]) {
            swap(&listptr[i], &listptr[pivot]);
            pivot = i;
        }  
    }  

    return pivot;  
}