快速排序（正序+倒序）C语言版

#include <stdio.h>

void sort(int *, int, int);
void sort(int arr[], int left, int right)
{
    // 如果数组（子数组）只有1个元素时直接返回
    if (left == right) {
        return;
    }

    // i为左向右移动位置指针,j为右向左移动位置指针
    int i, j, tmp;
    // 第1个元素作为本轮排序的参考值
    i = left + 1;
    j = right;

    while (i < j) {
        // 必须j先查找，条件匹配即停止
        // while (i < j && arr[j] > arr[left]) {
        while (i < j && !(arr[j] <= arr[left])) {
            j--;
        }

        // i开始查找，条件匹配即停止
        // while (i < j && arr[i] <= arr[left]) {
        while (i < j && !(arr[i] > arr[left])) {
            i++;
        }

        // 交换i和j位置的数值，可能是两个位置，也可能是同位置（虽然多余，但不影响结果）
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 执行到这里本轮的i，j查找已经结束，且两者位置重合，重合位置为拆分数组的分隔点
    // 参考值>i位置交换（因本次为正序）
    if (arr[left] > arr[i]) {
        tmp = arr[left];
        arr[left] = arr[i];
        arr[i] = tmp;
    }

    // 拆分为2个数组递归，左子数组不包含拆分点，右数组在至少包含拆分点本身1个元素（在本轮子数组为2个元素时的情况）
    sort(arr, left, i - 1);
    sort(arr, i, right);
}

int main(void)
{
    int arr[] = {12, 3, 7, 25, 11, 5, 23, 5, 0};
    int length;
    length = sizeof(arr) / sizeof(int);
    sort(arr,  0, length - 1);
    printf("-------------------\n");
    for ( int i = 0; i < length; i++ ) {
        printf("%d, ", arr[i]);
    }
    printf("\n");
    return 0;
}

倒序

#include <stdio.h>

void sort(int *, int, int);
void sort(int arr[], int left, int right)
{
    if (left == right) {
        return;
    }

    int i, j, tmp;
    i = left + 1;
    j = right;

    while (i < j) {
        while (i < j && arr[j] < arr[left]) {
        //while (i < j && !(arr[j] >= arr[left])) {
            j--;
        }

        while (i < j && arr[i] >= arr[left]) {
        //while (i < j && !(arr[i] < arr[left])) {
            i++;
        }

        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    if (arr[left] < arr[i]) {
        tmp = arr[left];
        arr[left] = arr[i];
        arr[i] = tmp;
    }

    sort(arr, left, i - 1);
    sort(arr, i, right);
}

int main(void)
{
    int arr[] = {12, 3, 7, 25, 11, 5, 23, 5, 0};

    int length;
    length = sizeof(arr) / sizeof(int);
    sort(arr,  0, length - 1);
    printf("-------------------\n");
    for ( int i = 0; i < length; i++ ) {
        printf("%d, ", arr[i]);
    }
    printf("\n");

    return 0;
}

快速排序（正序+倒序）C语言版

原文：https://blog.51cto.com/sndapk/2609551