程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 快排序算法，排序算法

快排序算法，排序算法

編輯：C++入門知識

快排序算法，排序算法

快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n²)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(nlogn) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實作出來。

使用快速排序法對一列數字進行排序的過程

本文地址：http://www.cnblogs.com/archimedes/p/quick-sort-algorithm.html，轉載請注明源地址。

算法原理

快速排序采用一種“分而治之、各個擊破”的觀念。

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。

步驟為：

1、從數列中挑出一個元素，稱為 "基准"（pivot），

2、重新排序數列，所有元素比基准值小的擺放在基准前面，所有元素比基准值大的擺在基准的後面（相同的數可以到任一邊）。在這個分區退出之後，該基准就處於數列的中間位置。這個稱為分區（partition）操作。

3、遞歸地（recursive）把小於基准值元素的子數列和大於基准值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

算法實現

C代碼如下：

// Completed on 2014.10.9 19:09
// Language: C99
//
// 版權所有（C）codingwu   (mail: [email protected]) 
// 博客地址：http://www.cnblogs.com/archimedes/
#include <stdio.h>
#include <stddef.h>
void swap(int * a, int * b)  //交換函數
{  
    int tmp = * a;
    * a = * b;
    * b = tmp;
}
void printArray(int a[], int count)   //打印數組元素
{
    int i;
    for(i = 0; i < count; i++)
        printf("%d ",a[i]);
    printf("\n");
}
size_t partition(int * ary, size_t len, size_t pivot_i) //劃分函數
{   
    size_t i = 0;
    size_t small_len = 0;
    int pivot = ary[pivot_i];
    swap(&ary[pivot_i], &ary[len - 1]);
     for (; i < len; i++) {
          if (ary[i] < pivot) {
            swap(&ary[i], &ary[small_len]);
              small_len++;
        }
    }
    swap(&ary[len - 1], &ary[small_len]); //交換元素
    return small_len;
}
void quick_sort(int * ary, size_t len) 
{
    if (len == 0 || len == 1) return;
    size_t small_len = partition(ary, len, 0);
    quick_sort(ary, small_len);
    quick_sort(&ary[small_len + 1], len - small_len - 1);
}
int main(void) 
{
    int ary[] = {2, 4, 12, 25, 13, 5, 3, 1, 7, 6};
    size_t len = sizeof(ary) / sizeof(ary[0]);
    printArray(ary, len);
    quick_sort(ary, len);
    printArray(ary, len);
    return 0;
}

C89標准在stdlib.h中定義了抽象數據類型的快速排序函數qsort：

// Completed on 2014.10.9 19:20
// Language: C99
//
// 版權所有（C）codingwu   (mail: [email protected]) 
// 博客地址：http://www.cnblogs.com/archimedes/
#include <stdio.h>
#include <stdlib.h>
static int cmp(const void *a,  const void *b)
{
    return *(int *)a - *(int *)b;
}
void printArray(int a[], int count)   //打印數組元素
{
    int i;
    for(i = 0; i < count; i++)
        printf("%d ",a[i]);
    printf("\n");
}
int main()
{
    int arr[10] = {5, 3, 7, 4, 1, 9, 8, 6, 2};
    size_t len = sizeof(arr) / sizeof(arr[0]);
    printArray(arr, len);
    qsort(arr, 10, sizeof(int), cmp);
    printArray(arr, len);
    return 0;
}

有關qsort函數的其他用法可以參考：《C語言中qsort函數的應用》

qsort函數實現

參考minix內核代碼中qsort函數的實現：

整個qsort函數實現的是通用類型，也即是使用C模擬了泛型，使用了4個輔助函數，聲明如下：

static    void qsort1(char *, char *, size_t);
static    int (*qcompar)(const char *, const char *); 
static    void qexchange(char *, char *, size_t);
static    void q3exchange(char *, char *, char *, size_t);

在《C語言實現泛型編程》中有介紹，要實現泛型，對於簡單的元素的交換問題，實現起來必須轉換為字節塊的交換，這裡采用的是qexchange 函數來實現，代碼如下：

static void
qexchange(register char *p, register char *q,
      register size_t n)
{
    register int c;

    while (n-- > 0) {
        c = *p;
        *p++ = *q;
        *q++ = c;
    }
}

代碼中還有一個增強版的交換函數q3exchange，顧名思義實現的是三個字節區域塊內容的交換，代碼如下：

static void
q3exchange(register char *p, register char *q, register char *r,
       register size_t n)
{
    register int c;
    while (n-- > 0) {
        c = *p;
        *p++ = *r;
        *r++ = *q;
        *q++ = c;
    }
}

原理比較簡單，我就不具體解釋了。

核心函數是qsort1，代碼結構較為復雜，下面詳細剖析：

函數原型 static void qsort1(char *, char *, size_t);

第一個參數傳遞數組首地址，第二個參數傳遞最後一個元素的首地址

函數的劃分元選取的是數組中間元素：

left = a1;
right = a2;
lefteq = righteq = a1 + width * (((a2-a1)+width)/(2*width));

lefteq和righteq分別指向左右兩邊區域的邊界，對於左邊區域，實行下面的代碼：

while (left < lefteq && (cmp = (*qcompar)(left, lefteq)) <= 0) {
    if (cmp < 0) {  
        left += width;
    } else {
        lefteq -= width;
        qexchange(left, lefteq, width);  
    }
}

