高快省的排序算法——快速排序-白红宇

高快省的排序算法——快速排序

阅读量：4160 次

发布时间：2019-05-26

本文共 2750 字，大约阅读时间需要 9 分钟。

高快省的排序算法——快速排序

快速排序是找出一个元素（理论上可以随便找一个）作为基准，然后对数组进行分区操作，使基准左边元素的值都不大于基准值，基准右边的元素值 都不小于基准值。假设我们对以下数组进行排序array[]{23,45,1,6,8,14,65,11}，通常我们把第一个数字作为基准位置，并记录下该位置的数字，x=23,同时 还需要两个指针记录位置两边元素的位置，记为 i，j，此时 i=0，j=array.length-1。下面我们开始进行排序。

x=23
23 45 1 6 8 14 65 11
i = 0
j = 7
第一次排序，23与11进行比较，23比11大，他们两个将位置互换，变成如下数组
11 45 1 6 8 14 65 23
i=1
j=7

因为i要向右移一个位置，所以i=1,i所处的位置的数字是45，45比23要大，所以他俩互换位置，变成如下数组
11 23 1 6 8 14 65 45
i=1
j=6

也就是说当右边的数比基准位置小，就互换位置，同时i+1，并且开始比对左边的位置，如果左边的比基准位置大就互换位置,，同时j-1，并且开始比对右边的位置。
在进行下一步，比对65与23，65比23大，所以不进行互换，只是将j-1，并且继续与右边进行比对，此时数组如下
11 23 1 6 8 14 65 45
i=1
j=5

继续比对23比14大他俩应该互换位置，数组变成如下
11 14 1 6 8 23 65 45
i=2
j=5
又该轮到比对左边的数字了，1比23小，不进行互换，只是将i+1，此时数组如下
11 14 1 6 8 23 65 45
i=3
j=5
再与左边的数字进行比较，6比23小，不进行互换，只是将i+1，此时数组如下
11 14 1 6 8 23 65 45
i=4
j=5
此时再与左边的数字进行比较，8比23小，不进行互换，只是将i+1，此时数组如下
11 14 1 6 8 23 65 45
i=5
j=5
此时i=j，中止比较，我们会发现在23左边的数字都比23小，在23右边的数字都比23要大，我们在按照上面的步骤分别对23左边的数组和23右边的数组进行处理，就能够完成任务，把一个大问题变成两个小问题，这也是分治法（ Divide and Conquer）的精髓。
我们继续上面步骤，将数组排列完
11 14 1 6 8
i=0
j=4

8 14 1 6 11
i=1
j=4

8 11 1 6 14
i=1
j=3

8 6 1 11 14
i=2
j=3

再次将11左边的数字进行快速排序
8 6 1
i=0
j=2

1 6 8
i=1
j=2

1 6 8
i=2
j=2
11左边的数组已经排完，排11右边的数组
14
因为11右边就一个数，所以不用进行排序，下面对23右边的数组进行排序
65 45
i=0
j=1

45 65
i=1
j=1
23右边的数组也排列完，快速排序完成

下面是代码实现

public class Demo {    public static void main(String[] args) {        int[] array = new int[]{
  23,45,1,6,8,14,65,11};        quickSort(array,array.length);        for (int i = 0; i < array.length; i++) {            System.out.print(array[i]+",");//打印数组        }    }    public static void quickSort(int[] array, int length) {        if (array == null || length < 1) {            System.out.println("sort Error");            return;//当数组为空 或者 长度小于1的时候打印错误并返回        }        sortMethod(array,0,length-1);    }    private static void sortMethod(int[] array, int start, int end) {        if (start>=end) {            return;//如果开始位置大于等于最后的位置，跳出循环        }        int i = start;        int j = end;        int value = array[i];        boolean status = true;        while (i != j) {            if (status) {
  //当右边的数据换了位置时再开始比对左边位置的数据                if (array[j] < value) {                    swap(array, i, j);                    status = false;                } else {                    j--;                }            } else {                if (array[i] > value) {                    swap(array, i, j);                    status = true;                } else {                    i++;                }            }        }        sortMethod(array, start, j - 1);//对右边数组继续进行排序        sortMethod(array,i+1,end);//对左边数组继续进行排序    }    public static void swap(int[] array, int i, int y) {        int temp = array[i];        array[i] = array[y];        array[y] = temp;    }}

运行结果：