快速排序 2022.01.03

快速排序 2022.01.03

快速排序的基本思想：先确定一个中轴值，然后分别从左右两端开始往中间遍历，在遍历的过程中将比中轴值大的放在右边，比中轴值小的放在左边；然后在利用递归的思想将左右两边分别进行快速排序即重复上面 *** 作。

快速排序执行结果：

 快速排序代码：

package DataStructures.sort;

import java.util.Arrays;


public class QuickSort {

    static int count = 0;

    public static void main(String[] args) {
        int[] nums = {-9,78,0,23,-567,70};
        System.out.println("快速排序前："+ Arrays.toString(nums));
        quickSort(nums,0,nums.length-1);
//        System.out.println("快速排序后："+ Arrays.toString(nums));
    }

    //快速排序
    public static void quickSort(int[] nums, int left, int right){
        int l = left;
        int r = right;
        int pivot = nums[(left+right)/2];

        int temp = 0;
        while( l < r ){
            //在左边找比中轴值大的值
            while (nums[l] < pivot ){
                l++;
            }
            //在右边找比中轴值小的值
            while ( nums[r] > pivot ){
                r--;
            }

            if( l >= r ){
                break;
            }

            temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;

            count++;
            System.out.println("第"+count+"次快排:"+Arrays.toString(nums));

            if( nums[r] == pivot ){
                r--;
            }

            if( nums[l] == pivot ){
                l++;
            }
        }

        //防止栈溢出
        if( l == r ){
            l++;
            r--;
        }

        //左递归
        if( left < r ){
            quickSort(nums,left,r);
        }
        //右递归
        if( right > l ){
            quickSort(nums,l,right);
        }
    }
}