学步园

快速排序又称为分区交换排序，其基本思想是：首先选一个轴值（即比较的基准），将待排序记录分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。

    int qsort(int v[], int left, int right) 
    {
        int last, i;
        if(left >= right)        //只有一个数据的时候，不用排了 
            return;
        swap(v, left, (left+right)/2);       //基准点本是中间位置的数据，这里把它换到了第一的位置
        last = left;    //last以前的都是小于left（基准点）的数据。last是最后一个小于基准点的数据的位置。基准点是left。 
        for(i=left+1; i<=right; i++)
        {
            if(v[i] < v[left])
                swap(v, ++last, i);              
        }   
        /*
        交换left与last的位置，因为left中保存的是基准点，而前面的一次划分，
        已经将比基准点小的数据都放在了下标小于等于last的位置上，而比基准点大的数据，
        都放在了last的后面。这里交换后，就保证基准点前面的数据都比他小。
        */
        swap(v, left, last);    //将基准点再放回中间的位置,基准点在last的位置上.这样做的好处是，保存了排序后基准点的位置。 
       
        qsort(v, left, last-1); 
        qsort(v, last+1, right);
    }
    
    void swap(int v[], int i, int j)
    {
        int temp ;
        temp = v[i];
        v[i] = v[j];
        v[j] = temp;     
    }

数据结构书本里的算法，比上面的容易理解，以第一个数值为轴值。

    int partition(int v[], int left, int right)
    {
        int i = left, j = right;
        while(i < j)    //这个条件很重要 
        {
            //以第一个值为基准值 
            while(i<j && v[i]<=v[j]) j--;   //右侧扫描 
            if(i < j)
            {
                 swap(v, i, j);
                 i++;
            }
                  
            while(i<j && v[i]<=v[j]) i++;   //左侧扫描 
            if(i < j)
            {
                 swap(v, i, j);
                 j--;
            }                 
        }   
        return i;
        
    }
    
    void QuickSort(int v[], int left, int right)
    {
         int pivot;
        if(left < right)
        {
            pivot = partition(v, left, right);   //第一次划分 
            QuickSort(v, left, pivot-1);         //左侧排序 
            QuickSort(v, pivot+1, right);        //右侧排序 
        }     
    }

最简单易理解的：

    void myQuickSort(int v[], int left, int right)
    {
        int i,j;
        i = left - 1;
        for(j=left; j<=right; j++)
        {
            if(v[j] <= v[right])
            {
                i++;
                swap(v, i, j);    
            }                        
        } 
        swap(v, i+1, right);    
        return i+1;
    }

写算法主要是理解思想，具体形式可以变化很多。自勉之~