算法原理

快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)，最差情况下复杂度为O(n^2)。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码实现

#include <stdio.h>

void print_arr(int arr[], int len);

void quick_sort(int arr[], int left, int right);

int main(int argc, const char * argv[]) {
    int arr[10] =  {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    print_arr(arr, 10);
    quick_sort(arr, 0, 9);
    print_arr(arr, 10);
    return 0;
}

void quick_sort(int arr[], int left, int right) {
    if (left < right) {
        int i = left, j = right, current = arr[left];
        while (i < j) {
            while (i < j && arr[j] > current)
                j--;
            if (i < j)
                arr[i++] = arr[j];
            while (i < j && arr[i] < current)
                i++;
            if (i < j)
                arr[j--] = arr[i];
        }
        arr[i] = current;
        quick_sort(arr, left, i-1);
        quick_sort(arr, i+1, right);
    }
}

void print_arr(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}