文档章节

学习快速排序算法

rainmanqqst
 rainmanqqst
发布于 2014/09/11 12:24
字数 1083
阅读 125
收藏 1

「深度学习福利」大神带你进阶工程师,立即查看>>>

       快速排序算法是一种分治排序算法。它将数组划分为两个部分,然后分别对两个部分进行排序。通过一次排序,算法将达到如下目的:

        1.对于某个i,a[i]在数组的最终位置上。所谓最终位置,即该数组经过完全排序后各个元素的位置。

        2.a[1],….,a[i-1]中的元素都比a[i]小。

        3.a[i+1],….,a[r]中的元素都比a[i]大。r是最后一个序号。

        快速排序是一个递归划分过程。我们对一个文件进行划分,划分的原则是将一些元素(划分元素)放在它们最终应该在的位置上。比划分元素小的元素都在划分元素的左边,比划分元素大得元素都在划分元素的右边。然后分别对左右两部分分别递归处理。


       选定a[0]作为划分元素。然后首先从左到右寻找比a[0]大的元素,找到后停止。接着从右到左寻找比a[0]小的元素,找到后停止。将这两个元素交换。这样小的元素被排到了a[0]的左边,大的元素被排到了右边。继续刚才的旅途,不断的左右交换。最后划分元素a[i]也做了交换,放到了它的最终位置上。

        对于数组A [7,9,0,1,3,1,5]其过程如下:

第一次排序

       将A[0]=7设为划分元素。

       1.由于是将A[0]设为划分元素,所以右游标先移动。右游标停留在A[6]=5上,因为5小于7。将A[0]A[6]交换.

       2.然后移动左游标,游标停留在A[1]=9上,因为9大于7。将A[1]A[6]交换。

       3.移动右游标,游标停留在A[5]=1上,将A[1]A[5]交换

       4.移动做游标一直移动到A[5]=7,此时左游标和右游标相会,此次排序结束。划分元素7,处于最终位置。

      第一次排序的结果将数组分为两个部分。第一部分是A[0]~A[4],由小于7的元素组成,第二部分为A[6],由大于7的元素组成。接下来的操作是将第一次排序的步骤在这些分组中重新再来一遍。首先是A[0]~A[4]部分。

第二次排序

      将A[0]=5设为划分元素。

      1.同样的从右游标开始。右游标定位到A[4]=3,因为3小于划分元素5。将A[0]A[4]交换。

      2.开始移动左游标,一直到A[4]=5。此时左游标和右游标相会,此次排序结束。划分元素5处于最终位置。

     接下来的排序就是不断的递归了,直到每个元素都处于最终位置为止。

第三次排序

第四次排序

第五次排序

第六次排序

当左边的部分都递归结束后,开始递归右边部分。

第七次排序

结果

 

      在以上的例子中划分元素的位置其实很重要。以最左端作为划分元素,游标就应该从右边先移动;以最右端作为划分元素,游标就应该从左边先开始。这是为了解决顺序数组的问题。一个数组如[1,2,3,4,5],划分元素为最左边,且左游标先移动,那么第一次排序的后果就会是[5,2,3,4,1]。这是一个错误的结果,将使排序永远进行下去。


python代码实现:

#!/usr/bin/env python

def swap(array,i,j):
  temp = array[i]
  array[i]=array[j]
  array[j]=temp
def parition(arry,begin,end):
  temp = array[begin]
  while 1:
    while begin<end:
      if(array[end]<temp):
        swap(array,begin,end)
        break
      else:
        end -=1
    while begin<end:
      if(array[begin]>temp):
        swap(array,begin,end)
        break
      else:
        begin += 1
    if(begin == end):
      break
  print array
  return begin
def quickSort(array,begin,end):
  i=parition(array,begin,end)
  if begin<i-1:
    print '------------right'
    quickSort(array,begin,i-1)
  if i+1<end:
    print '------------left'
    quickSort(array,i+1,end)

if __name__=="__main__":
  array=[7,9,0,1,3,1,5]
  quickSort(array,0,len(array)-1)
  print array

参考文档:

http://my.oschina.net/997155658/blog/311407

《算法:C语言实现》

下一篇: 学习hashMap
rainmanqqst
粉丝 8
博文 66
码字总数 37482
作品 0
浦东
程序员
私信 提问
加载中
请先登录后再评论。
Nutch学习笔记4-Nutch 1.7 的 索引篇 ElasticSearch

上一篇讲解了爬取和分析的流程,很重要的收获就是: 解析过程中,会根据页面的ContentType获得一系列的注册解析器, 依次调用每个解析器,当其中一个解析成功后就返回,否则继续执行下一个解...

强子哥哥
2014/06/26
712
0
高效 Java Web 开发框架--JessMA

JessMA 是功能完备的高性能 Full-Stack Web 应用开发框架,内置可扩展的 MVC Web 基础架构和 DAO 数据库访问组件(内部已提供了 Hibernate、MyBatis 与 JDBC DAO 组件),集成了 Action 拦截...

伤神小怪兽
2012/11/13
9.3K
3
TBB学习:并行循环

http://www.cppprog.com/2009/0325/92.html

Waiting4you
2009/05/12
674
0
SmartGWT学习整理 2、理解核心中的核心DataSource

SmartGWT学习整理 2、理解核心中的核心DataSource DataSource之所以重要,是因为它负责所有的与服务器的数据交互,几乎所有的控件都离不开它。 可以这样说,理解了DataSource就掌握了SmartGW...

st97
2010/11/16
2K
2
NGUI学习基于NGUI的序列帧动画制作

首先导入NGUI包,由于我是在NGUI的基础上进行了简单的扩展。所以还要额外加上几个需要用到的类。我就从新把自己新加的方法放在NGUI中打包。 导入NGUI包以后可以看到有这一个菜单。 创建一个序...

orientalfashion
2013/05/28
5.2K
1

没有更多内容

加载失败,请刷新页面

加载更多

大数据研发学习之路--Hadoop集群搭建

阅读编译文档 准备一个hadoop源码包,我选择的hadoop版本是:hadoop-2.7.7-src.tar.gz,在hadoop-2.7.7的源码 包的根目录下有一个文档叫做BUILDING.txt,这其中说明了编译hadoop所需要的一些...

DSJ-shitou
今天
8
0
OSChina 周五乱弹 —— 特么是别的公司派来的特洛伊木马吧?

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 小小编辑推荐:《我会守在这里》- 毛不易 《我会守在这里》- 毛不易 手机党少年们想听歌,请使劲儿戳(这里) @FalconChen :股市连跪了五天,...

小小编辑
今天
59
2
如何在find中排除目录。命令 - How to exclude a directory in find . command

问题: I'm trying to run a find command for all JavaScript files, but how do I exclude a specific directory? 我正在尝试为所有JavaScript文件运行find命令,但是如何排除特定目录? ......

法国红酒甜
今天
73
0
《Java8实战》笔记(02):通过行为参数传递代码

本文源码 应对不断变化的需求 通过筛选苹果阐述通过行为参数传递代码 初试牛刀:筛选绿苹果 public static List<Apple> filterGreenApples(List<Apple> inventory){List<Apple> result = ......

巨輪
今天
19
0
JeeSite 4 架构特点、安全方面、为什么好、工匠精神、不忘初心

1、底层架构 以 Spring Boot 2 为基础,Maven 多项目依赖,模块分项目,松耦合,方便模块升级、增减模块。 模块化的数据库自动升级程序,当模块升级代码需要更新数据库时,自动执行对应版本 ...

ThinkGem
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部