快速排序(Quick sort)

实现原理

原理一

选取数组中的某个元素作为所有元素排列大小的分界值

作为分界值的数组元素称之为：枢纽元（pivot）

也可称之为：主元

需要将比枢纽元小的元素放在其左侧，比枢纽元大的元素放在其右侧位置

并不关心其左侧区域或右侧区域内的各元素是否有序

以以下数组为例

5

1

9

3

8

2

7

6

可以让最右侧的6作为枢纽元，左侧比枢纽元小的元素不进行操作，比枢纽元大则标记位置，如果被标记的元素右侧（升序排列）有比枢纽元小的元素，则进行换位（直接和被标记的元素区内的第一个元素换位），保证比枢纽元小的元素都在数组左端，除枢纽元全部换位完成后，枢纽元插入到两种元素分界点位置

<=枢纽元

>枢纽元

待分区

枢纽元

分区结束前枢纽元区的元素不会发生换位

如需升序排列，则需要先达到以下效果：

5

1

3

2

6

9

7

8

根据枢纽元将原数组划分开的过程称为：分区（partition）

接下来对左右两个分区重复以上操作（不包括枢纽元）

5

1

3

2

9

7

8

最终得到有序数组（实际操作中未进行数组拆分）

代码实现

import java.util.Arrays;

import java.util.Random;

public class QuickSort1 {

    public static void quickSort(int[] arr ,int start ,int end){

        //确定枢纽元

        int hub = arr[end];

        //换位临时存储变量

        int tem = 0;

        //随时存储连续的小于枢纽元下标变量，换位辅助

        int x = start - 1;

        //遍历数组

        for (int i = start; i < end; i++) {

            //元素小于枢纽元

            if (arr[i] < hub){

                //arr[i]与arr[x]间出现了大于枢纽元的元素导致x与i差距变大

                if (i - x > 1){

                    tem = arr[i];

                    arr[i] = arr[x + 1];

                    arr[x + 1] = tem;

                    x++;

                    //换位后x变化一位

                }

                else {

                    x = i;

                    //如果没有出现大于枢纽元的元素则x随i变化

                }

            }

        }

        //将枢纽元插入到小于枢纽元那一侧的最后一位

        if (hub < arr[x + 1]){

            tem = arr[x + 1];

            arr[x + 1] = arr[end];

            arr[end] = tem;

        }

        //左侧元素大于一个则递归再次执行

        if (start < x){

            quickSort(arr ,start ,x);

        }

        //右侧元素大于一个则再次递归执行

        if (end > x + 2){

            quickSort(arr ,x + 2 ,end);

        }

    }

    public static void main(String[] args) {

        Random rd = new Random();

        //生成数组

        int[] arr = new int[rd.nextInt(100)];

        for (int i = 0; i < arr.length; i++) {

            arr[i] = rd.nextInt(500);

        }

        System.out.println(Arrays.toString(arr));

        quickSort(arr ,0 ,arr.length - 1);

        System.out.println(Arrays.toString(arr));

    }

}

原理二

8（x）

1

9

3

5

2

7

6（y）

假定x（8）是左侧区域最大下标，y（6）是右侧区域最小下标

默认情况下，x在最左侧，y在枢纽元元素位置，通过循环来移动位置

y>x情况下，y对应的元素大于枢纽元则y自减，y对应的元素小于枢纽元则结束循环

x<y情况下，x对应的元素小于枢纽元则x自加，x对应的元素大于枢纽元则结束循环

如果此时依旧符合x<y，则对此时的xy所对应的元素进行换位

特殊情况

数组中有多个和枢纽元素大小相同的元素，需要跳过 否则会卡死

代码实现

import java.util.Arrays;

import java.util.Random;



public class QuickSort2 {

    public static void quickSort(int[] arr ,int start ,int end){

        if (start >= end){

            return;

        }

        int x = start;

        int y = end;

        Random rd = new Random();

        int hub = arr[rd.nextInt(end - start) + start];

        int tem = 0;



        while (x < y){

            while (x < y && arr[x] < hub){

                x++;

            }

            while (x < y && arr[y] > hub){

                y--;

            }

            if (x < y && arr[x] == arr[y]){

                x++;

            }else {

                tem = arr[x];

                arr[x] = arr[y];

                arr[y] = tem;

            }

        }

        if (x + 1 > start){

            quickSort(arr ,start ,x - 1);

        }

        if (y + 1 < end){

            quickSort(arr ,y + 1 ,end);

        }

    }



    public static void main(String[] args) {

        Random rd = new Random();

        //生成数组

        int[] arr = new int[rd.nextInt(100)];

        for (int i = 0; i < arr.length; i++) {

            arr[i] = rd.nextInt(500);

        }

        System.out.println(Arrays.toString(arr));

        quickSort(arr ,0 ,arr.length - 1);

        System.out.println(Arrays.toString(arr));

    }

}

枢纽元选取

        错误做法

                选取两端的某个元素作为枢纽元，在有序甚至降序的数组中，表现很糟

        安全做法

                随机选取枢纽元

                        几乎不可能每次都产生劣质分区

                        但是生成随机数也有开销，可能导致排序效率下降

        三数中值分割法（Median-of-Three Partitioning）

                使用最左侧最右侧和中间位置的三个元素的中值作为枢纽元

                可以消除有序数组的坏情况