首页 / JAVA / quicksort(java版)
quicksort(java版)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了quicksort(java版)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1706字，纯文字阅读大概需要3分钟。
内容图文
相信大家都知道几种排序算法，比如说冒泡排序，选择排序，插入排序等等，这些个算法都不是很难，自己多多理解理解就能掌握了，而今天我们要谈的就是重头戏就是快速排序。
引用大牛的思想来对排序算法解释一下。（文章链接：http://bubkoo.com/2014/01/12/sort-algorithm/quick-sort/#参考文章）
快速排序是图灵奖得主 C. R. A. Hoare 于 1960 年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
利用分治法可将快速排序的分为三步：
- 在数据集之中，选择一个元素作为”基准”（pivot）。
- 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
- 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
下面的简单的介绍一下实现步骤：
上面的图片就是基本实现思路，有点不完全，说的是在快排中基准元素的查找以及定位，基准元素要将比基准元素大的和比基准元素小的要分开，然后一直递归下去，就能实现快排了，本例中基准元素是给定的，而是自己实现的过程中，每次会把第一个元素当成基准元素进行排序。
话不多说，上代码。
1
public
static
int getMiddle(int[] a, int low, int high){
2//比基准元素小的元素的索引 3int storeIndex = 0;
4//默认取第一个元素为基准元素 5int pivot = a[low];
6//先将基准元素移动到数组最后 7int tmp = a[low];
8 a[low] = a[a.length - 1];
9 a[a.length - 1] =tmp;
10//将比基准元素小的放到前面，后面跟上比基准元素大的11for(int i = 0; i < a.length - 1; i++) {
12if(a[i] <= pivot){
13int temp = a[i];
14 a[i] = a[storeIndex];
15 a[storeIndex] = temp;
16 storeIndex++;
17 }
18 }
19//将基准元素放回经过筛选元素后的中间位置20int temp = a[storeIndex];
21 a[storeIndex] = a[a.length - 1];
22 a[a.length - 1] = temp;
23//System.out.println(Arrays.toString(a));24return storeIndex;
25 }
2627publicstaticvoid quickSort(int[] a, int low, int high) {
28if(low < high) {
29int middleIndex = getMiddle(a, low, high);
30 System.out.println(Arrays.toString(a));
31//分成两组分别快排，递归的思想后面的分组就多了32 quickSort(a, low, middleIndex - 1);
33 quickSort(a, middleIndex + 1, high);
34 }
35 }
这两个函数就是实现排序，第一个函数是对基准位置的定位，第二是根据基准位置分为两组分别递归，代码中都包含注释，可以根据其更好地理解代码。
如果有何不妥，可以在评论区里交流哦。
原文：http://www.cnblogs.com/jie9608/p/7351541.html
内容总结
以上是互联网集市为您收集整理的quicksort(java版)全部内容，希望文章能够帮你解决quicksort(java版)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。