快速排序中的partition函数详解

快速排序的精髓就在partition函数的实现。我们构建两个指针,将数组分为三部分,黑色部分全部小于pivot,中间蓝色部分都大于pivot,后面红色部分未知。i指针遍历整个数组,只要它指向的元素小于pivot就交换两个指针指向的元素,然后递增。

// arr[]为数组,start、end分别为数组第一个元素和最后一个元素的索引
// povitIndex为数组中任意选中的数的索引
 int partition(int arr[], int start, int end, int pivotIndex)
 {
     int pivot = arr[pivotIndex];
     swap(arr[pivotIndex], arr[end]);
     int storeIndex = start;

     //这个循环比一般的写法简洁高效
     for(int i = start; i < end; ++i) {
         if(arr[i] < pivot) {
             swap(arr[i], arr[storeIndex]);
             ++storeIndex;
         }
     }
     swap(arr[storeIndex], arr[end]);
     return storeIndex;
}

两次swap是为了将pivot先暂存在最后一个位置,在完成一次partition之后将pivot还原至storeIndex所指的位置。因为它之前的元素都小于它,之后的都大于它。

如果没有这两次swap,那么storeIndex将指向大于等于pivot的元素,并不能保证它之后的元素都大于pivot(能保证之前的都是小于的)。storeIndex位置的元素一旦固定直至程序结束将不会再改变,因此需要使用两次交换暂存pivot元素。

时间: 04-13

快速排序中的partition函数详解的相关文章

delphi中的Format函数详解

首先看它的声明:[[email protected]][@21ki!] function Format(const Format: string; const Args: array of const): string; overload;[[email protected]][@21ki!] 事实上Format方法有两种形式,另外一种是三个参数的,主要区别在于它是线程安全的,[[email protected]][@21ki!]但并不多用,所以这里只对第一个介绍:[[email protect

快速排序中的partition函数的枢纽元选择,代码细节,以及其标准实现

很多笔试面试都喜欢考察快排,叫你手写一个也不是啥事.我很早之前就学了这个,对快速排序的过程是很清楚的.但是最近自己尝试手写,发现之前对算法的细节把握不够精准,很多地方甚至只是大脑中的一个映像,而没有理解其真正的本质意图.于是今天结合了<数据结构>(严蔚敏),和<算法导论>进行一番探究. 首先先给出快速排序的严蔚敏版的实现(实际上这部分的partition也是算法导论里面思考题的实现方式,细节可能不一样): 1 public class QuickSort implements So

linux中fork()函数详解[zz]

转载自:http://www.cnblogs.com/york-hust/archive/2012/11/23/2784534.html 一.fork入门知识 一个进程,包括代码.数据和分配给进程的资源.fork()函数通过系统调用创建一个与原来进程几乎完全相同的进程,也就是两个进程可以做完全相同的事,但如果初始参数或者传入的变量不同,两个进程也可以做不同的事. 一个进程调用fork()函数后,系统先给新的进程分配资源,例如存储数据和代码的空间.然后把原来的进程的所有值都复制到新的新进程中,只有

【转载】3D/2D中的D3DXMatrixPerspectiveFovLH和D3DXMatrixOrthoLH投影函数详解

原文:3D/2D中的D3DXMatrixPerspectiveFovLH和D3DXMatrixOrthoLH投影函数详解 3D中z值会影响屏幕坐标系到世界坐标系之间的转换,2D中Z值不会产生影响(而只是屏幕宽高比会产生影响,z值只对深度剔除产生影响).所以U3D中如果用2D摄像机那么屏幕坐标和世界坐标之间的转换需要用指定的2D摄像机才行,如果用主3D摄像机那么UI转换会产生计算结果异常. 一.D3DXMatrixPerspectiveFovLH函数 作用:Builds a left-handed

Android总结篇系列:Activity中几个主要函数详解

专注Android领域开发. 仰望星空,同时需要脚踏实地. ——好记性不如烂博客 Android总结篇系列:Activity中几个主要函数详解 Activity作为Android系统中四大基本组件之一,包含大量的与其他的各大组件.intent.widget以及系统各项服务等之间的交互的函数.在此,本文主要选取实际项目开发中常用的,但完全理解又需要有一定深入了解的几个函数进行讲解,后续本文会根据需要不断更新. 1. startActivityForResult / onActivityResult

【转】angularjs指令中的compile与link函数详解

这篇文章主要介绍了angularjs指令中的compile与link函数详解,本文同时诉大家complie,pre-link,post-link的用法与区别等内容,需要的朋友可以参考下 通常大家在使用ng中的指令的时候,用的链接函数最多的是link属性,下面这篇文章将告诉大家complie,pre-link,post-link的用法与区别. angularjs里的指令非常神奇,允许你创建非常语义化以及高度重用的组件,可以理解为web components的先驱者. 网上已经有很多介绍怎么使用指令

php学习之道:php中iconv函数 详解

iconv函数库能够完成各种字符集间的转换,是php编程中不可缺少的基础函数库. 用法如下: $string = "亲爱的朋友欢迎访问胡文芳的博客,希望给您带来一点点的帮助!"; iconv("utf8","gbk",$string)//将字符串string  编码由utf8转变成gbk: 扩展如下: echo $str= '你好,欢迎访问胡文芳的博客,该博客记录一个程序员的成长过程!'; echo ' '; echo iconv('GB2312

图像处理中的数学原理详解17——卷积定理及其证明

欢迎关注我的博客专栏"图像处理中的数学原理详解" 全文目录请见 图像处理中的数学原理详解(总纲) http://blog.csdn.net/baimafujinji/article/details/48467225 图像处理中的数学原理详解(已发布的部分链接整理) http://blog.csdn.net/baimafujinji/article/details/48751037 1.4.5   卷积定理及其证明 卷积定理是傅立叶变换满足的一个重要性质.卷积定理指出,函数卷积的傅立叶变

JQuery中$.ajax()方法参数详解

url: 要求为String类型的参数,(默认为当前页地址)发送请求的地址. type: 要求为String类型的参数,请求方式(post或get)默认为get.注意其他http请求方法,例如put和 delete也可以使用,但仅部分浏览器支持. timeout: 要求为Number类型的参数,设置请求超时时间(毫秒).此设置将覆盖$.ajaxSetup()方法的全局设 置. async:要求为Boolean类型的参数,默认设置为true,所有请求均为异步请求. 如果需要发送同步请求,请将此选项