重温快速排序(r4笔记第73天)

说起排序,总是会想起大名鼎鼎的快速排序,等自己再次翻开快速排序时,感觉是很陌生的,从这个对比也能看出自己确实是已经忘记了曾经重要的日子。 快速排序使用了分治思想,分而治之。为了达到它传说中较低的时间度,接受了来自大家多年的挑战还依然是名副其实的快速排序。 一个简单的例子就是通过简单的实例来说明。 我们假设一组数字如下: 6,9,4,1,8,7,2,3,5 我们假设以第一个数为参考,即temp为6,两边的数分别为i,j,从这组数的两边来比较这个中间变量,不断的移动下标,从右边开始寻找比temp小的数,从左边开始和寻找比temp大的数。 在这个例子中就是以8为基本的参考,分别从这组数的右边,左边开始移动下标,寻找分别是小于6,大于6的节点。 需要经过这么几轮的比较。 第一轮,我们发现右边第一个节点5<6,就是它了,从左边开始,节点9>6,需要对这个两个节点进行对调。 6,9,4,1,8,7,2,3,5 变为 6,5,4,1,8,7,2,3,9 继续移动下标,从右边开始寻找小于6的,从左边开始寻找大于6的数,结果我们比较一番,发现数3<6,8>6 所以结果如下: 6,5,4,1,8,7,2,3,9 变为: 6,5,4,1,3,7,2,8,9 接下来继续移动下标,发现,2<6,7>6得到的结果如下: 6,5,4,1,3,7,2,8,9 变为: 6,5,4,1,3,2,7,8,9 这个时候从右,从左下标都没法再移动了,再移动就交叉了,这个时候就是需要对这组数进行划分了,划分的基本参考就是6 6,5,4,1,3,2,7,8,9 变为: 2,5,4,1,3,6,7,8,9 这个时候就分成了两组数2,5,4,1,3 和7,8,9两组数,然后根据分治思想需要对着两组数进行进一步的比较。 右边的3个数7,8,9已经是最后结果了,我们来看看左边的数,2,5,4,1,3 设定temp=2,然后下标继续从右,从左开始移动。 2,5,4,1,3 变为: 2,1,4,5,3 然后下标继续移动就移动不了了。继续拆分。 变为1,2, 4,5,3 继续比较,拆分得到最后的结果。 通过程序的实现如下:

 void quicksort(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(left,i-1);//处理左边的

     quicksort(i+1,right);//处理右边的 

 } 

原文发布于微信公众号 - 杨建荣的学习笔记(jianrong-notes)

原文发表时间:2015-03-13

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HTML5学堂

算法之旅 | 快速排序法

HTML5学堂-码匠:前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法,它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广...

35950
来自专栏程序员叨叨叨

7.4 输入\输出修辞符(in\out\inout)

参数传递是指:函数调用实参值初始化函数形参的过程。在 C\C++中,根据形参值的改变是否会导致实参值的改变,参数传递分为“值传递(pass-by-value) ...

11910
来自专栏云霄雨霁

字符串排序----排序算法的选择

25800
来自专栏用户画像

排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

9020
来自专栏趣谈编程

堆排序

面试官:写一个堆排吧 我心想:幸好昨天刚看 ? 堆排是基于堆的一种排序算法,对于堆的了解,请看可以管理时间的二叉堆(如果对堆的插入和删除不清楚,强烈建议先看堆...

24090
来自专栏苦逼的码农

一些常用的算法技巧总结

数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些...

16330
来自专栏趣谈编程

希尔排序

21660
来自专栏于晓飞的专栏

DualPivotQuickSort 双轴快速排序 源码 笔记

这个算法是Arrays.java中给基本类型的数据排序使用的具体实现。它针对每种基本类型都做了实现,实现的方式有稍微的差异,但是思路都是相同的,所以这里只挑了i...

10920
来自专栏程序员叨叨叨

6.1 关系操作符(Comparison Operators)

在上一章中,我们已经介绍了Cg语言的基础数据类型(7种)、内置数据类型,以及数组、结构、接口等类型,本章将在此基础上讨论Cg中的表达式,表达式由操作符(oper...

6420
来自专栏落影的专栏

程序员进阶之算法练习(十六)

前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 没有捷径,但手熟尔; 一步领先,步步领先。 正文 5. L...

40350

扫码关注云+社区

领取腾讯云代金券