快速排序 时间复杂度：元素互异时间复杂度O(n·logn)，最坏情况时间复杂度O(n^2)； 空间复杂度：O(1),原址排序，但是递归需要使用空间 最优的情况下空间复杂度为：O(logn)  ；每一次都平分数组的情况，最差的情况下空间复杂度为：O( n )；退化为冒泡排序的情况； 不稳定排序

QuickSort.c

// 快速排序
int quickSortUnit(int *arr, int p, int r) {
    int x = rand() % (r - p + 1) + p; // p到r以内的随机数
    swap(arr, x, r); // 交换随机出来的数和最后一数，作为主元
    int i = p-1;
    for (int j = p; j <= r-1; j++) {
        if (arr[j] <= arr[r]) { // 第r个元素作为主元元素
            i += 1;
            swap(arr, i, j);
        }
    }
    swap(arr, i+1, r);
    return i+1; //
}

void quickSort(int *arr,int p, int r) {
    if (p >=r ) {
        return;
    }
    int q = quickSortUnit(arr, p, r);
    quickSort(arr, p, q-1);
    quickSort(arr, q+1, r);
}