文档章节

QuickSort -- 快速排序

NinjaFrog
 NinjaFrog
发布于 2017/09/07 23:51
字数 353
阅读 1
收藏 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;
	}
}

 

本文转载自:

共有 人打赏支持
NinjaFrog
粉丝 3
博文 64
码字总数 11574
作品 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语言实现——快速排序的递归和非递归实现

/*快排 - 递归实现 nlogn / / 原理: 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部...

Jo_ZSM
10/11
0
0
快速排序实现之递归与非递归

一、算法思想: 快速排序是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

没有更多内容

加载失败,请刷新页面

加载更多

码云项目100,水一发

简单回顾一下: 早期构想最多的,是希望能将PHP一些类和编码分区做得更细,所以很多尝试。但不得不说,PHP的功能过于单一,是的,也许写C/C++扩展,可以解决问题,那我为什么不用C#或者Golan...

曾建凯
今天
3
0
Spring应用学习——AOP

1. AOP 1. AOP:即面向切面编程,采用横向抽取机制,取代了传统的继承体系的重复代码问题,如下图所示,性能监控、日志记录等代码围绕业务逻辑代码,而这部分代码是一个高度重复的代码,也就...

江左煤郎
今天
4
0
eclipse的版本

Eclipse各版本代号一览表 Eclipse的设计思想是:一切皆插件。Eclipse核心很小,其它所有功能都以插件的形式附加于Eclipse核心之上。 Eclipse基本内核包括:图形API(SWT/Jface),Java开发环...

mdoo
今天
3
0
SpringBoot源码:启动过程分析(一)

本文主要分析 SpringBoot 的启动过程。 SpringBoot的版本为:2.1.0 release,最新版本。 一.时序图 还是老套路,先把分析过程的时序图摆出来:时序图-SpringBoot2.10启动分析 二.源码分析 首...

Jacktanger
今天
6
0
小白带你认识netty(二)之netty服务端启动(上)

上一章 中的标准netty启动代码中,ServerBootstrap到底是如何启动的呢?这一章我们来瞅下。 server.group(bossGroup, workGroup);server.channel(NioServerSocketChannel.class).optio...

天空小小
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部