文档章节

QuickSort -- 快速排序

garkey
 garkey
发布于 2017/09/07 23:51
字数 353
阅读 1
收藏 0
点赞 0
评论 0

/*
 * 快速排序:
 * 一趟快速排序的算法是:
 * 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
 * 2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];
 * 3)从j开始向前搜索,即由后开始向前搜索(j=j-1即j--),
 * 找到第一个小于key的值A[j],A[i]与A[j]交换;
 * 4)从i开始向后搜索,即由前开始向后搜索(i=i+1即i++),
 * 找到第一个大于key的A[i],A[i]与A[j]交换;
 * 5)重复第3、4、5步,直到 I=J;
 * (3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。
 * 找到并交换的时候i, j指针位置不变。
 * 另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。)
 */

public class QuickSort {
	public static void sort(int[] data) {
		quickSort(data, 0, data.length - 1);
	}

	private static void quickSort(int[] data, int i, int j) {
		int pivotIndex = (i + j) / 2;
		// swap
		QuickSort.swap(data, pivotIndex, j);

		int k = partition(data, i - 1, j, data[j]);
		QuickSort.swap(data, k, j);
		if ((k - i) > 1)
			quickSort(data, i, k - 1);
		if ((j - k) > 1)
			quickSort(data, k + 1, j);

	}

	/**
	 * @param data
	 * @param i
	 * @param j
	 * @return
	 */
	private static int partition(int[] data, int l, int r, int pivot) {
		do {
			while (data[++l] < pivot);
			while ((r != 0) && data[--r] > pivot);
			QuickSort.swap(data, l, r);
		} while (l < r);
		QuickSort.swap(data, l, r);
		return l;
	}

	public static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}
}

 

本文转载自:

共有 人打赏支持
garkey
粉丝 3
博文 58
码字总数 8942
作品 0
朝阳
程序员
Python天天美味(30) - python数据结构与算法之快速排序

快速排序的原理是将取出第一个数,将整个数组分为两波,一拨都大于这个数,另一波都小于这个数,然后递归用同样的方法处理第一波数字和第二波数字。都说是“快速排序”,效率肯定比其他的一般...

zting科技
2017/01/11
0
0
C++关于快速排序问题,我写的一个快速排序,测试时,当数组长度为1000时,还可以,可是到了1000000时就会出错

//C++关于快速排序问题,我写的一个快速排序,测试时,当数组长度为1000时,还可以,可是到了1000000时 //就会出错,很想知道问题出在哪里?求教?,我在VS2013环境下测试的 #include #include using ...

琴声悠扬TODO
2014/06/05
533
2
快速排序实现之递归与非递归

一、算法思想: 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 设当前待排序的无序区为R[low..high],利用...

妄语生
2016/12/22
28
0
QuickSort快排详细解释

快速排序在最差排序速度,平均排序速度,上都十分优秀,经过简单大数据数组测试,快速排序至少比冒泡排序(这一类复杂度为log(n^2)的排序法)快5倍,废话少说,直接上代码上解释 以下是C++代码,...

franos
2016/03/24
53
0
蓝桥杯 第七届省赛--快速排序

快速排序 排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其左边的元素都不大于它,其右边的元素都不小...

xnh_565175944
03/30
0
0
快速排序(Quicksort)的Javascript实现

日本程序员norahiko,写了一个排序算法的动画演示,非常有趣。 这个周末,我就用它当做教材,好好学习了一下各种排序算法。 排序算法(Sorting algorithm)是计算机科学最古老、最基本的课题...

杨军军
2011/04/06
0
0
快速排序法的python实现

快速排序法是最常用的排序法之一,下面用简单的python程序实现,并做验证。 quicksort.py #!/usr/local/bin/python3.5 -u import sys import random def generateRandomList(n): list = [] f...

李艳青1987
2016/11/17
23
0
快速排序(Quicksort)的Javascript实现

日本程序员norahiko,写了一个排序算法的动画演示,非常有趣。 这个周末,我就用它当做教材,好好学习了一下各种排序算法。 排序算法(Sorting algorithm)是计算机科学最古老、最基本的课题...

