教你JAVA语言快速排序的原理
来源:才华咖 本文已影响2.79W人
来源:才华咖 本文已影响2.79W人
快速排序(QuickSort )是常用到的效率比较高的一种排序算法,在面试过程中也经常提及。下面就详细讲解一下他的原理、给出一个Java版本的实现。
快速排序思想:
通过对数据元素集合Rn 进行一趟排序划分出独立的两个部分。其中一个部分的关键字比另一部分的关键字小。然后再分别对两个部分的关键字进行一趟排序,直到独立的元素只有一个,此时整个元素集合有序。
快速排序的过程——挖坑填数法(这是一个很形象的名称),对一个元素集合R[ low ... high ] ,首先取一个数(一般是R[low] )做参照 , 以R[low]为基准重新排列所有的元素。
所有比R[low]小的放前面,所有比R[low] 大的放后面,然后以R[low]为分界,对R[low ... high] 划分为两个子集和,再做划分。直到low >= high 。
比如:对R={37, 40, 38, 42, 461, 5, 7, 9, 12}进行一趟快速排序的`过程如下(注:下面描述的内容中元素下表从 0 开始):
原始序列3740384246157912一:high-->low1240384246157912一:low --> high1240384246157940二:high-->low129384246157940二:low --> high1293842461573840三:high --> low129742461573840三:low -->high1297424615423840四:high --> low129754615423840四:low --> high12975461461423840一趟排序结果1297537461423840
开始选取基准 base = 37,初始位置下表 low = 0 , high = 8 , 从high=8,开始如果R[8] < base , 将high位置中的内容写入到R[low]中, 将high位置空出来, low = low +1 ;
从low开始探测,由于low=1 , R[low] > base ,所以将R[low]写入到R[high] , high = high -1 ;
检测到low < high ,所以第一趟快速排序仍需继续:
此时low=1,high=7,因为 R[high] < base ,所以将 R[high] 写入到到R[low]中,low = low + 1;
从low开始探测,low = 2 , R[low] >base ,所以讲R[low]写入到R[high],high=high-1;
继续检测到 low 小于high
此时low=2,high=6,同理R[high] < base ,将R[high] 写入到R[low]中,low=low+1;
从low继续探测,low = 3 , high=6 , R[low] > base , 将R[low]写入到R[high]中,high = high-1;
继续探测到low小于high
此时low=3,high=5,同理R[high] < base,将R[high]写入到R[low]中,low = low +1;
从low继续探测,low = 4,high=5,由于R[low] > base , 将R[low]写入到R[high]中,high = high -1 ;
此时探测到low == high == 4 ;该位置即是base所在的位置,将base写入到该位置中.
然后再对子序列Rs1 = {12,9,7,5} 和 Rs2={461,42,38,40}做一趟快速排序,直到Rsi中只有一个元素,或没有元素。
(注: 在以上表单中可以看到一趟排序中有一些重复的数据(原始数据中没有重复的数据),这是因为没有清除该位置的数据,我们在特定的时间看该内存块的数据依然是它,直到下一次将数据写入该位置位置 —— 在此该位置的数据是一个没有意义脏数据,称之为 “坑”)
快速排序的Java实现:
复制代码 代码如下:
private static boolean isEmpty(int[] n) {
return n == null || th == 0;
}
// ///////////////////////////////////////////////////
/**
* 快速排序算法思想——挖坑填数方法:
*
* @param n 待排序的数组
*/
public static void quickSort(int[] n) {
if (isEmpty(n))
return;
quickSort(n, 0, th - 1);
}
public static void quickSort(int[] n, int l, int h) {
if (isEmpty(n))
return;
if (l < h) {
int pivot = partion(n, l, h);
quickSort(n, l, pivot - 1);
quickSort(n, pivot + 1, h);
}
}
private static int partion(int[] n, int start, int end) {
int tmp = n[start];
while (start < end) {
while (n[end] >= tmp && start < end)
end--;
if (start < end) {
n[start++] = n[end];
}
while (n[start] < tmp && start < end)
start++;
if (start < end) {
n[end--] = n[start];
}
}
n[start] = tmp;
return start;
}
在代码中有这样一个函数:
复制代码 代码如下:
public static void quickSortSwap(int[] n, int l, int h)
该函数可以实现,元素集合中特定的 l 到 h 位置间的数据元素进行排序。
关于快速排序就写到这里了。
sun认证java程序员须知Java日志框架
Java零基础如何学好Java语言
JavaScript与java语言有何不同
Java程序死锁问题原理及解决方案
Javascript和Java语言间的异同比较
java与JavaScript语言有何不同
JAVA语言的常见排序算法
java注册成windows服务程序及简单java定时关机的程序代码
学习Java语言快速有效的方法
谈Java语言与Java技术的介绍
冒泡排序算法原理及JAVA实现代码方法
计算机二级JAVA考试构建JAVA程序2017
JavaScript与java语言的区别
JavaScript与java语言有何区别
浅谈Java语言与Java 技术
教你如何快速找到工作
java语言程序设计实验报告
JAVA语言程序设计强化习题
用Javascript进行简单的Table点击排序
java程序10个面向对象设计原则
Java语言程序设计笔试题附答案
用Java写一个冒泡排序方法
经典Java面试题之Java中Char类型的运算
Java基本语法—java标识符
java算法字符组合排序
快速掌握Java编程的技巧
JAVA简单选择排序算法及实现
Java编程语言程序的认识误区
Java4安卓开发教程之java的变量
java程序员简历
计算机二级Java入门教程:Java类的基本构成
JavaScript快速排序实现实例教程
Java排序算法
常用Java排序算法详解
教你快速升职的方法精品多篇
JAVA常用4种排序方法
Java入门教程:如何使用一个Java
JAVA认证开源技术:关于Java的对象equals方法
java语言程序设计考试大纲
快速学习JavaScript免费教程资源