c语言实现快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

#include <stdio.h>

void swap(int *, int *);

void quickSort(int[], int, int);

void printArrString(int[], int);

int main() {
    int arr[] = {55, 17, 9, 87, 12, 41, 23, 14, 20, 32, 85};
    quickSort(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
    printArrString(arr, sizeof(arr) / sizeof(arr[0]));
    return 0;
}

void printArrString(int arr[], int length) {
    for (int i = 0; i < length; ++i) {
        if (i == 0) {
            printf("%d", arr[i]);
        } else {
            printf(",%d", arr[i]);
        }
    }
    printf("\n");
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quickSort(int arr[], int left, int right) {

    if (left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return;
    }

    int i = left;//当前最小范围
    int j = right;//当前最大范围
    int key = arr[left];//使用第一个值作为基准值
    for (; j > i; j--) {//从最后面开始往前查找
        if (arr[j] < key) {//如果有比基准值小的值
            swap(&arr[j], &arr[i]);//交换值
            //到这步的时候,可以100%确定比j大的值都小于基准值
            printf("b\n");
            printArrString(arr, right + 1);
            for (i++; i < j; i++) {//从最小范围后面开始查起
                if (arr[i] > key) {//如果大于基准值,
                    swap(&arr[i], &arr[j]);//则和j位置的数据交换
                    //到这步的时候,可以确定比j小的都小于基准值
                    printf("c\n");
                    printArrString(arr, right + 1);
                    break;
                }
            }
            //在这个时候,可能i和j并没有交叉(i和j中间还有没有查找完的值)
            //所以必须继续查询比基准值大/小的值,直到i==j,也就是i左边的值都比基准值大,右边的值都比基准值小
        }
    }
    //获得的左边的值,继续拆分,直到不能拆分(i>=j)
    quickSort(arr, left, i - 1);
    //获得的右边的值,继续拆分,直到不能拆分(i>=j)
    quickSort(arr, i + 1, right);
}

本文为仙士可原创文章,转载无需和我联系,但请注明来自仙士可博客www.php20.cn

• 上一篇： 手把手教你写一个composer包
• 下一篇： HTTP跨域详解和解决方式