> 文档中心 > java常见的排序算法(三)快速排序

java常见的排序算法(三)快速排序

主要思想:
其实就是在一个数组中找到一个轴,将大于这个轴的数放一边,小于这个轴的数放另一边,这样就把数组分成了两部份,然后递归分别将前后两部分再找一个轴,做相同操作,直至排列完全
这里有一个轴的概念,这个轴其实就是数组中任意取一个值,一般取边界值。经典的快速排序中,采用的是单轴快排,而改进版的采用了双轴快排。
在这里插入图片描述

如图,选取数组中边界9为轴,定义两个指针,i,j分别从两端往中间遍历,当i遇到比轴大的就与j比轴小的值进行交换
在这里插入图片描述

这样最终将轴与i+1进行交换,得到一次的循环的结果,然后将轴排好的数组按轴分为做右两个数组递归重复上面的动作

代码如下:

public static void sort(int[] arr, int leftBound, int rightBound){    if (leftBound>=rightBound)return;    int mid = partition(arr, leftBound, rightBound);    sort(arr,leftBound,mid-1);    sort(arr,mid+1,rightBound);}static int partition(int[] arr, int leftBound, int rightBound){    int pivot = arr[rightBound];    int left = leftBound;    int right = rightBound-1;    while (left<=right){ while (left<=right && arr[left] <= pivot)left ++; while (left<=right && arr[right] > pivot)right --; if (left < right)swap(arr,left,right);    }    swap(arr,left,rightBound);    return left;}static void swap(int[] arr,int left,int right){    if (left==right)return;    arr[left] = arr[left] ^ arr[right];    arr[right] = arr[left] ^ arr[right];    arr[left] = arr[left] ^ arr[right];}

以上是传统的单轴排序,在jdk中,Arrays中的快排采用的改进算法,也就是双轴排序,简单的来说就是选取两个轴,将数组分为了三部分来进行排序,当然,实现比较复杂,感兴趣的可以研究研究
java常见的排序算法(三)快速排序

找手机网游