阮一峰
2011/04/04
0
0
排序算法之快速排序

快速排序是一种基于分治技术的重要排序算法,顺便提一下什么是分治: 分治法是按照以下方案工作: 1.将一个问题划分为同一类型的若干子问题,子问题规模相同或相近 2.对这些子问题进行求解(...

卫莨
2017/11/10
0
0
’快速排序‘ (quicksort)算法的探讨(1)--- 处理大量重复数据

quicksort在序列的各个元素不相同时效率比较高, nlgn。 但是,如果序列的各个元素几乎都相同时,效率就低了,n^2。 以下是我对randomized quicksort的一个测试 ./quicksort [size] [range] 表...

ChenQi
2012/04/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Git 2.18版本发布:支持Git协议v2,提升性能

Git 2.18版本发布:支持Git协议v2,提升性能Git 2.18版本发布:支持Git协议v2,提升性能 新版本协议的主要驱动力是使 Git 服务端能够对各种 ref(分支与 tag)进行过滤操作。 这就意味着,G...

linux-tao
28分钟前
0
0
python浏览器自动化测试库【2018/7/22-更新】

64位py2.7版本 更新 document_GetResources 枚举页面资源 document_GetresourceText 获取指定url的内容 包括页面图片 下载地址下载地址 密码:upr47x...

开飞色
44分钟前
28
0
关于DCL双重锁失效及解决方案

关于DCL双重锁失效及解决方案 Double Check Lock (DCL)实现单例 DCL 方式实现单例的优点是既能够在需要时才初始化单例,又能够保证线程安全,且单例对象初始化后调用getInstance方法不进行...

DannyCoder
50分钟前
0
0
PowerDesigner 16.5 安装配置

PowerDesigner16.5破解版是一款业内领先且开发人员常用的数据库建模工具,PowerDesigner可以从物理和概念两个层面设计数据库,方便用户制作处清晰直观的数据流程图和结构模型,欢迎有需要的朋...

Gibbons
今天
0
0
mac Homebrew 指令积累

1通用命令 brew install [包名] //安装包 brew list //列举安装的包 brew info [包名] // 显示安装包的详细信息 mysql 相关 #启动mysql 服务 brew service start mysql my...

Kenny100120
今天
0
0
前端Tips: 创建, 发布自己的 Vue UI 组件库

创建, 发布自己的 Vue UI 组件库 前言 在使用 Vue 进行日常开发时, 我们经常会用到一些开源的 UI 库, 如: Element-UI, Vuetify 等. 只需一行命令, 即可方便的将这些库引入我们当前的项目: n...

ssthouse_hust
今天
1
0
大数据教程(2.13):keepalived+nginx(多主多活)高可用集群搭建教程【自动化脚本】

上一章节博主为大家介绍了目前大型互联网项目的keepalived+nginx(主备)高可用系统架构体系,相信大家应该看了博主的文章对keepalived/nginx技术已经有一定的了解,在本节博主将为大家分享k...

em_aaron
今天
5
0
Git 2.18版本发布:支持Git协议v2,提升性能

在最新的官方 Git 客户端正式版2.18中添加了对 Git wire 协议 v2 的支持,并引入了一些性能与 UI 改进的新特性。在 Git 的核心团队成员 Brandon Williams 公开宣布这一消息前几周,Git 协议 ...

六库科技
今天
0
0
Java8新特性之接口

在JDK8以前,我们定义接口类中,方法都是抽象的,并且不能存在静态方法。所有的方法命名规则基本上都是 public [返回类型] [方法名](参数params) throws [异常类型] {}。 JDK8为接口的定义带...

developlee的潇洒人生
今天
0
0
aop + annotation 实现统一日志记录

aop + annotation 实现统一日志记录 在开发中,我们可能需要记录异常日志。由于异常比较分散,每个 service 方法都可能发生异常,如果我们都去做处理,会出现很多重复编码,也不好维护。这种...

长安一梦
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部