快速排序

引子：

快速排序算是归并排序的一个改进吧，思路也是递归二分。

而区别是归并排序使用的中点是随机数列的索引中点，而快速排序使用的中点是一个具体的值，这个值的初始值是随机的，可以定为数组的第1个元素，也可以是第x个。

需要经过一轮切分，来确定这个“中点值”，切分操作还会让让小于中点值的数都放到左边，大于中点的值数都放到右边，所以这一轮切分中会有很多次中点左右两边的交换。

然后再次从左边开始切分成两块，这样不断的递归，递归退出的条件是最左边数索引大于最右边数的索引。

整体逻辑如下：

void QuickSort(int* ua, int nStart, int nEnd)  
{  
    //递归退出条件   
    if(nStart >= nEnd)  
    {  
        return;  
    }  
    int nMid = QuickPartition(ua, nStart, nEnd);  
    QuickSort(ua, nStart, nMid-1);  
    QuickSort(ua, nMid+1, nEnd);  
}  

void QuickSort(int* ua, int nStart, int nEnd)
{
//递归退出条件
if(nStart >= nEnd)
{
return;
}
int nMid = QuickPartition(ua, nStart, nEnd);
QuickSort(ua, nStart, nMid-1);
QuickSort(ua, nMid+1, nEnd);
}

而切分的具体逻辑如下：

int QuickPartition(int* ua, int nStart, int nEnd)  
{  
    int i = nStart;  
    int j = nEnd + 1;  
  
    //中点值   
    int nFlagValue = ua[nStart];  
  
    while(1)  
    {  
        //找到左边大于中点的值，记录索引   
        while( ua[++i] < nFlagValue )  
        {  
            if( i == nEnd)  
            {  
                break;  
            }  
        }  
        //找到右边小于中点的值，记录索引   
        while( ua[--j] > nFlagValue )  
        {  
            if( j == nStart)  
            {  
                break;  
            }  
        }  
        //两边向中间靠拢的过程中相遇则退出   
        if( i >= j)  
        {  
            break;  
        }  
        //交换两边的值   
        swap( ua[i], ua[j] );  
    }  
    //最后一个从右边换过来的值与中点值交换位置，   
    //保证中点值的左边都小于中点值，右边都大于中点值   
    swap( ua[nStart], ua[j] );  
  
    //返回将右边最后一个小于中点值的数的索引，做为右边部分的中点值。   
    return j;  
}  

int QuickPartition(int* ua, int nStart, int nEnd)
{
int i = nStart;
int j = nEnd + 1;

//中点值
int nFlagValue = ua[nStart];

while(1)
{
//找到左边大于中点的值，记录索引
while( ua[++i] < nFlagValue )
{
if( i == nEnd)
{
break;
}
}
//找到右边小于中点的值，记录索引
while( ua[--j] > nFlagValue )
{
if( j == nStart)
{
break;
}
}
//两边向中间靠拢的过程中相遇则退出
if( i >= j)
{
break;
}
//交换两边的值
swap( ua[i], ua[j] );
}
//最后一个从右边换过来的值与中点值交换位置，
//保证中点值的左边都小于中点值，右边都大于中点值
swap( ua[nStart], ua[j] );

//返回将右边最后一个小于中点值的数的索引，做为右边部分的中点值。
return j;
}

切分的过程是这样的：

1，先确定中点值，本算法是取随机数组的第一个数。

2，从第2个数向右遍历，直到找到大于中点值的数，记录索引。

3，从最后一个数向左遍历，直到找到小于中点值的数，记录索引。

4，如果上述两个索引已经相遇或交错，那么退出此过程，否则交换两个值，让大值去右边，小值去左边。

5，直到两个索引相遇或交错。

6，因为第一个值，也就是中间值，是没有参与上面的交换的过程的，所以他是大于右边交换过来的值的，为了保证中间值的左边都小于中间值，需要将此中间值与最后一个从右边换到左边的值的位置交换。

7，返回当前中点值的位置，也就是从第6步中交换得来的值，做为右边部分的中点值。

到此，一轮切分完成，也顺利地将中间值从第一个位置移动到了左右两边临界的位置。

接下来就是递归地重复上面的过程了。

补充：软件开发 , C++ ,