简单算法 之 快速排序

快速排序

算法介绍

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

排序动态图

算法原理

取出第一个数的下标做为左下标（left），左下标上的数为基准数（base），取出最后一个数为右下标（right），从右right开始判断它上面的数是否有base小，right自减，直到找到比base小的数为止，然后开始从左边算，left自增，直到找到比base大的数，找到之后交换他们两个数的位置，循环此操作，直到left=right，然后将base 与 left（或right任意一个）交换值，这样base就是到了他该到的位置上，base从中间隔开把这个数组分隔成了两段，然后使用将递归继续传入参数执行以上操作。

代码块

public class QuickSort {
          
   
    public static void main(String[] args) {
          
   
        int[] arr = {
          
   5,1,4,2,3,9,6,8,7};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int left,int right){
          
   
        //保存左下标和右下标，以便递归调用
        int start = left;
        int end = right;
        //递归结束条件
        if(left>right){
          
   
            return;
        }
        //保存基准数
        int base = arr[left];
        while (left<right){
          
   
            //找到比基准数小的数的下标
            while (left<right){
          
   
                if(arr[right] < base)break;
                right--;
            }
            //找到比基准数大的数的下标
            while (left<right){
          
   
                if(arr[left] > base)break;
                left++;
            }
            //交换它们的值
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        //交换基准数与left（或right）下标的值
        int temp = arr[start];
        arr[start] = arr[left];
        arr[left] = temp;
        //递归循环
        quickSort(arr, start, left-1);
        quickSort(arr, left+1, end);
    }
}

运行结果