锐客网

  1. 首页 > it技术 > >

C/C++实现快速排序(两种方式)图文详解

目录

  • 介绍
  • 实现
    • 方式一
    • 方式二
  • 总结

    介绍 快速排序是对冒泡排序算法的一种改进，快速排序算法通过多次比较和交换来实现排序。

    流程如下：

    C/C++实现快速排序(两种方式)图文详解
    文章图片


    实现 以下有两种实现方式，说是两种，其实就是在交换元素时具体细节上有点不同罢了。

    方式一
    int Partition(int A[],int low,int high){ int pivot=A[low]; //第一个元素作为基准 while(low=pivot) high--; A[low]=A[high]; while(low
    该方式，先把基准元素保存起来

    如下图数组，把49看作基准元素，先移动high指针，当指向27时退出while循环，把27放到low位置

    C/C++实现快速排序(两种方式)图文详解
    文章图片


    【C/C++实现快速排序(两种方式)图文详解】C/C++实现快速排序(两种方式)图文详解
    文章图片


    这时候，high位置就空出来一个，那么让low移动，移动到下图所示时，65>49，退出while循环，再将65放到high位置

    C/C++实现快速排序(两种方式)图文详解
    文章图片


    这样low这个位置又空出来了，再移动high，如此反复。

    C/C++实现快速排序(两种方式)图文详解
    文章图片


    最后得到如下图的情况：

    C/C++实现快速排序(两种方式)图文详解
    文章图片


    这样我们就按照“49”，把数组分为了左右两部分。

    对左右两部分分别进行上述操作即可。

    C/C++实现快速排序(两种方式)图文详解
    文章图片


    方式二
    void Quick_sort(int left,int right,int arr[]){ if(left>=right)return; int i,j,base,temp; i=left,j=right; base=arr[left]; while(i=base && i
    对于第二种方式，看下图即可很好理解。

    高低指针不是轮流替换空余位置，而是同时找到不符合的元素，然后交换二者。

    最后，高低指针相遇，再把基准元素与相遇位置上的元素交换即可。

    C/C++实现快速排序(两种方式)图文详解
    文章图片


    C/C++实现快速排序(两种方式)图文详解
    文章图片


    C/C++实现快速排序(两种方式)图文详解
    文章图片


    C/C++实现快速排序(两种方式)图文详解
    文章图片


    总结 本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注脚本之家的更多内容！

      推荐阅读


      上一篇：禾连科技一面面经

      下一篇：使用BigInteger实现除法取余