40.C语言 数组排序 – 快速法排序

最后更新于:2020-08-16 22:02:39

一.简介

经过前面的学习,我们已经学会了数组遍历,在开发中,我们经常回碰到对数组进行排序,例如:学习成绩排序,身高排序,年龄排序等等;C语言中常见的数组排序一共有四种:

1.冒泡法排序

2.选择法排序

3.插入法排序

4.快速法排序

二.数组快速法排序原理

快速排序法号称是目前最优秀的算法之一,实现思路是,将一个数组的排序问题看成是两个小数组的排序问题,而每个小的数组又可以继续看成更小的两个数组,一直递归下去,直到数组长度大小最大为2。

三.数组快速法排序实战

/************************************************************************/
/*@文件名      : 数组快速法排序实战.cpp
/*@日  期      : 2020/07/25 21:52
/*@作  者      : 猿说编程
/*@公众号      : 猿说编程
/*@博客        : www.shuopython.com
/*@描述        : C语言教程 - 数组快速法排序实战
/************************************************************************/

#include<stdlib.h>
#include<stdio.h>


//快速排序 
void quickSort(int *arr, int l, int r)
{
    //此处编写代码实现快速排序
    int i, j, x, temp;
    if (l < r)
    {
        i = l;
        j = r;
        x = arr[(l + r) / 2];
        //以中间元素为轴 
        while (1)
        {
            while (i <= r && arr[i] < x)
                i++;
            while (j >= 0 && arr[j] > x)
                j--;
            if (i >= j) //相遇则跳出 
                break;
            else
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                //交换 
            }
        }
        quickSort(arr, l, i - 1); //对左半部分进行快排 
        quickSort(arr, j + 1, r); //对右半部分进行快排 
    }
}

void main()
{
    int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 10 };
    int len = sizeof(a) / sizeof(int);

    for (int i = 0; i < len; i++)
    {
        printf("排序之前:index:%d  value:%d\n", i, a[i]);
    }

    //快速法排序
    quickSort(a, 0, 9);
    printf("-----------------------------------\n");


    for (int i = 0;i<len;i++)
    {
        printf("排序之后:index:%d  value:%d\n", i, a[i]);
    }


    system("pause");
}
输出:
排序之前:index:0  value:9
排序之前:index:1  value:8
排序之前:index:2  value:7
排序之前:index:3  value:6
排序之前:index:4  value:5
排序之前:index:5  value:4
排序之前:index:6  value:3
排序之前:index:7  value:2
排序之前:index:8  value:1
排序之前:index:9  value:10
-----------------------------------
排序之后:index:0  value:1
排序之后:index:1  value:2
排序之后:index:2  value:3
排序之后:index:3  value:4
排序之后:index:4  value:5
排序之后:index:5  value:6
排序之后:index:6  value:7
排序之后:index:7  value:8
排序之后:index:8  value:9
排序之后:index:9  value:10
请按任意键继续. . .


猜你喜欢

1. 三目运算符

2. 逗号表达式

3. NaN(Not a Number)

4. memcpy/strcpy/strcpy_s 区别

5. unicode 和多字节区别

6. 数组定义和使用

7. 数组遍历

8. _WIN32/WIN32/_WIN64/WIN64区别

9. Debug和_DEBUG区别

10. 判断windows操作系统是x86/x64

11. 数组排序 – 冒泡法排序

12. 数组排序 – 选择法排序




转载请注明: 猿说编程 » C/C++教程 » 数组排序 – 快速法排序

赞赏

微信赞赏支付宝赞赏