交换排序之快速排序Java

交换排序之快速排序（Java）

博客说明

文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！

快速排序法介绍

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

代码

package cn.guizimo.sort;import java.util.Arrays;public class QuickSort {    public static void main(String[] args) {        int[] arr = {-9, 78, 0, 23, -587, 71};        System.out.println("排序前");        System.out.println(Arrays.toString(arr));        quickSort(arr, 0, arr.length - 1);        System.out.println("排序后");        System.out.println(Arrays.toString(arr));    }    public static void quickSort(int[] arr, int left, int right) {        int l = left;        int r = right;        int temp = 0;        int pivot = arr[(left + right) / 2];        while (l < r) {            while (arr[l] < pivot) {                l += 1;            }            while (arr[r] > pivot) {                r -= 1;            }            if (l >= r) {                break;            }            temp = arr[l];            arr[l] = arr[r];            arr[r] = temp;            if (arr[l] == pivot) {                r -= 1;            }            if (arr[r] == pivot) {                l += 1;            }        }        if (l == r) {            l += 1;            r -= 1;        }        //向左递归        if (left < r) {            quickSort(arr, left, r);        }        //向右递归        if (right > l) {            quickSort(arr, l, right);        }    }}

测试

测试速度

package cn.guizimo.sort;import java.util.Arrays;public class QuickSort {    public static void main(String[] args) {        int max = 80000;        int[] arr = new int[max];        for (int i = 0; i < max; i++) {            arr[i] = (int)(Math.random() * 8000000);        }        long date1 = System.currentTimeMillis();        quickSort(arr, 0, arr.length - 1);        long date2 = System.currentTimeMillis();        System.out.println("快速排序"+max+"数组的时间为："+(date2-date1));    }    public static void quickSort(int[] arr, int left, int right) {        int l = left;        int r = right;        int temp = 0;        int pivot = arr[(left + right) / 2];        while (l < r) {            while (arr[l] < pivot) {                l += 1;            }            while (arr[r] > pivot) {                r -= 1;            }            if (l >= r) {                break;            }            temp = arr[l];            arr[l] = arr[r];            arr[r] = temp;            if (arr[l] == pivot) {                r -= 1;            }            if (arr[r] == pivot) {                l += 1;            }        }        if (l == r) {            l += 1;            r -= 1;        }        //向左递归        if (left < r) {            quickSort(arr, left, r);        }        //向右递归        if (right > l) {            quickSort(arr, l, right);        }    }}

感谢

尚硅谷

万能的网络

以及勤劳的自己