[数据结构与算法]快速排序 Quick sort 作者:哇塞大嘴好帅(我爱大嘴网)

快速排序 Quick sort 作者:哇塞大嘴好帅(我爱大嘴网)

0.what is quick Sort

? 快速排序（Quick sort）是对冒泡排序算法的一种改进

? 1.首先设定一个基准值，通过该分界值将数组分成左右两部分

? 2.循环将大于或等于基准值的数据集中到数组右边，小于基准值的数据集中到数组的左边

? 3.基准值的左边和右边的数据进行重复1，2步骤的操作，也是取一个基准值将大于或等于基准值的数据集中到数组右边，小于基准值的数据集中到数组的左边。

? 4.当上述所完成后，一个排序就完成了

1.思路

? 第一次循环先设置下标为0 的值为基准值，在左指针不等于右指针的情况下左指针找到比基准值小的数据，右指针找到比基准值大的数据，当查找完毕在左指针小于右指针的情况下 两个指针下标的数据进行交换。

? 当左指针等于右指针的时就将基准值与左右指针重合下标的数据进行交换。（找到基准值该放置的位置）

? 之后将基准值左侧的数据假设为一组，右侧为一组，进行递归，操作内容和以上一致。

2.代码实现

package com.dazuizui.insertionSort;

/**
 *     先设置一个基准值，
 *
 *     第一轮循环把所有比基准值小的数全部放到左面，大的放在右面。**
 *
 *        首先设置右指针找到比基准值小的数然后停下来，左指针找到比基准值大的数。并且2个指针下标不相等，然后交换位置。
 *
 *     当左指针右指针位置重合的时候就将重合位置的下标数据和key进行交换,之后将基准值左侧堪称一个数组，进行递归操作，基准值右侧也一样
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {25,99,24,17,30,54,696,78,91,45};
        quick(array,0, array.length-1);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }

    }

    /**
     *
     * @param array
     * @param left   数组开始的位置
     * @param right  数组结束的位置
     */
    public static void quick(int[] array,int left,int right) {
        //执行任务前的合法判断
        if (left == right || left > right || array == null){
            return;
        }

        int temp;
        int key = array[left];
        int l = left;
        int r = right;

        while (l != r){
            //左指针找到比基准值大的下标
            while (array[l] <= key && l < r){
                l++;
            }
            //左指针找到比基准值小的下标
            while (array[r] >= key && l < r){
                r--;
            }


            //左指针右指针的基准值下标的数据进行交换
            if (l < r){
                temp = array[l];
                array[l] = array[r];
                array[r] = temp;
            }
        }

        //基准值与左右指针重合的位置进行交换
        array[left] = array[l];
        array[l]  = key;
        //进行递归 执行内容和以上一致
        quick(array,left,l-1);
        quick(array,l+1,right);
    }
}