文档章节

QuickSort -- 快速排序

gackey
 gackey
发布于 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;
	}
}

 

本文转载自:

共有 人打赏支持
gackey
粉丝 3
博文 59
码字总数 9252
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

马太效应

马太效应

yizhichao
8分钟前
0
0
69.for while循环 continue break exit

20.10 for循环 20.11/20.12 while循环 20.13 break跳出循环 20.14 continue结束本次循环 20.15 exit退出整个脚本 扩展 select用法 http://www.apelearn.com/bbs/thread-7950-1-1.html 20.10......

王鑫linux
16分钟前
0
0
完整的软件开发流程是怎样的

在it圈混迹了这么久,做过各种各样的工作。但是我确一直不知道一个软件从无到有到底是怎么开发的。于是就产生了强烈的好奇心:一个软件产品的结果为什么是这样?为什么开发的速度不能再快一点...

TreasureWe
23分钟前
0
0
深度学习与图像处理之:人像背景虚化

简单实现思路: 对图像内容进行分割,提取人像 对图像背景进行模糊化处理 将人像和背景重新合成 在这里,使用DeepLabV3模型对图像内容进行分割并提取人像,实现的代码如下: import numpy a...

IOTService
25分钟前
0
0
20180918上课截图

小丑鱼00
32分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部