教你学习快速排序算法-程序员必备哦

栏目: IT资讯 · 发布时间: 5年前

内容简介:排序这个序列:6 1 2 7 9 3 4 5 10 8

举个例子

排序这个序列:6 1 2 7 9 3 4 5 10 8

  • 步骤1:选择一个基准数作为对比的开始值,这里选择第一个数6:
  • 步骤2、先从右往左找一个小于 6 的数,再从左往右找一个大于 6 的数。

教你学习快速 <a href='https://www.codercto.com/topics/21904.html'>排序</a> 算法-程序员必备哦

  • 步骤3、然后交换他们

教你学习快速排序算法-程序员必备哦

变成这样子:

教你学习快速排序算法-程序员必备哦

继续执行步骤2和3,直到两个哨兵相遇,:

教你学习快速排序算法-程序员必备哦 教你学习快速排序算法-程序员必备哦

左右两个哨兵都走到3:

教你学习快速排序算法-程序员必备哦
  • 步骤4:将开始选择基准数字6换到中间,测试6左边的数都小于6,右边的数都大于6。完成第一次循环:

教你学习快速排序算法-程序员必备哦 教你学习快速排序算法-程序员必备哦

第一次完成之后,再按照此方法分别对6左右两边的数列进行递归排序即可。是不是很简单。

看下代码就更清晰了:

void quicksort(int a[], int left,int right)
    {
        int i,j,t,temp;
        if(left>right)
            return;

        temp=a[left]; //temp中存的就是基准数
        i=left;
        j=right;
        while(i!=j)
        {
            //顺序很重要,要先从右边开始找
            while(a[j]>=temp && i<j)
                j--;
            //再找右边的
            while(a[i]<=temp && i<j)
                i++;
            //交换两个数在数组中的位置
            if(i<j)
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
        //最终将基准数归位
        a[left]=a[i];
        a[i]=temp;

        quicksort(a, left,i-1);//继续处理左边的,这里是一个递归的过程
        quicksort(a, i+1,right);//继续处理右边的 ,这里是一个递归的过程
    }

也可以这么写:

/**
     * 快排
     * @param arr
     * @param low
     * @param high
     * @return
     */
    public static int[] quit(int arr[], int low, int high) {
        int l = low;
        int h = high;
        int key = arr[l];  //先找出一个数作为基准数(这里取数组最中间的一位)

        while (l < h) {
            while (l < h && arr[h] >= key) h --; //从后向前:寻找比基准数小的数据,如果找到,停下来
            if (l < h) {  //“探测”到了符合要求的数据,则交换数据,继续顺着方向寻找
                arr[l] = arr[h];
                l ++;
            }
            while (l < h && arr[l] <= key) l ++; //从前向后:寻找比基准数大的数据,如果找到,停下来
            if (l < h) { ////“探测”到了符合要求的数据,则交换数据,继续顺着方向寻找
                arr[h] = arr[l];
                h --;
            }
        }
        arr[l] = key;
        if (l > low) quit(arr, low, l - 1);
        if (h < high) quit(arr, h + 1, high);
        return arr;
    }

热度: 1


以上所述就是小编给大家介绍的《教你学习快速排序算法-程序员必备哦》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

游戏运营:高手进阶之路

游戏运营:高手进阶之路

饭大官人 / 电子工业出版社 / 2018-1-1 / 79.00元

《游戏运营:高手进阶之路》是一本系统的、成体系的、注重运营效能、强化系统思维、提升专业认知的书籍。《游戏运营:高手进阶之路》几乎完整覆盖了一个游戏运营人员日常工作中的方方面面,并从工作中具体的业务场景出发,归纳整理出各种解决问题的方法论。《游戏运营:高手进阶之路》为广大游戏从业者建立了完整的知识技能成长体系,包含两大岗位基本功—内容输出和协作推进,四大职业技能—活动策划、版本管理、用户运营、数据分......一起来看看 《游戏运营:高手进阶之路》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具