数据结构和算法之手动实现快速排序(稳定排序和非稳定排序)

文一西路代码狗 2020-07-25

1285

1、算法介绍

2、算法示例

3、代码实现

4、随机主元快速排序

5、随机主元快速排序代码实现

一、算法介绍

快速排序（Quicksort）是对冒泡排序算法的一种改进。快速排序由C. A. R. Hoare在1960年提出，也是基于分治思想的一种排序算法，相对于上节归并排序来讲，快速排序简化了治的操作，重点在于分。快速排序的基本思想是：选取首元素或者尾元素作为主元，通过一趟排序将要排序的数据分割成独立的两部分，其中左边一部分的所有数据都比主元小，另外右边一部分的所有数据都比主元大，然后再按此方法对这左右两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序。

二、算法示例

如设有数列{2, 6, 7, 1, 3, 5, 6, 4}

算法过程如下所示：

这样，经过层层递归之后，所有的元素已经是局部有序，然后直接把他们拼接起来就行了。

三、代码实现

     /**
     * @Date: 2020-03-24
     * @Description: 快速排序算法(选取一个数为基数 ， 比他大的总是在右边 ， 小的总是在左边)
     * @Description: 时间复杂度好的情况下为O(n), 坏的情况下为O(n ^ 2)
     */
    public static void quickSort(int a[], int low, int high) {
        if (low >= high) {
            return;
        }
        int p = partition(a, low, high);
        quickSort(a, low, p - 1);
        quickSort(a, p + 1, high);
    }


    public static int partition(int[] a, int low, int high) {
        int i = low;
        int j = high;
        int base = a[low];
        while (i != j) {
            while (a[j] >= base && i < j) {
                j--;
            }
            while (a[i] <= base && i < j) {
                i++;
            }
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        //将a[low] a[i]的值进行交换，因为a[i]始终是比base小的数的最右边的一个数
        a[low] = a[i];
        a[i] = base;
        return i;
    }

四、随机主元快速排序

上面介绍的快速排序算法实际上是一种非稳定的排序算法，在某些条件下时间复杂度可能为O(nlogn)，在某些条件下也可能为O(n^2),所以可以认为他的时间复杂度为O(n^2)，当然这是一种不太能接受的时间复杂度，那么必须对其进行优化重构，下面先来看看在什么条件下会出现O(nlogn)，又在什么条件下出现O(n^2)。

时间复杂度出现O(nlogn)是这个数组不具有特定的规则，一般的数组，那么出现O(n^2)可能就是下面这种情况：

数列{2, 3, 4, 5, 6, 7, 1}

对于这样的数列，如果继续按照之前的固定以尾元素为主元的方式进行分解的话，会发现每次划分都是一种极限划分，也就是主元左边或者右边一定有一边是没有元素的，比自己大的或者比自己小的只存在自己的一边。

如下图所示：

可以看出基于这样的序列进行快速排序如果我们恶意构造一个具有上图这样特点的序列，时间复杂度就会升至O(n^2)，为此，对于主元的选取来说，不能固定以任意一个元素为主元，应该采取随机获取一个主元的方式，这样，主元位置是随机的，就无法构造出一个序列，使排序的时候所有的元素要么全部在主元左边要么全部在主元右边。

五、随机主元快速排序代码实现

和固定主元实现不同的是，这里使用random生成了元素范围内的一个随机数，然后和尾元素进行交换，这样就意味着主元是随机的。

    /**
     * @Date: 2020-03-24
     * @Description: 快速排序算法(随机选取一个数为基数 ， 比他大的总是在右边 ， 小的总是在左边)
     * @Description: 时间复杂度为O(nlogn)
     */
    public static void quickSortRandom(int a[], int low, int high) {
        if (low >= high) {
            return;
        }
        int p = randomPartition(a, low, high);
        quickSortRandom(a, low, p - 1);
        quickSortRandom(a, p + 1, high);
    }


    public static int randomPartition(int[] a, int left, int right) {
        int r = new Random().nextInt(right - left + 1) + left; //生成一个随机数，即是主元所在位置
        swap(a, left, r); //将主元与序列最右边元素互换位置，这样就变成了之前快排的形式。
        return partitionRandom(a, left, right); //直接调用之前的代码
    }


    public static int partitionRandom(int[] a, int low, int high) {
        int i = low;
        int j = high;
        int base = a[low];
        while (i != j) {
            while (a[j] >= base && i < j) {
                j--;
            }
            while (a[i] <= base && i < j) {
                i++;
            }
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        //将a[low] a[i]的值进行交换，因为a[i]始终是比base小的数的最右边的一个数
        a[low] = a[i];
        a[i] = base;
        return i;
    }


    //交换数组a中的a[i]和a[j]
    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

至此，以这种随机快排的方式时间复杂度就为O(nlogn)，和归并排序时间复杂度是一样的。虽然这两种实现方式时间复杂度一样，但是在实际应用中快速排序使用的相对较多，在Javajdk或者在其他计算机语言中sort排序就是使用的快速排序，因为，快速排序比归并排序常数阶要小。

数据库

文章转载自文一西路代码狗，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数据结构和算法 之 手动实现快速排序(稳定排序和非稳定排序)

评论

数据结构和算法之手动实现快速排序(稳定排序和非稳定排序)