快速排序

思想：
选一个基准值， 将大于它的放右边， 小于它的放左边。找到该基准值的下标， 然后继续递归调用。

代码实现

// 快速排序
void quickSort(int a[], int n) {
    if (n <= 1) {
        return;
    }
    quickSort_c(a, 0, n - 1);
    
    for (int i = 0; i < n; i++) {
        NSLog(@"%d", a[i]);
    }
}

// 递归函数
void quickSort_c(int a[], int left, int right) {
    // 递归终止条件
    if (left >= right) {
        return;
    }
    // 找到分区下标
    int q = partionSection1(a, left, right);
    // 递归调用
    quickSort_c(a, left, q - 1);
    quickSort_c(a, q + 1, right);
}

找到基准值的下标
分区实现一

int partionSection1(int a[], int left, int right) {
    int i, j, pivot;
    i = left;
    // 取一个标注数， 将小于它的放左边， 大于它的放右边
    pivot = a[right];
    // 利用选择排序思想
    for (j = left; j <= right - 1; j++) {
        if (a[j] < pivot) {
            int temp = a[j];
            a[j] = a[i];
            a[i] = temp;
            i = i + 1;
        }
    }
    int tempR = a[i];
    a[i] = a[right];
    a[right] = tempR;
    return i;
}

分区实现二

int partionSection2(int a[], int left, int right) {
    int i = left;
    int j = right;
    int key = a[left]; // 基准值
    while (i < j) {
        while (i < j && a[j] >= key) {
            j--;  // 左移
        }
        a[i] = a[j];
        while (i < j && a[i] <= key) {
            i++;  // 右移
        }
        a[j] = a[i];
    }
    a[i] = key;
    return i;
}

使用

int a[] = {4, 13, 2, 1, 7, 9, 10, 8, 3, 6};
    int num = sizeof(a) / sizeof(int);
    quickSort(a, num);

💚细品分区一和分区二的实现