首先,来看一下,快速排序的实现的动态图:
快速排序介绍:
快速排序,根据教科书说法来看,是冒泡排序的一种改进。
快速排序,由一个待排序的数组(array),以及找准三个变量:
根据中枢值(pivot)来做调整,将数组(array)分为三个部分:
以上就是快速排序要做的第一步,将数组按照:左边数组 、 中枢值 、 右边数组 区分开来。
再根据 递归思想 , 对 左边数组 、 中枢值 、 右边数组 不断递归循环操作,不断拆分出三部分来,最终达到快速排序的效果。
核心逻辑:
快排算法递归调用:
接下来附上完整实现代码:
public class QuickSort { /** * 快速排序调用方法 * * @param ary 待排序数组 * @param left 左值 * @param right 右值 * @return int值 * @author Cansluck */ public static int getSortNum(int[] ary, int left, int right) { // 定义一个中枢值pivot,让其等于数组的左值,枢轴选定后永远不变,最终在中间,前小后大 int pivot = ary[left]; while (left < right) { // 看后面ary[right] > pivot比较,如果右边数组值大于中枢值,说明不需要调整位置,则让右值(right)自减1 while (left < right && ary[right] >= pivot) { right--; // 执行自减操作 } // 如果上面循环不符合条件的,则说明右边数组的一个值,小于中枢值(pivot),则将其替换到左边数组中 ary[left] = ary[right]; // 看后面ary[left] < pivot比较,如果左边数组值小于中枢值,说明不需要调整位置,则让左值(left)自增1 while (left < right && ary[left] <= pivot) { left++; // 执行自增操作 } // 如果上面循环不符合条件,则说明左边数组的一个值,大于中枢值(pivot),则将其替换到右边数组中 ary[right] = ary[left]; } // 最后将中枢值给自增后的左边数组的一个值中 ary[left] = pivot; // 返回左边数组下标 return left; } /** * 快速排序递归方法 * * @author Cansluck * @param ary 待排序数组 * @param left 左值 * @param right 右值 */ public static void quickSort(int[] ary, int left, int right) { // 定义中枢值 int pivot; // 判断 if (left < right) { // 根据方法得到了每次中枢值的位置 pivot = getSortNum(ary, left, right); // 根据中枢值(pivot),来对左边数组进行递归调用快速排序 quickSort(ary, left, pivot - 1); // 根据中枢值(pivot),来对右边数组进行递归调用快速排序 quickSort(ary, pivot + 1, right); } } public static void main(String[] args) { int[] ary = {97, 58, 12, 88, 77, 22, 33, 44, 66, 22}; quickSort(ary, 0, ary.length - 1); for (int i = 0; i < ary.length; i++) { if (i != ary.length - 1) System.out.print(ary[i] + ", "); else System.out.println(ary[i]); } } }
以上就是快速排序的详细介绍及完整实现。有兴趣的小伙伴也自行实现以下吧~
到此这篇关于Java实现快速排序算法的文章就介绍到这了,更多相关Java实现快速排序算法内容请搜索小牛知识库以前的文章或继续浏览下面的相关文章希望大家以后多多支持小牛知识库!
本文向大家介绍java实现快速排序算法,包括了java实现快速排序算法的使用技巧和注意事项,需要的朋友参考一下 1、算法概念。 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。 2、算法思想。 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序
本文向大家介绍Java基于分治法实现的快速排序算法示例,包括了Java基于分治法实现的快速排序算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Java基于分治法实现的快速排序算法。分享给大家供大家参考,具体如下: 运行结果: PS:这里再为大家推荐一款关于排序的演示工具供大家参考: 在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具: http://tools.jb51
本文向大家介绍Python实现快速排序算法及去重的快速排序的简单示例,包括了Python实现快速排序算法及去重的快速排序的简单示例的使用技巧和注意事项,需要的朋友参考一下 快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用。 该方法的基本思想是: 1.先从数列中取出一个数作为基准数。 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
本文向大家介绍Ruby实现的3种快速排序算法,包括了Ruby实现的3种快速排序算法的使用技巧和注意事项,需要的朋友参考一下 刚学Ruby,正巧算法老师鼓励用不熟悉的语言来写算法,我就用Ruby吧~~ 话说Ruby可真是超厉害,好多凭直觉的方法都可以用。。。。。无限膜拜中。。。。 期间我遇到了invalid multibyte char (US-ASCII)的错误,解决办法是在开头加一个#encod
主要内容:快速排序算法的实现提到排序算法,多数人最先想到的就是快速排序算法。快速排序算法是在分治算法基础上设计出来的一种排序算法,和其它排序算法相比,快速排序算法具有效率高、耗费资源少、容易实现等优点。 快速排序算法的实现思路是: 从待排序序列中任选一个元素(假设为 pivot)作为中间元素,将所有比 pivot 小的元素移动到它的左边,所有比 pivot 大的元素移动到它的右边; pivot 左右两边的子序列看作是两个待排
本文向大家介绍Python实现快速排序和插入排序算法及自定义排序的示例,包括了Python实现快速排序和插入排序算法及自定义排序的示例的使用技巧和注意事项,需要的朋友参考一下 一、快速排序 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所
本文向大家介绍Javascript实现快速排序(Quicksort)的算法详解,包括了Javascript实现快速排序(Quicksort)的算法详解的使用技巧和注意事项,需要的朋友参考一下 目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的。 "快速排序"的思想很简单,
快速排序,这是一个经典的算法,本文给出几种python的写法,供参考。 特别是python能用一句话实现快速排序。 思路说明 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 (1) 分治法的基本思想 分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解