参考书籍:大话数据结构P417
不要急着写代码,先捋思路,可以先参照代码进行理解
快排基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的数字都比另一部分小,则分别对这两部分进行递归排序,以达到有序的目的
以从小到大排序为例,首先选左边第一个为基准值(当然你也可以选其他),然后设置两个指针,从右往左找到比基准值小的数然后与基准值交换,相当于比基准值小的换到左边,再从右往左,找到比基准值大的然后与基准值交换,相当于比基准值大的换到右边
过程如图,一遍排序之后,基准值就会到中间,左边均小于基准值,右边则均大于
{20,10,40 ,50, 70,80,60,90}
不过还没排好序,还需要对左右两边进行递归排序,不断重复此过程
代码实现如下:
package Sort; import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] arr = {50,10,90,70,40,80,60,20}; quickSort(arr, 0, arr.length-1); } public static void quickSort(int[] arr,int left,int right){ int pivot=0;//基准值的索引 if(left<right) { //将数组一分为二 pivot = partition(arr,left,right); //左递归 quickSort(arr, left, pivot-1); //右递归 quickSort(arr, pivot+1, right); } } //排序并返回基准值的索引 public static int partition(int[] arr,int left,int right) { int pivotkey=arr[left];;//基准值 while(left<right) { //找到比基准值小的 while(left<right && arr[right]>=pivotkey) { right--; } //比基准值小的数与基准值交换,即放在基准值的左边 swap(arr,left,right); //找到比基准值大的 while(left<right && arr[left]<=pivotkey) { left++; } //比基准值大的数与基准值交换,即放在基准值的右边 swap(arr,left,right); } //打印排序之后的序列 System.out.println(Arrays.toString(arr)); return left; } //交换 public static void swap(int[] arr,int left,int right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } }
为什么外面已经有left<right判断了,里面还要进行判断?
这是因为内循环改变了left和right的值,不做判断就会在里面的while循环一直循环
为什么以一个为基准值要从右开始找?
如图,
快排之所以快,每次交换是跳着换,而冒泡是相邻交换,首尾交换为例,快排直接1次对换,而冒泡要换n-1次