资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

web中怎么写一个快速排序的主体框架

本篇内容主要讲解“web中怎么写一个快速排序的主体框架”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“web中怎么写一个快速排序的主体框架”吧!

成都创新互联欢迎来电:18982081108,为您提供成都网站建设网页设计及定制高端网站建设服务,成都创新互联网页制作领域10年,包括成都社区文化墙等多个方面拥有多年的网站运维经验,选择成都创新互联,为网站锦上添花。

1、首先需要设置一个枢轴元素即setPivot(int i);

2、然后根据枢轴元素进行划分,将比枢轴元素大的排在右边,小的排在左边; 

3、分别对枢轴元素左边和右边的序列重复1和2的步骤进行划分,这是一个递归过程,整个代码框架很简单:

public void sort(int from, int to) {
        if (from >= to) {
            return;
        }
        setPivot(from);
        int partitionPos = partition(from, to);
        sort(from, partitionPos - 1);
        sort(partitionPos + 1, to);
  }

  每个子序列返回的条件是from >= to,由于枢轴元素是随机选择的,所以有以下几种划分情况:

1、轴枢元素正好能将序列分成均匀的两半,如果是奇数个元素那么子序列退出的条件是from==to,如果是偶数个元素如2个,那么会出现from>to的情况。

2、轴枢元素不能将序列分成均匀的两半,最极端的情况是轴枢元素将划分的序列总是比它大或者小,此时同样会出现from>to的情况。

实际上不管轴枢元素是否能将序列分成均匀的两半,只要序列的个数是偶数个一定会出现from>to的情况!

目前只描述了最终划分结果可能出现的情况,还没有说明如何划分,下面给出一个划分的方案:

    假设给定序列7、6、5、4、3、2、1,并选择4为枢轴,则示例代码如下:

int   partition(int from, int to) {   
        int right = to;
        int left = from;
        while (true) {
            while (comparePivot(right) > 0) {
                right--;
            }

            while (comparePivot(left) < 0) {
                left++;
            }
            if (left == right) {
                break;
            }
            swap(left, right);
        }

        return left;
    }

     验证一下:7和1进行交换,序列变成1、6、5、4、3、2、7;left=0;right=6;

                      6和2进行交换,序列变成1、2、5、4、3、6、7;left=1;right=5;

                      5和3进行交换,序列变成1、2、3、4、5、6、7;left=2;right=4;

                      left=3;right=3;退出循环

                      然后分别调用sort(0,2),sort(4,6),对于sort(0,2)的排序过程如下:

                       假设选取2为枢轴,由于原始序列已经有序,right=1;left=1;退出循环。 最后的两个递归是sort(0,0)以及sort(2,2),这两个递归会由于from==to条件直接退出。

                      sort(4,6)也是类似的情况。

到此,相信大家对“web中怎么写一个快速排序的主体框架”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!


网站标题:web中怎么写一个快速排序的主体框架
分享URL:http://cdkjz.cn/article/ghcgoe.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220