手撕快速排序

• 一. 快速排序动态图
• 二. 快速排序流程
• 三. Java代码实现

一. 快速排序动态图

时间复杂度为 O(NlogN) 不稳定

二. 快速排序流程

主要思想就是分治

1. 确定分界点，去左边界 pivot=arr[left]。
2. 调整区间 使小于等于pivot的值在左边，使大于等于pivot的值在右边。
3. 当i==j两个指针相遇的时候，说明arr数组已经分为左右两个区间了。
4. 再递归处理左右两个区间，重复上面三个步骤
5. 递归出来的条件是区间只剩下一个元素

三. Java代码实现

注释给的非常详细了，自己debug领悟一下

package com.xizi.sort;

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr=new int[]{5,4,3,2,1};
        int n=arr.length;
        quickSort(arr,0,n-1);
        for(int a:arr) {
            System.out.print(a+" ");
        }
        //底层使用双轴快速排序
        Arrays.sort(arr);
    }

    //时间复杂度 O(NlogN)
    //1. 选取pivot
    //2. 划分，根据选取的pivot将数组划分成小于pivot的部分和大于pivot的部分
    //3. 递归求解小于pivot和大于pivot的部分
    public static void quickSort(int[] arr,int left,int right) {
        //边界判断 区间只剩下一个元素时直接返回
        if(left>=right) {
            return;
        }
        //取左边界为分界点
        int pivot=arr[left];
        //下面使用do while循环 i先减1 j加1
        int i=left-1,j=right+1;
        // 调整区间 使小于pivot的值在左边  大于pivot的值在右边
        // 当i==j相遇 arr[]就会被划分为两个区域
        while(i<j) {
            //从前往后找到第一次小于pivot的值
            do {i++;}while(arr[i]<pivot);
            //从后往前找到第一次大于pivot的值
            do {j--;}while(arr[j]>pivot);
            //然后进行交换
            if(i<j) {
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        //递归处理 左右区间
        quickSort(arr,left,j);
        quickSort(arr,j+1,right);

    }

}