QuickSort

坚持学习，坚持写博客，努力向大佬前进！ QAQ ………
之前面试被算法虐惨了，所以决定开一个算法的分类，记录一些日常算法

快速排序

我们先通过图片看下快排到底是怎样实现的

然后就是上代码：

package com.util;
 
/**
 * @author zhouxh
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] num = {64,45,78,64,52,11,3,55,99,12,18};
        System.out.println(arrayToString(num,"排序前"));
        QuickSort(num,0,num.length-1);
        System.out.println(arrayToString(num,"排序后"));
    }
    /**
     * 快速排序
     * @param num    排序的数组
     * @param left    数组的前针
     * @param right 数组后针
     */
    private static void QuickSort(int[] num, int left, int right) {
        // 排除 死循环的可能
        if(left>right){
            return;
        }
        int i = left;
        int j = right;
        int key = num[left];
        while (i<j){
            // 倒序 找一个比 key 小的
            while (num[j]>=key&&i<j){
                j--;
            }
            // 正序 找一个比 key 大的
            while (num[i]<=key&&i<j){
                i++;
            }
            // 如果大的在小的右边，交换位子
            if(i<j){
                int temp = num[i];
                num[i] = num[j];
                num[j] = temp;
            }
        }
        // 以上循环替换直到所以比key值小的 都在右边 大的都在右边时 结束
        // 将之后一个小的 和 key互换，以达到 key左边都比key小，右边都比key大
        num[left] = num[i];
        num[i] = key;
        // 此时根据 key 分成的左右两边分别排序
        QuickSort(num,left,i-1);
        QuickSort(num,i+1,right);
    }
    /**
     * 将一个int类型数组转化为字符串
     * @param arr
     * @param flag
     * @return
     */
    private static String arrayToString(int[] arr,String flag) {
        String str = "数组为("+flag+")：";
        for(int a : arr) {
            str += a + "\t";
        }
        return str;
    }
}