排序算法:快速排序 QuickSort

快速排序的的基本思路是: 通过一次排序,将数组分割为   参考值(1个值)、较大(比参考值都大的一群)、较小值(比参考值度小的一群) 3部分。然后将较大的部分和较小的部分视为2个数组进行再次排序,整个排序过程使用递归进行,以此达到整个数组的排列。  如下图:

在排序过程中可以设置任意一个数组元素为参考值,但是为了遍历的方便性 可以采用头尾使代码更简单,上图r(最后一个元素)为参考值。

j指针为每次遍历的下标,i指针则标识分隔符i之前的素组则都比r小,i之后的则都比r大,
每次遍历j都和r比较,如果j < r则进行i 和j的交换然后i的指针+1 , 到最后一轮时,r和i进行交换,则形成一个结果  比 [r小的区域,  r , 比r大的区域]  依次再次对左右2个区域进行相同的处理。

代码如下…

void sort_quick(int* array, int start, int end)
{
    
    if(start >= end)
    {
        return;
    }
    int valueR = array[end];
    
    int i = start; //从i之后为比r大的  i之前比r 要小。
    int j; //当前游标
    for(j = start; j<end; j++)
    {
        int v = array[j];
        if( v < valueR )
        {
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
            ++i;
        }
        //else if(v>valueR){}
    }
    
    int tmp = array[i];
    array[i] = valueR;
    array[end] = tmp;
   
    sort_quick(array, start ,  i -1 );
    sort_quick(array,  i + 1 , end);
}


int a[] = {2,8,7,1,3,5,6,4};        
int len= (sizeof(a) / sizeof(int));
sort_quick(a, 0, len-1);
发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>