比较排序——三路快速排序

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

快速排序Quicksort计算机科学词汇适用领域Pascalc++等语言是对冒泡排序算法的一种改进。

一、单路排序流程

快速排序算法通过多次比较和交换来实现排序其排序流程如下

(1)首先设定一个分界值通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边小于分界值的数据集中到数组的左边。此时左边部分中各元素都小于分界值而右边部分中各元素都大于或等于分界值。

(3)然后左边和右边的数据可以独立排序。对于左侧的数组数据又可以取一个分界值将该部分数据分成左右两部分同样在左边放置较小值右边放置较大值。右侧的数组数据也可以做类似处理。 [2]

(4)重复上述过程可以看出这是一个递归定义。通过递归将左侧部分排好序后再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后整个数组的排序也就完成了。

二、三路快排改进

双路快排是在单路快排的基础上将重复相等的值相对单路均匀的分到两边

三路快速排序是双路快速排序的进一步改进三路排序算法把排序的数据分为三部分分别为小于 v等于 v大于 vv 为标定值这样三部分的数据中等于 v 的数据在下次递归中不再需要排序小于 v 和大于 v 的数据也不会出现某一个特别多的情况通过此方式三路快速排序算法的性能更优。

三、三路快速排序的时间空间复杂度及稳定性

1、时间复杂度O(nlogn)因为我们这里三路快速排序的过程中向下递归分割数组的过程时间复杂度为O(logn)我们在划分数组部分的时候还要遍历数组时间复杂度为O(n)因此三路快速排序的时间复杂度为:O(nlogn)。

2、空间复杂度S(1)因为我们在三路快速排序时是对原数组进行直接排序并没有其他创建新的数组。

3、稳定性稳定我们在三路快速排序时并不会出现大跨度的交换元素。

四、代码实现

package 排序算法;

import java.util.Arrays;

//三路快排
public class QuickSortThreeWay {
    public static void main(String[] args) {
        int[] arr = {5,4,5,4,3,2,3,2,1,1,1,1,2,3,3,2,1,2,3,4,3,2,4,5,3,5,4,5,3,5,3,2,2,5,6};
        quickSortThreeWay(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSortThreeWay(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        //partition
        swap(arr, L, (int) (Math.random() * (R - L + 1) + L));
        int v = arr[L];
        int lt = L;  //[L+1,lt] < v
        int gt = R + 1;  //[gt,R] > v
        int i = L + 1;  //[lt+1,i) == v
        while (i < gt) {
            if (arr[i] < v) {
                swap(arr, lt + 1, i);
                lt++;
                i++;
            } else if (arr[i] > v) {
                gt--;
                swap(arr, i, gt);
            } else {
                i++;
            }
        }
        swap(arr, L, lt);
        quickSortThreeWay(arr, L, lt - 1);
        quickSortThreeWay(arr, gt, R);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}