十大排序之快速排序

javaQuicksort_2">java实现快速排序（Quicksort）

十大排序之归并排序

扫码关注公众号，更多资料尽在掌握。

1.简介
快速排序，快速排序（Quicksort）是对冒泡排序的一种改进。它采用了分治法的策略，数据量越大，越能体现快排的速度。快速排序的平均时间复杂度是O(nlogn)，空间复杂度是O(log2n)，是不稳定排序。
快速排序实现的思想是：指通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。

总结：
第一步、在数列中取出一个数作为基准数（一般是最左边的数）。
第二步、定义两个指针：一个从右往左移动，找到比基准数小的停下；另一个指针从左往右移动，找到比基准数大的停下，交换两个指针对应的数。
第三步、交换完成，继续检索，重复第二步。
第四步、当两个指针相遇，停止检索，将基准数和相遇位置元素交换。此时，第一轮排序结束。这时候的数组特点：
基准数左边都小于基准数，基准数右边都大于基准数，
第五步、采用分治策略，按照上述步骤继续排列基准数左边，右边同理。

看文字理解可能有点云里雾里，接下来我们用图来解释下这个过程。

2.图解步骤

1.假设这有个待排序数组。我们定义基准数为5，定义两个指针 i、j
在这里插入图片描述

2 j指针先从右往左移动，找到比基准数小的，停下，然后i指针向右移动，找到比基准数大的，停下，

在这里插入图片描述

3.找到了，停下。

在这里插入图片描述

4.交换两个元素。
在这里插入图片描述

5.重复上述步骤，直到两个指针相遇。
在这里插入图片描述

6.到这里，基准数归位了。你就会发现，基准数左边的都小于基准数，基准数右边的都大于基准数。

7.现在使用分治法策略，先排左边，再排右边，重复上面的步骤。

在这里插入图片描述

左边完成：
在这里插入图片描述

同理。右边也是。

在这里插入图片描述

最终，完成排序。
在这里插入图片描述

3.代码实现。

接下来，我们用java语言来实现一下这个过程吧。

java">package com.znzz.quicksort;
//快速排序

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {1,3,65,7,4,6,2};

        System.out.println(Arrays.toString(arr));
       long start =  System.currentTimeMillis(); //获取系统当前时间（ms）
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        System.out.println(System.currentTimeMillis() - start); //计算程序所用时间（ms）
    }

    // 定义方法，用来快速排序
    public static  void quickSort(int[] arr, int left, int right){
         //判断，如果左边大于右边，不合法，直接return
        if (left > right){
            return;
        }
        //定义变量保存基准数
        int base = arr[left];
        //定义变量i，指向最左边
         int i = left;
        //定义变量j，指向最右边
        int j = right;

        //开始检索
        while (i != j) {
            //由j从右往左检索。检索到比基准数小的就停下，检索到比基准数小大的就据徐检索
            while (arr[j] >= base && i < j) {
                j--;   //表示从右往左移动
            }
            //i从左往右检索
            while (arr[i] <= base && i < j) {
                i++;   //表示从左往右移动
            }
            //到这，表示i、j都停下了，代表都找到了符合的元素，开始交换对应元素。
            swap(arr, i, j);

        }
               //到这，说明i = j，表示相遇了
               //停止检索，把基准数和相遇位置的数交换。
               arr[left] = arr[i];
               arr[i] = base;
              //基准数在这就归位了，这样，左边的数都比它小，右边的数都比他大
              //现在开始排左边。
            quickSort(arr, left, i-1);
        //现在开始排右边。
        quickSort(arr, i+1, right);
    }

    public  static  void swap(int [] arr, int i, int j){
        int temp = arr[i];
           arr[i] = arr[j];
            arr[j] = temp;

   }
}