C语言实现快速排序算法实例

2022-11-13 10:11:30 算法 排序 实例

首先我们要对一组数据进行排序：

在数组中选一个基准数（通常为数组第一个，黄圈圈标记了）；

将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边，怎么移动，后面说；

对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。

好了，咱们开始吧！

快速排序需要两个哨兵，i 和 j,分别指向数组的头和尾。接下来就要进行移动。

我们通常选择第一个元素作为基准数，去移动数组元素，使其达到这个基准数的左边都是小于它的，右边都是大于它的。开始移动 i 和 j , i 和 j 是交互移动的，这里我们需要先移动 j，这是为甚呢，原因是先移动 j,等到这一行移动结束，i 的下一个就是 j 的时候，我们先移动 j ,可以避免将数据移动错误，后面会有体会。

当移动 j 时，就开始比较 j 是否比基准数大，如果大于或者等于就 j–,否则再看 i,如果 i 小于等于6，则i++ 再与基准数进行比较,否则 i 就要与 j指向的值互换，我们拿上面那个看

第一步：看j的值比6小，然后看i，i的值是6,所以i++,后面 i继续++，4，3，5都比6小，所以 i 就移动到了7下面。

到这里，j 所指向的值要与 i 所指向的值互换。

互换完成，后面在比较 j 所指向的位置是否比基准数大，如果大就 j–;

这里 7 ， 9 ,都比6大，所以j–,进行两次，j 就到达了4的下面。

4比6小，所以要再看 i，i 指向0，所以 i需要 i++,到 1，1也小于6, 所以 i 还需要++，到这里 i 就和 j指向同一个数4，

然后 i = j 了，不能够满足条件，所以就要进行互换，将 i 指向的数，与基准数互换，这一轮比较就结束了，

到这里，基准数6的左边都比6小，右边都比6大。后面还是按照这个来分别再基准数6的左右开始比较。

后面就找这样来，在左右两边再各自将第一个元素作为基准数进行排序。

以此类推，就好了，我把代码贴上。

#include <stdio.h>

#define SIZE 6

//快速排序
void quick_sort(int num[], int low, int high )
{
    int i,j,temp;
    int tmp;

    i = low;
    j = high;
    tmp = num[low];   //任命为中间分界线，左边比他小，右边比他大,通常第一个元素是基准数

    if(i > j)  //如果下标i大于下标j，函数结束运行
    {
        return;
    }

    while(i != j)
    {
        while(num[j] >= tmp && j > i)   
        {
            j--;
        }

        while(num[i] <= tmp && j > i)
        {
            i++;
        }

        if(j > i)
        {
            temp = num[j];
            num[j] = num[i];
            num[i] = temp;
        }
    }

    num[low] = num[i];
    num[i] = tmp;

    quick_sort(num,low,i-1);
    quick_sort(num,i+1,high);
}

int main(int arGC , char **argv)
{
    //创建一个数组
    int num[SIZE] ={0};
    int i;

    //输入数字
    for(i =0; i < SIZE; i++)
    {
        scanf("%d",&num[i]);
    }

    quick_sort(num, 0, SIZE-1);

    for(i = 0; i < SIZE; i++)
    {
        printf(" %d ", num[i]);
    }

    return 0;
}

总结

到此这篇关于C语言实现快速排序算法的文章就介绍到这了,更多相关C语言快速排序内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

相关文章