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);
}
目录
相关文章
|
29天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
52 4
|
2月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
6月前
|
C语言
【C语言】: 快速排序——qsort函数的介绍
【C语言】: 快速排序——qsort函数的介绍
49 0
|
存储 算法
玩转快速排序(C语言版)
玩转快速排序(C语言版)
78 0
|
7月前
|
C语言
【C语言/数据结构】排序(快速排序及多种优化|递归及非递归版本)
【C语言/数据结构】排序(快速排序及多种优化|递归及非递归版本)
50 0
|
7月前
|
算法 C语言
C语言之冒泡排序、快速排序法、希尔排序法
C语言之冒泡排序、快速排序法、希尔排序法
|
算法 搜索推荐 C语言
c语言写快速排序代码
c语言写快速排序代码
|
7月前
|
搜索推荐 C语言
【c语言】快速排序
【c语言】快速排序
35 0
|
算法 搜索推荐 编译器
一文带你学透快排(快速排序C语言版)
一文带你学透快排(快速排序C语言版)
|
存储 算法 C语言
【数据结构】深入浅出理解快速排序背后的原理 以及 版本优化【万字详解】(C语言实现)
【数据结构】深入浅出理解快速排序背后的原理 以及 版本优化【万字详解】(C语言实现)
79 0