算法学习记录009_快速排序

一、java版本

package com.study.data.structures.sort;

import java.util.Arrays;

/**
 * 快速排序
 * int[] arr={9, 4, 2, 1, 3, 6, -11};
 * 假设以index=(0+7)/2=3为基准，小于arr[3]=1的放到arr[3]=1的左边，大于arr[3]的放到arr[3]的右边。
 * 第一次调用quickSort方法
 * 0）传入待分组的数组arr,传入left=0和right=arr.length-1
 * 1）假设arr数组最左边有一个箭头l指向left,最右边有一个箭头r指向right,middle=(left+right)/2。。arr[3]=1
 * 2）l,r同时开始移动，l向右移动，r向左移动。
 * 3）在移动过程中如果arr[l]<arr[middle]，则l+=1;arr[r]>arr[middle];则r-=1
 * 4) 进入循环比较，当遇到arr[l]>arr[middle]时，说明此时l所指向的元素需要被挪动到arr[middle]右边；当遇到arr[r]<arr[middle]时，说明此时l所指向的元素需要被挪动到arr[middle]左边；
 * 5）步骤4）得出结果l=0,r=6
 * 6）l与r所指向的元素进行交换，得到结果{-11,4,2,1,3,6,9}。
 * 7）因为l与r还没有相交，所以跳到步骤3）继续执行。
 * 8）步骤4）得出结果此时l=1,r=3;
 * 9）l与r所指向的元素进行交换，得到结果{-11,1,2,4,3,6,9}
 * 10)因为l与r还没有相交，所以跳到步骤3）继续执行。
 * 11）步骤4）得出结果此时l=1,r=1;
 * 12）因为l与r相等，所以l+=1,r-=1。这是为了避免陷入无限递归
 * 12) 此时arr中小于arr[middle]=1的元素已经在arr[middle]=1的左侧了。因为r==left==0的,所以左侧元素不用跳转到步骤1）执行了
 * 13）此时arr中大于arr[middle]=1的元素已经在arr[middle]=1的右侧了。但是l<right的,所以将l到right之间的元素跳转到步骤1）执行传入arr,l=left=2,right=right=6
 * <p>
 * <p>
 * 第三次调用quickSort方法
 * arr={-11,1,2,4,3,6,9}
 * 0）传入待分组的数组arr,传入left=2和right=6
 * 1）假设arr数组最左边有一个箭头l指向left,最右边有一个箭头r指向right,middle=(left+right)/2=4。arr[4]=3
 * 2）l,r同时开始移动，l向右移动，r向左移动。
 * 3）在移动过程中如果arr[l]<arr[middle]，则l+=1;arr[r]>arr[middle];则r-=1
 * 4) 进入循环比较，当遇到arr[l]>arr[middle]时，说明此时l所指向的元素需要被挪动到arr[middle]右边；当遇到arr[r]<arr[middle]时，说明此时l所指向的元素需要被挪动到arr[middle]左边；
 * 5) 步骤4）得出结果，l=3,r=4
 * 6）l与r所指向的元素进行交换，得到结果{-11,1,2,3,4,6,9}。此时l=3,r=4。l与r还没相交，说明元素还没有根据middle分类完毕。
 * 7）将交换之后的元素与middle进行是否相等比较，是为了防止陷入无限递归。如果arr[l]==middle,那么l+=1;如果arr[r]==middle,那么r-=1;
 * 8) 现在l=4,r=4,继续跳转到步骤2依次执行。最后l=4,r=3时，此次挪动结束
 * 9）得到结果{-11,1,2,3,4,6,9}。
 * 10) 因为r大于left了，所以将left到r之间的元素跳转到步骤1）执行传入arr,left=left=2,right=r=3;
 * 11）因为l小于right,所以将l=1到r之间的元素跳转到步骤1）执行传入arr,l=left=4,right=right=6;
 * <p>
 * <p>
 * <p>
 * 第四次调用quickSort方法
 * arr={-11,1,2,3,4,6,9}
 * 0）传入待分组的数组arr,传入left=2和right=3
 * 1）假设arr数组最左边有一个箭头l指向left,最右边有一个箭头r指向right,middle=(left+right)/2=2。arr[2]=2
 * 2）l,r同时开始移动，l向右移动，r向左移动。
 * 3）在移动过程中如果arr[l]<arr[middle]，则l+=1;arr[r]>arr[middle];则r-=1
 * 4) 进入循环比较，当遇到arr[l]>arr[middle]时，说明此时l所指向的元素需要被挪动到arr[middle]右边；当遇到arr[r]<arr[middle]时，说明此时l所指向的元素需要被挪动到arr[middle]左边；
 * 5）步骤4）得出结果，l=2,r=2
 * 6） 此时l与r相交。并且l==r，所以l+=1,r-=1。这是为了避免陷入无限递归。
 * 7）最后l=3,r=2
 * 10) 因为r==left==2，所以不再用跳转到步骤1）;
 * 11）因为l==right==3，所以不再用跳转到步骤1）;
 * 12) 最后的结果是{-11,1,2,3,4,6,9}
 * <p>
 * 第五次调用quickSort方法
 * arr={-11,1,2,3,4,6,9}
 * 0）传入待分组的数组arr,传入left=4和right=6
 * 1）假设arr数组最左边有一个箭头l指向left,最右边有一个箭头r指向right,middle=(left+right)/2=5。arr[5]=6
 * 2）l,r同时开始移动，l向右移动，r向左移动。
 * 3）在移动过程中如果arr[l]<arr[middle]，则l+=1;arr[r]>arr[middle];则r-=1
 * 4) 进入循环比较，当遇到arr[l]>arr[middle]时，说明此时l所指向的元素需要被挪动到arr[middle]右边；当遇到arr[r]<arr[middle]时，说明此时l所指向的元素需要被挪动到arr[middle]左边；
 * 5）步骤4）得出结果，l=5,r=5
 * 6） 此时l与r相交。并且l==r，所以l+=1,r-=1。这是为了避免陷入无限递归。
 * 7）最后l=6,r=4
 * 10) 因为r==left==4，所以不再用跳转到步骤1）;
 * 11）因为l==right==6，所以不再用跳转到步骤1）;
 * 12) 最后的结果是{-11,1,2,3,4,6,9}
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {9, 4, 2, 1, 3, 6, -11};
        int[] arrays = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arrays[i] = (int) (Math.random() * 80000);
        }
        long startTime = System.currentTimeMillis();
        quickSort(arrays, 0, arrays.length - 1);
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
    }

    /**
     * @param arr   需要排序的数组
     * @param left  最左边的位置
     * @param right 最右边的位置
     */
    public static void quickSort(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int middle = (left + right) / 2;
        int middleValue = arr[middle];
        int temp = 0;
        //[-11, 4, 2, 1, 3, 6, 9]
        while (l < r) {
            while (arr[l] < middleValue) {
                l += 1;
            }

            while (arr[r] > middleValue) {
                r -= 1;
            }
            //左右箭头相遇，说明此时数据已经根据middleValue分类完毕
            if (l >= r) {
                break;
            }

            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            if (arr[l] == middleValue) {
                l += 1;
            }
            if (arr[r] == middleValue) {
                r -= 1;
            }
        }
//        System.out.println(Arrays.toString(arr));
        //不加这个判断就是在一直递归调用
        if (l == r) {
            l += 1;
            r -= 1;
        }

        if (r > left) {
            quickSort(arr, left, r);
        }

        if (l < right) {
            quickSort(arr, l, right);
        }
    }
}

二、js版本

let arr = [9, 4, 2, 1, 3, 6, -11]
arr = [];
for (let i = 0; i < 80000; i++) {
    arr[i] = parseInt(Math.random() * 80000)
}


function quickSort(arr, left, right) {
    let l = left;
    let r = right
    let middle = parseInt((left + right) / 2)
    let middleValue = arr[middle]
    let temp = 0
    while (l < r) {
        while (arr[l] < middleValue) {
            l += 1
        }
        while (arr[r] > middleValue) {
            r -= 1
        }

        if (l >= r) {
            break;
        }
        temp = arr[l]
        arr[l] = arr[r]
        arr[r] = temp

        if (arr[l] === middleValue) {
            l += 1
        }
        if (arr[r] === middleValue) {
            r -= 1
        }
    }

    // console.log(arr,l,r);
    if (l === r) {
        l += 1
        r -= 1
    }

    if (r > left) {
        quickSort(arr, left, r)
    }

    if (l < right) {
        quickSort(arr, l, right)
    }
  
}
let start = Date.now()
quickSort(arr, 0, arr.length-1)
let end = Date.now()
console.log('结果：：'+(end-start));