八大排序算法之快速排序（Java实现）

本文主要是介绍八大排序算法之快速排序（Java实现），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

参考书籍：大话数据结构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次

这篇关于八大排序算法之快速排序（Java实现）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！