时间排序_几种常见排序方法的实现及时间对比（JAVA）

清疚 2023-01-06 04:27 123阅读 0赞

![220ac7ce6c81f3b514b4fc12b6ad68a3.png][]

## 首先贴出工具类 ##

ArrayUtil:

import org.apache.commons.lang3.time.StopWatch;
    
    public class ArrayUtil {
         
    
        //交换数组元素
        public static void swap(Comparable[] array, int left, int right) {
         
            Comparable tempValue = array[left];
            array[left] = array[right];
            array[right] = tempValue;
        }
    
        //比较元素
        public static boolean less(Comparable v, Comparable w) {
         
            return v.compareTo(w) < 0;
        }
    
        //打印
        public static void show(Comparable[] array) {
         
            StringBuilder sb = new StringBuilder();
            for (Comparable a : array) {
         
                sb.append(a).append(" ");
            }
            System.out.println("排序后：" + sb.toString());
        }
    
        //判断是否有序
        public static boolean isSort(Comparable[] array) {
         
            for (int i = 1; i < array.length; i++) {
         
                if (less(array[i], array[i - 1])) {
         
                    return false;
                }
    
            }
            return true;
        }
    
        //选择排序方式，计算时间
        public static double runTime(String method, Comparable[] array) throws Exception {
         
            StopWatch watch = new StopWatch();
            watch.start();
            switch (method) {
         
                case "Insertion": {
         
                    InsertSort.sort(array, 0, array.length);
                    break;
                }
                case "Selection": {
         
                    SimpleSelectionSort.sort(array);
                    break;
                }
                case "Shell": {
         
                    ShellSort.sort(array);
                    break;
                }
                case "Quick": {
         
                    QuickSort.optimizeSort(array, 0, array.length - 1);
                    break;
                }
                //快速排序的三向切分
                case "Quick3Way":{
         
                    QuickSort.quick3way(array,0,array.length-1);
                    break;
                }
                case "Heap": {
         
                    HeapSort.sort(array);
                    break;
                }
                case "Bubble": {
         
                    BubbleSort.sort(array);
                    break;
    
                }
                //自顶向下归并
                case "Merge": {
         
                    Comparable[] aux = new Comparable[array.length];
                    Merge.mergeSort(array, aux, 0, array.length - 1);
                    break;
                }
                //自底向上归并
                case "MergeBU": {
         
                    Merge.mergeSortBu(array);
                    break;
                }
                default: {
         
                    throw new Exception("error");
                }
            }
    
            watch.stop();
            if (isSort(array)) {
         
                return watch.getNanoTime();
            }
            throw new RuntimeException(method+"排序不成功");
        }
    
        /**
         * @param method 使用排序方法的名称
         * @param count  生成几组数据
         * @param length 每组数据的长度
         * @return total 平均使用时间 单位ms
         * @throws Exception e
         */
        public static void timeRandomInput(String method, int count, int length) throws Exception {
         
            double total = 0.0;
            Comparable[] array = new Comparable[length];
            for (int i = 0; i < count; i++) {
         
                for (int j = 0; j < length; j++) {
         
                    array[j] = StdRandom.uniform() * 100;
                }
    
                total += runTime(method, array);
            }
            double ms = total/count/100000;
            String formatMs = String.format("%.2f", ms);
            System.out.println(method+" 平均运行时间:"+formatMs);
        }
    
    }

随机数生成类:

