快速排序

快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

快速排序过程
基本思想

1. 先从数列中取出一个数作为基准数。
2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3. 再对左右区间重复第二步，直到各区间只有一个数。

C语言实现

QuickSort.h

#include <stdio.h>

void QuickSort(int *arr, int left, int right)
{
    if (left < right)
    {
        int key = arr[left];
        int low = left;
        int high = right;
        while (low < high)
        {
            while (low < high && arr[high] > key)
                high--;
            arr[low] = arr[high];
            while (low < high && arr[low] < key)
                low++;
            arr[high] = arr[low];
        }
        arr[low] = key;
        QuickSort(arr, left, low - 1);
        QuickSort(arr, low+1, right);
    }
}

QuickSort_test.c

#include "QuickSort.h"

int main()
{
    int i;
    int arr[10] = {3, 5, 1, 4, 6, 8, 9, 7, 2, 0};
    for (i = 0; i < 10; i++)
        printf("%d ", arr[i]);
    printf("\n");
    QuickSort(arr, 0, 9);
    for (i = 0; i < 10; i++)
        printf("%d ", arr[i]);

    getchar();
    return 0;
}