對於右邊區域，實行下面的代碼：

while (right > righteq) {
    if ((cmp = (*qcompar)(right, righteq)) < 0) {    
        if (left < lefteq) {
            qexchange(left, right, width);
            left += width;
            right -= width;
            goto again;
        }
        righteq += width;
        q3exchange(left, righteq, right, width);
        lefteq += width;
        left = lefteq;
    } else if (cmp == 0) {
        righteq += width;
        qexchange(right, righteq, width);
    } else right -= width;
}

goto語句跳轉到左邊區域代碼，直到左邊區域元素均小於lefteq指向的元素，也即是中間元。之後left==lefteq，此時當cmp<0，此時左邊已經沒有空位，righteq += width操作向右移動讓出一個位置，q3exchange(left, righteq, right, width)操作輪換三個位置的元素。

完整代碼如下：

/*
 * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
 * See the copyright notice in the ACK home directory, in the file "Copyright".
 */
/* $Header: qsort.c,v 1.3 90/08/28 14:03:24 eck Exp $ */

#include    <stdlib.h>

static    void qsort1(char *, char *, size_t);
static    int (*qcompar)(const char *, const char *);
static    void qexchange(char *, char *, size_t);
static    void q3exchange(char *, char *, char *, size_t);

void
qsort(void *base, size_t nel, size_t width,
      int (*compar)(const void *, const void *))
{
    /* when nel is 0, the expression '(nel - 1) * width' is wrong */
    if (!nel) return;
    qcompar = (int (*)(const char *, const char *)) compar;
    qsort1(base, (char *)base + (nel - 1) * width, width);
}

static void
qsort1(char *a1, char *a2, register size_t width)
{
    register char *left, *right;
    register char *lefteq, *righteq;
    int cmp;

    for (;;) {
        if (a2 <= a1) return;
        left = a1;
        right = a2;
        lefteq = righteq = a1 + width * (((a2-a1)+width)/(2*width));
        /*
           Pick an element in the middle of the array.
           We will collect the equals around it.
           "lefteq" and "righteq" indicate the left and right
           bounds of the equals respectively.
           Smaller elements end up left of it, larger elements end
           up right of it.
        */
again:
        while (left < lefteq && (cmp = (*qcompar)(left, lefteq)) <= 0) {
            if (cmp < 0) {
                /* leave it where it is */
                left += width;
            }
            else {
                /* equal, so exchange with the element to
                   the left of the "equal"-interval.
                */
                lefteq -= width;
                qexchange(left, lefteq, width);
            }
        }
        while (right > righteq) {
            if ((cmp = (*qcompar)(right, righteq)) < 0) {
                /* smaller, should go to left part
                */
                if (left < lefteq) {
                    /* yes, we had a larger one at the
                       left, so we can just exchange
                    */
                    qexchange(left, right, width);
                    left += width;
                    right -= width;
                    goto again;
                }
                /* no more room at the left part, so we
                   move the "equal-interval" one place to the
                   right, and the smaller element to the
                   left of it.
                   This is best expressed as a three-way
                   exchange.
                */
                righteq += width;
                q3exchange(left, righteq, right, width);
                lefteq += width;
                left = lefteq;
            }
            else if (cmp == 0) {
                /* equal, so exchange with the element to
                   the right of the "equal-interval"
                */
                righteq += width;
                qexchange(right, righteq, width);
            }
            else    /* just leave it */ right -= width;
        }
        if (left < lefteq) {
            /* larger element to the left, but no more room,
               so move the "equal-interval" one place to the
               left, and the larger element to the right
               of it.
            */
            lefteq -= width;
            q3exchange(right, lefteq, left, width);
            righteq -= width;
            right = righteq;
            goto again;
        }
        /* now sort the "smaller" part */
        qsort1(a1, lefteq - width, width);
        /* and now the larger, saving a subroutine call
           because of the for(;;)
        */
        a1 = righteq + width;
    }
    /*NOTREACHED*/
}

static void
qexchange(register char *p, register char *q,
      register size_t n)
{
    register int c;

    while (n-- > 0) {
        c = *p;
        *p++ = *q;
        *q++ = c;
    }
}

static void
q3exchange(register char *p, register char *q, register char *r,
       register size_t n)
{
    register int c;

    while (n-- > 0) {
        c = *p;
        *p++ = *r;
        *r++ = *q;
        *q++ = c;
    }
}

那種排序算法最快？

插入排序因為可以二分查找

快速排序算法

C語言程序：

/* 快速排序 */
#include "stdio.h"

void QuickSort(int e[], int first, int end)
{
int i=first,j=end,temp=e[first];
while(i<j)
{
while(i<j && e[j]>=temp)
j--;
e[i]=e[j];
while(i<j && e[i]<=temp)
i++;
e[j]=e[i];
}
e[i]=temp;
if(first<i-1)
QuickSort(e,first,i-1);
if(end>i+1)
QuickSort(e,i+1,end);
}

void main()
{
int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
int len = 8;
int i;
printf("before sort\n");
for(i=0; i<len; i++)
printf("%d ", arr[i]);
printf("\n");

QuickSort(arr, 0, len-1);

printf("after sorted\n");
for(i=0; i<len; i++)
printf("%d ", arr[i]);
printf("\n");
}