由快速排序到分治思想

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第一篇《由快速排序到分治思想》,非常赞!希望对大家有帮助,大家会喜欢!

快速排序是一种基于分治思想的排序算法 它主要分为以下几步

1、一个数组按切分元素分成两个数组,一个数组是大于切分元素的,另一个数组是小于切分元素的,

2、然后将这两个部分按上面的思路独立排序。

3、并将有序的子数组归并 得到一个完整的数组。

这中间的关键就在于切分。

代码实现

public class Quick {
       private static void sort(Comparable[] a, int l0, int l1) {
              // TODO Auto-generated method stub
              if(l0 > l1) return;   //做基本的判断
              int l2=partition(a,l0,l1);  //调用方法实现按切分 得到最终a所在位置
              sort(a,l0,l2-1);   //排序比a小的数组
              sort(a,l2+1,l1);   //排序比a大的数组
       }
       private static int partition(Comparable[] a, int l0, int l1) {  //定义切分方法
              int i=l0;   int j=l1+1; //定义左右指针
              Comparable  v=a[0];  //获得切分元素
              while(true){   扫描左右
                     while(less(a[++i],v))  if(i==l1)  break;
//调用 less方法做判断a[i] 和v 直到a[i]大于v时 或者 i 到数组末尾时才停止
                     while(less(v,a[j--])) if(j==l0)  break;
//调用 less方法做判断a[j] 和v 直到a[j]小于v时 或者 i 到数组头时才停止
                     if(i>j)  break;   //做判断  如果作为切分调出循环
                     exch(a,i,j);   调用exch()方法来吧a[i]和a[j] 交换位置
              }
              exch(a,l0,j);   //调用exch()方法 将v放入正确的位置
              return j;
       }
}

快速排序的特性

复杂度 NlgN 空间复杂度 lgN 其运行效率与切分元素值有关 一把在排序之前先随机整个数组。 快速排序也是最快的通用排序算法。

分治思想理念

分治,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题。所以他有三个要点

1、划分步:把输入的问题划分为k个子问题,并尽量使这k个子问题的规模大致相同

2、治理步:调用处理方法来处理问题。

3、组合步:组合步把各个子问题的解组合起来。

从快速排序到分治

在快速排序中将一个数组按切分元素分成两个数组就是在不同的划分步。然后将这两个部分按上面的思路独立排序 这就是治理步。 最后将所有的子数组归并到一个数组 就是组合步。

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2018-01-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python标准库collections中与字典有关的类

Python标准库中提供了很多扩展功能,大幅度提高了开发效率。这里主要介绍OrderedDict类、defaultdict类和Counter类。 (1)Orde...

2696
来自专栏take time, save time

初级程序员面试不靠谱指南(二)

3.read-only的const。如果你突然冒出一句看似很高深的话但又不解释一般都是装逼,就像前面提到过const准确的应该理解为一个read-only的变量...

2737
来自专栏CaiRui

Python之‘数据结构’

简介 数据结构基本上就是--它们是可以处理一些数据的结构。或者说,它们是用来存储一组相关数据的。在Python里面有三种内建的数据结构--列表、元组和字典。 一...

1788
来自专栏小詹同学

Leetcode打卡 | No.014 最长公共前缀

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

792
来自专栏python学习之旅

Python笔记(七):字典、类、属性、对象实例、继承

(一)  简单说明    字典是Python的内置数据结构,将数据与键关联(例如:姓名:张三,姓名是键,张三就是数据)。例如:下面这个就是一个字典 {'姓名':...

3555
来自专栏C语言及其他语言

C语言的数据类型

变量与常量数据 在程序的世界中,可以让计算机按照指令做很多事情,如进行数值计算、图像显示、语音对话、视频播放、天文计算、发送邮件、游戏绘图以及任何我们可以想...

3495
来自专栏java一日一条

Java中有关Null的9件事

对于Java程序员来说,null是令人头痛的东西。时常会受到空指针异常(NPE)的骚扰。连Java的发明者都承认这是他的一项巨大失误。Java为 什么要保留nu...

732
来自专栏陈树义

如何快速学好Shell脚本?

903
来自专栏MyBlog

Effective.Java 读书笔记(8)关于equals方法

重写equals看上去十分简单对吧,但是我觉得很多时候重写equals可能会招致一些问题,这些问题有时可能会特别严重,当然了不重写不就完事了吗?但是这只适用于那...

634
来自专栏java一日一条

Java中有关Null的9件事

对于Java程序员来说,null是令人头痛的东西。时常会受到空指针异常(NPE)的骚扰。连Java的发明者都承认这是他的一项巨大失误。Java为什么要保留nul...

502

扫码关注云+社区