快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。归并排序和快速排序一样均采用了分治法。
C语言实现:
来自算法导论的单向扫描算法,从左往右去扫描直到倒数第二个元素,出现小于最右边的元素则将小的那个元素与i标识的下标的元素交换,单向扫描法存在着冗余的元素交换,比如此时数组已有序1,2,3,4,5,6,单向扫描前5个元素均小于最后的元素6,那么每次都将自己与自己交换。C实现:

#include <stdio.h>

void swap(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int Partition(int *arr,int p,int r)
{
    int x, i;
    x=arr[r];
    i=p-1;
    for(int j=p; j<=r-1; j++)
    {
        if(arr[j]<=x)
        {
            swap(&arr[++i], &arr[j]);
        }
    }
    
    swap(&arr[++i],&arr[r]);
    
    return i;
}

void QuickSort(int *arr,int p,int r)
{
    if(p<r)
    {
        int q=Partition(arr,p,r);
        QuickSort(arr,p,q-1);
        QuickSort(arr,q+1,r);
    }
}

/*验证排序后的数组从小到大递增*/
int isSorted(int a[],int n)
{
    for(int i = 1;i < n;i++)
    {
        if(a[i] < a[i-1])
            return -1;
    }
    return 0;
}

int main()
{
    int a[10] = {7,8,2,10,9,1,5,4,3,6};
    QuickSort(a, 0,9);
    for(int i = 0;i < 10;i++)
        printf("%d ",a[i]);
    if(-1 == isSorted(a, 10))
    {
        printf("Error for selectionSort");
    }
    
    return 0;
}

另一种方法是从数组两端进行扫描,左侧扫描到大于"哨兵"的值,右侧扫描出小于"哨兵"的值,然后将两者交换,下面的算法来源于维基百科,仔细读来发现这个快速排序有点意思。我们更常见的形式是以a[left]作为哨兵。

#include <stdio.h>

void swap(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

void quick_sort_recursive(int arr[], int start, int end)
{
    if (start >= end)
        return;
    
    int key = arr[end];
    int left = start, right = end - 1;
    while (left < right)
    {
        while (arr[left] < key && left < right)
            left++;
        while (arr[right] >= key && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    /*如果arr[left] < key,那么arr[left]将数组分为两部分,否则key将数组分为两部分*/
    if (arr[left] >= key)
        swap(&arr[left], &arr[end]);
    else
        left++;
    /*上面left++是为了判断类似8 7 6 5 4这种情形,执行到此处时为4 7 6 5 8,此时left为0,无需继续递归排序左半部分*/
    if (left)
        quick_sort_recursive(arr, start, left - 1);
    
    quick_sort_recursive(arr, left + 1, end);
}

void quick_sort(int arr[], int len)
{
    quick_sort_recursive(arr, 0, len - 1);
}
/*验证排序后的数组从小到大递增*/
int isSorted(int a[],int n)
{
    for(int i = 1;i < n;i++)
    {
        if(a[i] < a[i-1])
            return -1;
    }
    return 0;
}

int main()
{
    int a[10] = {7,8,2,10,9,1,5,4,3,6};
    quick_sort_recursive(a, 0,9);
    for(int i = 0;i < 10;i++)
        printf("%d ",a[i]);
    if(-1 == isSorted(a, 10))
    {
        printf("Error for selectionSort");
    }
    
    return 0;
}