import java.util.Random;
    
    /**
     * 此类提供一系列产生随机数的方法，以满足不同用例需要
     *
     * @author crazyMonkey
     */
    
    public final class StdRandom {
         
    
    //随机数对象
    
        private static Random random;
    
    //用于产生随机数的种子
    
        private static long seed;
    
    // 静态初始化区域
    
        static {
         
    
    //产生随机数种子
    
            seed = System.currentTimeMillis();
    
            random = new Random(seed);
    
        }
    
        private StdRandom() {
         
        }
    
    /***********************************************************
     * 产生基本的随机数
     ***********************************************************/
    
        /**
         * 获取此类实例的伪随机种子生成器
         */
    
        public static void setSeed(long s) {
         
    
            seed = s;
    
            random = new Random(seed);
    
        }
    
        /**
         * 获取此类实例提供的伪随机种子生成器
         */
    
        public static long getSeed() {
         
    
            return seed;
    
        }
    
        /**
         * 返回一个随机的范围在[0,1)之间的double类型的数
         */
    
        public static double uniform() {
         
    
            return random.nextDouble();
    
        }
    
        /**
         * 返回一个随机的范围在[0,N)之间的int类型的数
         */
    
        public static int uniform(int N) {
         
    
            return random.nextInt(N);
    
        }
    
        /**
         * 返回一个范围在 [0, 1)的实数
         */
    
        public static double random() {
         
    
            return uniform();
    
        }
    
        /**
         * 返回一个范围在 [a, b)的int类型值
         */
    
        public static int uniform(int a, int b) {
         
    
            return a + uniform(b - a);
    
        }
    
        /**
         * 返回一个范围在 [a, b)的实数
         */
    
        public static double uniform(double a, double b) {
         
    
            return a + uniform() * (b - a);
    
        }
    
    }

## 快速排序 ##

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

代码:

public class QuickSort {
         
    
    
        public static void optimizeSort(Comparable[] array, int left, int right) {
         
            optimizeAdjust(array, left, right);
        }
    
        /**
         * @param array 待排序数组
         * @param left  数组的左界
         * @param right 数组的右界
         */
    
        //三数取中切分
        private static void optimizeAdjust(Comparable[] array, int left, int right) {
         
            if (left < right) {
         
                if (right - left <= 15) {
         
                    InsertSort.sort(array, left, right);
                    return;
                }
                int i, j;
                Comparable key;
                i = left;
                j = right;
                int mid = i + (j - i) / 2;
                if (ArrayUtil.less(array[j], array[mid])) {
         
                    ArrayUtil.swap(array, mid, j);
                }
                if (ArrayUtil.less(array[j], array[i])) {
         
                    ArrayUtil.swap(array, i, j);
                }
                if (ArrayUtil.less(array[i], array[mid])) {
         
                    ArrayUtil.swap(array, mid, i);
                }
                key = array[i];
    
                while (ArrayUtil.less(i, j)) {
         
                    while (ArrayUtil.less(i, j) && !ArrayUtil.less(array[j], key)) {
         
                        // 从右向左找第一个小于x的数
                        j--;
                    }
                    array[i] = array[j];
                    while (i < j && !ArrayUtil.less(key, array[i])) {
         
                        // 从左向右找第一个大于x的数
                        i++;
                    }
                    array[j] = array[i];
                }
                array[i] = key;
                commonAdjust(array, left, i - 1);
                commonAdjust(array, i + 1, right);
            }
        }
    
    
        public static void quick3way(Comparable[] a,int left,int right){
         
            if (right<=left) return;
            int lt =left,  i = left+1,gt = right;
            Comparable key = a[left];
            while (i<=gt){
         
                int temp = a[i].compareTo(key);
                if (temp<0){
         
                    ArrayUtil.swap(a,lt++,i++);
                }else if (temp>0){
         
                    ArrayUtil.swap(a,gt--,i);
                }else {
         
                    i++;
                }
            }
            quick3way(a,left,lt-1);
            quick3way(a,gt+1,right);
        }
    }

## 冒泡排序: ##

