java实现快速排序

java实现快速排序

算法思路

选定一个元素作为基准数（一般用中数），设置左右两个指针，右指针从右往左找比基准数小的数，左指针从左往右找比基准数大的数，两个指针重叠时的位置就是基准数的位置，此时左侧所有元素都小于该元素，右侧所有元素都大于该元素。然后递归的让左侧和右侧分别执行该操作，最终让整个数组变得有序。

代码实现

import java.util.Arrays;
import java.util.Scanner;

public class QuickSort {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一组数字（以空格分开）：");
        String[] data = sc.nextLine().split(" ");
        int[] arr = new int[data.length];
        for(int i = 0; i < data.length; i++){
            arr[i] = Integer.valueOf(data[i]);  // 输入不定长度的数组
        }
        long sTime = System.nanoTime();
        quickSort(arr);
        long eTime = System.nanoTime();
        System.out.println(Arrays.toString(arr));
        System.out.println("耗时：" + (eTime-sTime) + "ns");
        sc.close();
//      int[] testArr = {1, 4, 6, 7, 6, 6, 7, 6, 8, 6};
//      int[] testArr = {7, 3, 1, 5, 4, 6};
//      int[] testArr = {7, 6, 5, 4, 3, 2};
    }

    public static void quickSort(int[] oArr) {
        quickSort(oArr, 0, oArr.length-1);
    }

    private static void quickSort(int[] oArr, int left, int right) {
        int i = left;
        int j = right;
        int mid = (i+j+1)/2;
        int pivot = oArr[mid];

        oArr[mid] = oArr[i];
        while (i < j) {
            while (oArr[j] >= pivot && i < j) {
                j--;
            }
            if (i < j) {
                oArr[i++] = oArr[j];
            }
            while (oArr[i] < pivot && i < j) {
                i++;
            }
            if (i < j) {
                oArr[j--] = oArr[i];
            }
        }
        oArr[i] = pivot;

        if (left < i-1) {
            quickSort(oArr, left, i-1);
        }
        if (i+1 < right) {
            quickSort(oArr, i+1, right);
        }
    }

}

延伸阅读

基础算法实践： https://github.com/AlbertKnag/algs-practice

快速的三向切分：https://www.jianshu.com/p/779bc4b61254

三种快速排序以及快速排序的优化：https://blog.csdn.net/insistgogo/article/details/7785038

小知识

1、for (int x : arr)

int[] testArr = {7, 3, 1, 5, 4, 6};
for (int x : testArr) {
    System.out.print(x + " | ");
}

这种有冒号的for循环叫做foreach循环，这样遍历数组元素更方便

见：https://www.cnblogs.com/yangyi9343/p/4751413.html

2、eclipse批量修改变量名

双击变量名，右键选择Refactor下的Rename...

见：https://jingyan.baidu.com/article/7c6fb4281cde5880642c90a0.html