网站建议:179001057@qq.com

快速排序算法

技术2022-05-11  1

    递归的一个例子是快速排序。快速排序算法是C.A.R.Hoare于1962年发明的。对于一个给定的数组,从中选择一个元素(叫做分区元素),并把其余元素划分成两个子集合—一个是由所有小于分区元素的元素组成的子集合,另一个是由所有大于等于分区元素的元素组成的子集合。对这样两个子集合递归应用同一过程。当某个子集合中的元素数小于两个时,这个子集合不需要再排序,故递归停止。下面这个版本的快速排序函数可能不是最快的一个,但它是最简单的一个。在每一次划分子集合时都选取各个子数组的中间元素。

/* qsort:以递增顺序对v[left] ... v[right] 进行排序*/void qsort( int v[], int left, int right ){    int i, last;    void swap( int v[], int i, int j );    if ( left >= right )                            /* 若数组所包含的元素数少于两个,则什么也不做*/        return;    swap( v, left, (left + right)/2 );              /* 把分区元素移到v[0] */    last = left;    for ( i = left+1; i <= right; i++ )             /* 分区*/        if ( v[i] < v[left] )            swap( v, ++last, i );    swap( v, left, right );                         /* 恢复分区元素*/    qsort( v, left, last-1 );    qsort( v, last+1, right );}

之所以把数组元素交换操作作为一个独立的函数swap,是因为它在qsort函数中要使用三次。/* swap:交换v[i]与v[j]的值*/void swap( int v[], int i, int j ){    int temp;    temp = v[i];    v[i] = v[j];    v[j] = temp;}


最新回复(0)