public class BubbleSort {
         
    
        public static void sort(Comparable[] array) {
         
    
            int len = array.length;
            int key = len - 1;
            //用来标记，如果未标记，则表示没有发生交换，说明数组有序
            int flag = 0;
            //用来记录发生交换时的位置，这个位置之后，数组有序
            int pos = 0;
            //进行正向遍历后，再进行反向遍历
            int start = 0;
            for (int i = 0; i < len - 1; i++) {
         
                flag = 0;
                for (int j = start; j < key; j++) {
         
                    if (ArrayUtil.less(array[j+1],array[j])) {
         
                        ArrayUtil.swap(array, j, j + 1);
                        flag = 1;
                        pos = j;
                    }
                }
                if (flag == 0) {
         
                    break;
                }
                flag = 0;
                key = pos;
                //反向遍历，把最小值遍历到数组的左端
                for (int k = key;k>start;k--){
         
                    if (ArrayUtil.less(array[k],array[k-1])){
         
                        ArrayUtil.swap(array,k,k-1);
                        flag = 1;
                    }
                }
                start++;
                if (flag == 0) {
         
                    break;
                }
            }
    
    
        }
    }

## 插入排序: ##

public class InsertSort {
         
        /*
         * 插入排序 整体思路还是很简单,稍微优化，减少了数组的交换 复杂度N^2
         */
        public static void sort(Comparable[] array,int start,int end) {
         
            Comparable key;
            for (int i = start+1; i < end; i++) {
         
                key = array[i];
                int j = i;
                for (;j > start && ArrayUtil.less(key, array[j - 1]); j--) {
         
                    array[j] = array[j-1];
                }
                array[j] = key;
            }
        }
    }

## 希尔排序： ##

public class ShellSort {
         
        /*
         * 希尔排序 插入排序的优化算法
         * h相等于步长，计算h的方法3*h+1,（1,4,13,40.....）
         * 数组从0开始，步长为h，将0，0+h,0+2h...算作一个新的数组，对它们进行插入排序
         * 从最大的h开始，每次插入排序后，h/=3,直到h=1，排序完成
         * 运用了和插入排序同样的优化方法，减少了数组的交换
         */
        public static void sort(Comparable[] array){
         
            int len = array.length;
            int h =1;
            while (h<len/3){
         
                h=3*h+1;
            }
            Comparable key;
            while (h>=1){
         
                for (int i = h;i<len;i++){
         
                    int j =i;
                    key = array[i];
                    for (;j>=h && ArrayUtil.less(key,array[j-h]);j-=h){
         
                        array[j] = array[j-h];
                    }
                    array[j] = key;
                }
                h/=3;
            }
        }
    }

## 选择排序: ##

//简单选择排序，选择数组中最小的数，与数组左端交换，交换过后将左端下标+1
    public class SimpleSelectionSort {
         
        public static void sort(Comparable[] array){
         
            int min;
            int len = array.length;
            for(int i = 0;i<len-1;i++){
         
                min = i;
                for (int j=min+1;j<len;j++){
         
                    if (ArrayUtil.less(array[j],array[min])){
         
                        min = j;
                    }
                }
                if (i!=min){
         
                    ArrayUtil.swap(array,i,min);
                }
            }
        }
    }

## 堆排序: ##

public class HeapSort {
         
    
        /*
         *初始化堆,规则：非叶子结点的值必定大于它的叶子结点，堆的顶端为数组的最大值
         *建立堆过程自下而上
         */
        public static void sort(Comparable[] array) {
         
    
            initHeap(array);
            int count = array.length;
            while (count > 1) {
         
                //交换数组的第0位和最后一位，第一位总是为数组最大值，然后将待排序个数减一
                ArrayUtil.swap(array,count-1,0);
                count--;
                buildHeap(array, count, 0);
            }
        }
    
        private static void initHeap(Comparable[] array) {
         
            int arrayLen = array.length;
            for (int index = (arrayLen / 2 - 1); index >= 0; index--) {
         
                buildHeap(array, arrayLen, index);
            }
        }
    
