文档章节

排序––快速排序(二)

F
 FAT_mt
发布于 08/25 21:46
字数 793
阅读 11
收藏 0

根据排序––快速排序(一)的描述,现准备写一个快速排序的主体框架:

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)也是类似的情况。

                    最后整个序列就是有序序列,由此看来该程序貌似正确,但是此情况比较特殊,为了能适应一般的情况,还需改进。其实正确的快速排序代码量很少,但是要把各种情况分析到位,写一个正确的快速排序代码个人认为起码没有其它排序算法那么简单。

© 著作权归作者所有

F

FAT_mt

粉丝 5
博文 88
码字总数 52536
作品 3
南京
高级程序员
私信 提问
Lua--table.sort使用分析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/wwlcsdn000/article/details/81711630 Lua–table.sort使用分析 在Lua中我们经常需要对table进行排序,官方也...

那远远的云端
2018/08/15
0
0
JavaScript实现的9大排序算法

插入排序 算法简介 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插...

阿振
2016/05/16
49
0
排序算法总结(python版)

经典排序算法总结与实现 经典排序算法在面试中占有很大的比重,也是基础,为了未雨绸缪,在寒假里整理并用Python实现了七大经典排序算法,包括冒泡排序,插入排序,选择排序,希尔排序,归并...

dby_freedom
2018/08/28
0
0
经典排序算法(Java实现)

以下程序均将数据封装于DataWrap数据包装类中,如下所示: 三、插入排序 1、直接插入排序   每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记...

whc20011
2016/02/02
36
0
白话经典算法系列之七 堆与堆排序

堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。...

长平狐
2012/12/10
144
0

没有更多内容

加载失败,请刷新页面

加载更多

二叉查找树的第 K 个结点

private TreeNode ret;private int cnt = 0;public TreeNode KthNode(TreeNode pRoot, int k) { inOrder(pRoot, k); return ret;}private void inOrder(TreeNode root......

Garphy
49分钟前
4
0
windo8 weblogic

需要的软件包 现在安装jdk 则先进入你电脑自带jdk \bin目录下 然后java -jar 执行你的jar包就可以了 欢迎界面直接点击下一步,跳到更新界面,直接选择跳过 然后选择安装目录(注意:目录不要有...

恩多
56分钟前
6
0
Activiti 批注

Activiti添加批注(comment)信息 在每次提交任务的时候需要描述一些批注信息,例如:请假流程提交的时候要描述信息为什么请假,如果领导驳回可以批注驳回原因等  1、添加批注 // 由于流程...

奔跑的android
今天
4
0
centos7命令行和图形界面的相互切换

最近安装了centos7,发现在命令行和图形界面的相互切换命令上,与centos以往版本有很大不同。 1,centos7默认安装后,跟其他版本一样,启动默认进入图形界面; 2,在图形化桌面,右击鼠标,选...

无名氏的程序员
今天
6
0
快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么

一:快速失败(fail—fast) 在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出Concurrent Modification Exception。 原理:迭代器在...

Bb进阶
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部