Java排序算法（六）快速排序

文章目录

- 快速排序

Java排序算法（一）冒泡排序

 Java排序算法（二）选择排序

 Java排序算法（三）插入排序

 Java排序算法（四）希尔排序

 Java排序算法（五）归并排序

快速排序

算法思想

快速排序主要是通过选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。依次类推，达到总体待排序序列都有序。

算法描述

① 选择基准： 在待排序列中，按照某种方式挑出一个元素，作为“基准”（pivot）。
② 分割操作： 以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比基准小，在基准右边的元素都比基准大。
③ 递归地对两个序列进行快速排序，直到两个序列为空或者只有一个元素。

动画描述

算法详解

将序列 26 53 67 48 57 13 49 32 60 50 进行快速排序。

①选左边界为基准，把基准位置值保存在临时变量temp中。
②先从后往前找比基准位置值（temp）小的值停止，将high位置元素放在low位置处。
③再从前往后找，找到比基准位置值大的值停止，将low 位置元素放在high位置处。
④继续重复步骤②③，直到 high = low，此时low（high）位置就是基准值temp所放的位置。

进行完第一轮排序后，从基准点为切割位置，统计切割位置左右的元素个数，如果切割位置左边的元素个数大于等于2个，那么继续重复步骤①②③④，切割位置右边同理。完成排序后，继续以基准点为切割位置统计切割位置左右的元素个数…直到切割位置左右两边的元素个数都小于等于1个。 如下：

所以结果为：

代码演示

import java.util.Arrays;

public class SortTest06 {
    public static int partition(int[] arr,int low,int high) {
        //安全检测
        if (arr == null || arr.length == 1) {
            return -1;
        }
        int temp = arr[low];//基准值
        while(low < high) {
            //从后向前找比基准位置元素小的元素
            while (low < high && arr[high] > temp) {
                high--;
            }
            if (low == high) {//如果low == high，那么这个位置就是基准元素所放的位置
//                arr[low] = temp;
//                return low;
                break;
            }
            arr[low] = arr[high];

            //从前往后找比基准位置元素大的元素就停止
            while(low < high && arr[low] < temp) {
                low++;
            }
            if (low == high) {//如果low == high，那么这个位置就是基准元素所放的位置
//                arr[low] = temp;
//                return low;
                break;
            }
            arr[high] = arr[low];
        }
        arr[high] = temp;
        return low;
    }
    public static void quick(int[] arr,int low,int high) {
        int index = partition(arr,low,high);//返回基准位置的下标
        if (index == -1) {
            return;
        }
        //如果基准位置下标的左边元素个数 >= 2，则左边继续划分
        if (index - low > 1) {
            quick(arr,low,index - 1);
        }
        //如果基准位置下标的右边元素个数 <= 2，则右边继续划分
        if (high - index > 1) {
            quick(arr,index + 1,high);
        }

    }

    public static void quickSort(int[] arr) {
        //安全检测
        if (arr == null) {
            return;
        }
        quick(arr,0,arr.length - 1);
    }

    public static void main(String[] args) {
        int[] arr = {26,53,67,48,57,13,49,32,60,50};
        System.out.println("排序前:" + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}