随手编程---快速排序(QuickSort)-Java实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了随手编程---快速排序(QuickSort)-Java实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2092字,纯文字阅读大概需要3分钟。
内容图文
背景
快速排序,是在上世纪60年代,由美国人东尼·霍尔提出的一种排序方法。这种排序方式,在当时已经是非常快的一种排序了。因此在命名上,才将之称为“快速排序”。这个算法是二十世纪的七大算法之一,平均情况下时间复杂度为Ο(nlogn),而且在O(nlogn)的情况下,实际的运算速度都要快于其他同时间复杂度的排序方法。
对东尼·霍尔以及快速排序的提出背景感兴趣的同学,可以看看这篇介绍:http://www.nowamagic.net/librarys/veda/detail/2391
排序思想
快速排序的思路想到很困难,但是理解起来却非常容易
他的思路是这样的:
1、先选定队列中,某一个元素为基数Value(一般选择头元素,或尾元素)。
2、将基数Value依次与所有元素比较大小。按照比较结果将元素分为两个队列A、B。一个所有元素比基数Value大,一个所有元素比基数Value小。
3、将A作为新的队列,再次选定基数,然后分成两个更小的队列
4、就这样一直将每一个小的队列无限的拆分成更小的两个队列。
5、一直到一个队列已经拆分成不能拆封为止(也就是一个元素)
6、因为队列之间的顺序都是固定的。将这些队列一次组合起来,整体的排序就算完成了。
(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )
注意这里有两个最核心的步骤,就是
1、选出Value元素,将整体队列划分成两个子队列
2、然后将子队列重新作为一个新的,整体规模比当前要小的,新的队列,进行计算,直到计算起来非常容易为止。
这两个核心步骤造就了快排天生的优势:
1、通过比较大小划分到子队列中的元素,在未来的比较过程中,这个元素的比较范围始终都停留在这个子队列中,不再做多余的比较。这使得早期的比较对后期的比较仍然有很大的影响。而类似于冒泡的排序方法,则前期很多的比较,对后期的作用非常小。这点和kmp算法很像,前期的比较尽量做到最大的利用。
2、将原有规模的队列,拆分成若干个规模小的子队列,这些子队列要(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )解决的问题与原有队列一致,只是规模变小了。这样不断的拆分,形成一种分而治之的思想。这种思想与背包算法也是不谋而合。
对于文字理解起来有困难的同学,可以看下下边这张网上经典的动态图,非常生动
java实现:
import java.util.Arrays; public class QuickSort { public static void main(String args[]) { QuickSort quicksort = new QuickSort(); int[] arrays = newint[] { 1, 12, 2, 13, 3, 14, 4, 15, 5, 16, 17, 17, 177, 18, 8, 8, 19 }; quicksort.quickSort(arrays); System.out.println(Arrays.toString(arrays)); } privatevoid quickSort(int[] arrays) { subQuickSort(arrays, 0, arrays.length - 1); } privatevoid subQuickSort(int[] arrays, int start, int end) { if (start >= end) { return; } int middleIndex = subQuickSortCore(arrays, start, end); subQuickSort(arrays, start, middleIndex - 1); subQuickSort(arrays, middleIndex + 1, end); } privateint subQuickSortCore(int[] arrays, int start, int end) { int middleValue = arrays[start]; while (start < end) { while (arrays[end] >= middleValue && start < end) { end--; } arrays[start] = arrays[end]; while (arrays[start] <= middleValue && start < end) { start++; } arrays[end] = arrays[start]; } arrays[start] = middleValue; return start; } }
原文:https://www.cnblogs.com/ziytong/p/12583782.html
内容总结
以上是互联网集市为您收集整理的随手编程---快速排序(QuickSort)-Java实现全部内容,希望文章能够帮你解决随手编程---快速排序(QuickSort)-Java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。