        /**
         *
         * @param array 待排序数组
         * @param count 待排序元素的个数
         * @param index 元素的索引值
         */
        private static void buildHeap(Comparable[] array, int count, int index) {
         
            int maxChildIdx;
            while (index <= count / 2 - 1) {
         
                //判断结点时候为偶数，如果是则只有左叶子结点
                if (count % 2 == 0 && index == count / 2 - 1) {
         
                    maxChildIdx = index * 2 + 1;
                } else {
         
                    int leftChildIdx = index * 2 + 1;
                    int rightChildIdx = index * 2 + 2;
                    //判断左右叶子结点谁大，并赋值
                    maxChildIdx = ArrayUtil.less(array[leftChildIdx],array[rightChildIdx]) ?
                                rightChildIdx: leftChildIdx;
                }
                /*
                 *判断结点是否大于它的父节点，是就交换它们，赋值进入下一次判断
                 * 建堆是自下而上的过程，while循环是自上而下再判断
                 */
                if (ArrayUtil.less(array[index] , array[maxChildIdx])) {
         
                    ArrayUtil.swap(array,index,maxChildIdx);
                    index = maxChildIdx;
                } else {
         
                    break;
                }
            }
        }
    
    }

## 归并排序的两种： ##

public class Merge {
         
       
        public static void mergeSort(Comparable[] dest, Comparable[] src, int l, int r) {
         
            if (l < r) {
         
                int mid = (l + r) / 2;
                mergeSort(dest, src, l, mid);
                mergeSort(dest, src, mid + 1, r);
                merge(dest, src, l, mid, r);
            }
        }
        public static void mergeSortBu(Comparable[] array){
         
            int N = array.length;
            Comparable[] aux = new Comparable[N];
            for (int n = 1; n < N; n = n+n) {
         
                for (int i = 0; i < N-n; i += n+n) {
         
                    int lo = i;
                    int m  = i+n-1;
                    int hi = Math.min(i+n+n-1, N-1);
                    merge(array, aux, lo, m, hi);
                }
            }
        }
        public static void merge(Comparable[] a,Comparable[] aux,int left,int mid,int right){
         
            int i = left;
            int j = mid+1;
            for (int k = left;k<=right;k++){
         
                aux[k] = a[k];
            }
            for (int k = left;k<=right;k++){
         
                if (i>mid){
         
                    a[k] = aux[j++];
                } else if (j>right) {
         
                    a[k] = aux[i++];
                }
                else if (ArrayUtil.less(aux[j],aux[i])){
                           a[k] = aux[j++];
                }else {
         
                    a[k] = aux[i++];
                }
            }
        }
    }

## 测试类： ##

public class Test {
         
        public static void main(String[] args) throws Exception {
         
            int count = 3;
            int Length = 10000;
            ArrayUtil.timeRandomInput(SortMethod.INSERTION, count, Length);
            ArrayUtil.timeRandomInput(SortMethod.SELECTION, count, Length);
            ArrayUtil.timeRandomInput(SortMethod.MERGE_BU, count, Length);
            ArrayUtil.timeRandomInput(SortMethod.MERGE, count, Length);
            ArrayUtil.timeRandomInput(SortMethod.BUBBLE, count, Length);
            ArrayUtil.timeRandomInput(SortMethod.COMMON_QUICK, count, Length);
            ArrayUtil.timeRandomInput(SortMethod.QUICK_3WAY, count, Length);
            ArrayUtil.timeRandomInput(SortMethod.HEAP, count, Length);
        }
    }

运行截图：

![99f8b5c98b4eb2a278aa86052dad04f0.png][]

![6a11c9d44039beda4abd0188a4f786e0.png][]

![043f716044dc8c9a351c5c390314c75d.png][]

[220ac7ce6c81f3b514b4fc12b6ad68a3.png]: /images/20221119/1c7e2848c5544841b7399e6b0ced8d3f.png
[99f8b5c98b4eb2a278aa86052dad04f0.png]: /images/20221119/b20e1746214e481d8154c3c381202c79.png
[6a11c9d44039beda4abd0188a4f786e0.png]: /images/20221119/d8acaa24d93f4c11bf5236c2c1efb12a.png
[043f716044dc8c9a351c5c390314c75d.png]: /images/20221119/12f056caa8374636a6c7b84ac247b884.png