Java 排序方法,快速排序JAVA实现
概念
快速排序属于交换排序，主要步骤是和基准元素进行比较，把比基准元素小的移到一边，比基准元素大的移到另一边。从而将数组分成两部分，然后从这两部分中选择参考元素，重复上述步骤。流程如下：
(推荐视频：java视频教程)
如何解决写爬虫IP受阻的问题？立即使用。
这个想法叫做分而治之。
基准元素
可以随机选择元素。在下面，我将使用第一个元素作为参考元素。
排序过程
排序过程如下：
第一轮
第二轮
第三轮
如上图所示：
如果元素个数为n，时间复杂度为O(n)，因为在排序过程中需要和所有元素进行比较。
排序轮次平均需要logn轮次，所以快速排序的平均时间复杂度为O(nlogn)。
排序的实现方法
实现方法有双边循环法和单边循环法。
双边循环法
选择首选的引用元素(pivot)4，并将左右指针设置为指向数组最左边和最右边的元素，如下所示：
在第一轮指针移动之后，获得以下结构：
然后由左和右指向的元素被交换：
第一个周期结束时，再次切换到右指针，重复上述步骤。
第二次循环后，您可以获得：
第三次循环后，您可以获得：
第四次循环后，您会得到：
当判断左右指针指向同一个元素时，指针停止移动，pivot和pointer元素互换，这样：
宣布这个周期结束，按照支点元素分成两部分。这两部分的数组将按照上述步骤进行操作。
实现代码
公共类DoubleSort {
public static void quick sort(int[]arr，int startIndex，int endIndex) {
//递归结束条件
if (startIndex=endIndex) {
返回；
}
//基准元素位置
int pivotIndex=partition(arr，startIndex，end index)；
//根据基准元素，分成两部分进行递归排序。
快速排序(arr，startIndex，pivotIndex-1)；
快速排序(arr，pivotIndex 1，end index)；
}
public static int partition(int[]arr，int startIndex，int endIndex) {
//以第一个元素为基准元素，或者随机选择。
int pivot=arr[startIndex]；
int left=startIndex
int right=endIndex
而(左！=右){
//控制右指针进行比较并向左移动
while(left right arr[right]=pivot){
右-；
}
//控制左指针进行比较并向右移动
while(left right arr[left]=pivot){
左；
}
//交换左右指针指向的元素
如果(左/右){
int temp=arr[right]；
arr[right]=arr[left]；
arr[left]=temp；
}
}
arr[startIndex]=arr[left]；
arr[left]=pivot；
向左返回；
}
公共静态void main(String[] args) {
int[] arr=new int[]{4，7，6，5，3，2，8，1 }；
快速排序(arr，0，arr . length-1)；
system . out . println(arrays . tostring(arr))；
}
}单边循环法
双边循环法从数组的两边比较交换元素，而单边循环法从数组的一边遍历，一直比较交换，更容易实现。
流程如下：
原始数组如下：
当遍历到元素3时，由于3 ^ 4，mark向右移动。
然后交换元素。
然后继续遍历，按照上面的步骤判断，下面的过程就不写了。
实现代码
公共类SingleSort {
public static void quick sort(int[]arr，int startIndex，int endIndex) {
//递归结束条件
if (startIndex=endIndex) {
返回；
}
//基准元素位置
int pivotIndex=partition(arr，startIndex，end index)；
//根据基准元素，分成两部分进行递归排序。
快速排序(arr，startIndex，pivotIndex-1)；
快速排序(arr，pivotIndex 1，end index)；
}
/**
*分而治之(单边循环法)
* @param数组
* @param startIndex
* @param endIndex
* @返回
*/
public static int partition(int[]arr，int startIndex，int endIndex) {
//以第一个元素为基准元素，或者随机选择。
int pivot=arr[startIndex]；
int mark=startIndex
for(int I=startIndex 1；长度；i ) {
if (pivot arr[i]) {
继续；
}
马克；
int temp=arr[mark]；
arr[mark]=arr[I]；
arr[I]=temp；
}
arr[startIndex]=arr[mark]；
arr[mark]=pivot；
返回标记；
}
公共静态void main(String[] args) {
int[] arr=new int[]{4，7，6，5，3，2，8，1 }；
快速排序(arr，0，arr . length-1)；
system . out . println(arrays . tostring(arr))；
}
}总结
我也是第一次接触算法。在慢慢了解算法的思路和实现过程后，我真的为我过去写的算法感到羞愧。这篇文章也是为了加深我对快排算法的印象。本文如有不足之处，欢迎在下方留言补充。感谢大家的阅读。Thanks()。
参考：《小灰的算法之旅》第四章。
本文来自我们，java教程专栏，欢迎学习！以上是快速掌握java排序算法的细节——快速排序(图文)。请多关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。