package com.softsec.demo;
 
/**
 * Created with IDEA
 *
 * @Author Chensj
 * @Date 2020/5/17 19:04
 * @Description
 * @Version 1.0
 */
public class quickSortDemo {
 
    public static void main(String[] args) {
        // 創(chuàng)建測試數(shù)組
        int[] arr = new int[]{19,97,9,17,1,8};
        System.out.println("排序前：");
        showArray(arr); // 打印數(shù)組
        // 調用快排接口
        quickSort(arr);
        System.out.println("\n" + "排序后：");
        showArray(arr);// 打印數(shù)組
    }
 
    /**
     * 快速排序
     * @param array
     */
    public static void quickSort(int[] array) {
        int len;
        if(array == null
                || (len = array.length) == 0
                || len == 1) {
            return ;
        }
        sort(array, 0, len - 1);
    }
 
    /**
     * 快排核心算法，遞歸實現(xiàn)
     * @param array
     * @param left
     * @param right
     */
    public static void sort(int[] array, int left, int right) {
        if(left > right) {
            return;
        }
        // base中存放基準數(shù)
        int base = array[left];
        int i = left, j = right;
        while(i != j) {
            // 順序很重要，先從右邊開始往左找，直到找到比base值小的數(shù)
            while(array[j] >= base && i < j) {
                j--;
            }
 
            // 再從左往右邊找，直到找到比base值大的數(shù)
            while(array[i] <= base && i < j) {
                i++;
            }
 
            // 上面的循環(huán)結束表示找到了位置或者(i>=j)了，交換兩個數(shù)在數(shù)組中的位置
            if(i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
 
        // 將基準數(shù)放到中間的位置（基準數(shù)歸位）
        array[left] = array[i];
        array[i] = base;
 
        // 遞歸，繼續(xù)向基準的左右兩邊執(zhí)行和上面同樣的操作
        // i的索引處為上面已確定好的基準值的位置，無需再處理
        sort(array, left, i - 1);
        sort(array, i + 1, right);
    }
 
    /**
     * 數(shù)組打印
     * @param num
     */
    private static void showArray(int[] num) {
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }
}

#快速排序 傳入列表、開始位置和結束位置
def quick_sort( li , start , end ):
    # 如果start和end碰頭了，說明要我排的這個子數(shù)列就剩下一個數(shù)了，就不用排序了
    if not start < end :
        return
 
    mid = li[start] #拿出第一個數(shù)當作基準數(shù)mid
    low = start   #low來標記左側從基準數(shù)始找比mid大的數(shù)的位置
    high = end  #high來標記右側end向左找比mid小的數(shù)的位置
 
    # 我們要進行循環(huán)，只要low和high沒有碰頭就一直進行,當low和high相等說明碰頭了
    while low < high :
        #從high開始向左，找到第一個比mid小或者等于mid的數(shù)，標記位置,（如果high的數(shù)比mid大，我們就左移high）
        # 并且我們要確定找到之前，如果low和high碰頭了，也不找了
        while low < high and li[high] > mid :
            high -= 1
        #跳出while后，high所在的下標就是找到的右側比mid小的數(shù)
        #把找到的數(shù)放到左側的空位 low 標記了這個空位
        li[low] = li[high]
        # 從low開始向右，找到第一個比mid大的數(shù)，標記位置,（如果low的數(shù)小于等于mid，我們就右移low）
        # 并且我們要確定找到之前，如果low和high碰頭了，也不找了
        while low < high and li[low] <= mid :
            low += 1
        #跳出while循環(huán)后low所在的下標就是左側比mid大的數(shù)所在位置
        # 我們把找到的數(shù)放在右側空位上，high標記了這個空位
        li[high] = li[low]
        #以上我們完成了一次 從右側找到一個小數(shù)移到左側，從左側找到一個大數(shù)移動到右側
    #當這個while跳出來之后相當于low和high碰頭了，我們把mid所在位置放在這個空位
    li[low] = mid
    #這個時候mid左側看的數(shù)都比mid小，mid右側的數(shù)都比mid大
 
    #然后我們對mid左側所有數(shù)進行上述的排序
    quick_sort( li , start, low-1 )
    #我們mid右側所有數(shù)進行上述排序
    quick_sort( li , low +1 , end )
 
 
#入口函數(shù)
if __name__ == '__main__':
    li = [19,97,9,17,1,8]
    quick_sort(li , 0 , len(li) -1 )
    print(li)