专栏首页仙士可博客c语言实现快速排序

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C语言实现选择排序

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩...

    仙士可
  • C语言实现冒泡排序

    冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把...

    仙士可
  • C语言生成固定范围的随机数

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

    仙士可
  • 对数器应用-SelectionSort-选择排序

    sr
  • BucketSort-桶排序-计数排序

    sr
  • 堆排序

    下标从0开始,最后一个父节点位置为len/2-1 (len表示数组长度)           ( (len - 1)-1)/2            len...

    用户2965768
  • InsertSort-插入排序

    sr
  • CodeForces E. XOR and Favorite Number(Div.2)

     一个莫队的基础题,题目要求[L,R]里面有多少对子区间异或值为k,记录一下前缀异或和arr,因为x^x=0,现在我们要求区间[L,R]的异或和值,用arr...

    mathor
  • Java算法--堆排序

    solve
  • Java第二周学习

    数据类型: 告知编译器,当前数组中能够保存的数据类型到底是什么?并且在确定数据类型之后,整个数组中保存的数据类型无法修改!!! []:

    用户7073689

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动