title: 常用排序方式分析与比较
date: 2020-04-05 15:59:00
tags:

• 排序
• 直接插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 直接选择排序
• 堆排序
• 归并排序
  categories:
• 算法

下面选取在实际项目中应用较多的排序方式作一个性能比较，并会对各个方式作一个分析总结。

排序性能比较

测试方案

1. 随机生成10万个整型数字，作为待排序数据。
2. 逐个应用各个排序算法，通过计算开始至结束时间来获得算法执行时间，然后对其进行排序。

测试结果

分析

稳定性

1. 直接插入、冒泡和归并排序算法是稳定的。
2. 直接选择、希尔、快速和堆排序算法是不稳定的。

排序方法的选取

1. 若待排序的一组记录数目n较小（如n<=50）时可采用插入排序或选择排序。
2. 若n较大时应该采用快速排序、堆排序或归并排序。

排序方法对记录存储方式的要求

一般的排序方法都可以在顺序结构（一维数组）上实现。当记录本身信息量较大时，为了避免移动记录耗费大量的时间，可以采用链式存储结构。例如插入排序、归并排序和基数排序（未评测）易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序、堆排序在链表上却难以实现，在这种情况下可以提取关键字建立索引表，然后对索引表进行排序。

排序方式实现

直接插入排序

    /**
     * 插入排序：直接插入排序
     */
    public static void inlineSort(int[] data) {
        int j, tmp;
        for (int i = 1; i < data.length; i++) {
            //若data[i]大于等于有序区中所有的元素则data[i]不动
            if (data[i] < data[i - 1]) {
                //把当前元素复制一份副本
                tmp = data[i];
                //找插入位置
                for (j = i - 1; j > -1 && tmp < data[j]; j--) {
                    //元素后移
                    data[j + 1] = data[j];
                }
                //插入data[i]到正确位置
                data[j + 1] = tmp;
            }
        }
    }

希尔排序

    /**
     * 插入排序：希尔排序
     */
    public static void shellSort(int[] data) {
        //计算最大分组间隔
        int increment = 1;
        while (increment <= data.length / 3) {
            increment = increment * 3 + 1;
        }

        //按照增量序列对顺序表data希尔排序
        for (; increment > 0; increment = (increment - 1) / 3) {
            shellInsert(data, increment);
        }
    }

    /**
     * 希尔排序中的一趟插入排序
     *
     * @param data      待排序数组
     * @param increment 当前增量
     */
    private static void shellInsert(int[] data, int increment) {
        int j, tmp;
        //将data[dk+1...]分别插入有序区
        for (int i = increment; i < data.length; i++) {
            if (data[i] < data[i - increment]) {
                //把当前元素复制一份副本
                tmp = data[i];
                j = i - increment;
                while (j > -1 && tmp < data[j]) {
                    //元素后移，查找插入位置
                    data[j + increment] = data[j];
                    //查找前一记录
                    j = j - increment;
                }
                //插入data[i]到正确位置
                data[j + increment] = tmp;
            }
        }
    }

冒泡排序

    /**
     * 交换排序：冒泡排序
     *
     * @param data 待排序数组
     */
    public static void bubbleSort(int[] data) {
        int tmp;
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data.length - 1; j++) {
                if (data[j] > data[j + 1]) {
                    tmp = data[j + 1];
                    data[j + 1] = data[j];
                    data[j] = tmp;
                }
            }
        }
    }

快速排序

    /**
     * 交换排序：快速排序（划分交换排序），是对冒泡排序的一种改进。
     *
     * @param data 待排序数组
     */
    public static void quickSort(int[] data, int low, int high) {
        if (low < high) {
            //做一次划分排序
            int p = partition(data, low, high);
            //对左区间递归排序
            quickSort(data, low, p - 1);
            //对右区间递归排序
            quickSort(data, p + 1, high);
        }
    }

    /**
     * 一趟划分算法
     *
     * @param data 待排序数组
     * @param i    划分区间
     * @param j    划分区间
     * @return
     */
    private static int partition(int[] data, int i, int j) {
        //用区间的第一个记录为基准
        int tmp = data[i];
        while (i < j) {
            while (i < j && data[j] >= tmp) {
                //从j所指的位置起向前（左）搜索
                j--;
            }
            if (i < j) {
                data[i] = data[j];
                i++;
            }
            while (i < j && data[i] <= tmp) {
                //从i所指的位置起向后（右）搜索
                i++;
            }
            if (i < j) {
                data[j] = data[i];
                j--;
            }
        }
        //基准记录tmp位于最终排序的位置i上
        data[i] = tmp;
        return i;
    }

直接选择排序

    /**
     * 选择排序：直接选择排序
     *
     * @param data 待排序数组
     */
    public static void straightSelectSort(int[] data) {
        int k, tmp;
        //做length-1趟排序
        for (int i = 0; i < data.length - 1; i++) {
            //设k为第i趟排序中关键字最小的记录位置
            k = i;
            //在[i...length-1]选择关键字最小的记录
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[k]) {
                    //若有比data[k]小的记录则记住该位置
                    k = j;
                }
            }
            if (k != i) {
                //与第i个记录交换
                tmp = data[i];
                data[i] = data[k];
                data[k] = tmp;
            }
        }
    }

堆排序

    /**
     * 选择排序：堆排序，是对直接选择排序法的一种改进。
     *
     * @param data 待排序数组
     */
    public static void heapSort(int[] data) {
        int i, tmp;
        for (i = (data.length - 1) / 2; i >= 0; i--) {
            sift(data, i, (data.length - 1));
        }
        for (i = (data.length - 1); i >= 1; i--) {
            tmp = data[0];
            data[0] = data[i];
            data[i] = tmp;
            sift(data, 0, i - 1);
        }
    }

    /**
     * 调整为大根堆
     *
     * @param data 待排序数组
     * @param i    开始
     * @param h    结束
     */
    private static void sift(int[] data, int i, int h) {
        int x = data[i];
        int j = 2 * i;
        while (j <= h) {
            if (j < h && data[j] < data[j + 1]) {
                j++;
            }
            if (x >= data[j]) {
                break;
            }
            data[i] = data[j];
            i = j;
            j = 2 * i;
        }
        data[i] = x;
    }

归并排序

    /**
     * 归并排序
     *
     * @param data 待排序数组
     * @param n    待排序数组长度
     */
    public static void mergeSort(int[] data, int n) {
        if (n < 2) {
            return;
        }
        int mid = n / 2;
        int[] l = new int[mid];
        int[] r = new int[n - mid];

        for (int i = 0; i < mid; i++) {
            l[i] = data[i];
        }
        for (int i = mid; i < n; i++) {
            r[i - mid] = data[i];
        }
        mergeSort(l, mid);
        mergeSort(r, n - mid);

        merge(data, l, r, mid, n - mid);
    }

    /**
     * 合并结果
     *
     * @param a
     * @param l
     * @param r
     * @param left
     * @param right
     */
    private static void merge(int[] a, int[] l, int[] r, int left, int right) {

        int i = 0, j = 0, k = 0;
        while (i < left && j < right) {
            if (l[i] <= r[j]) {
                a[k++] = l[i++];
            } else {
                a[k++] = r[j++];
            }
        }
        while (i < left) {
            a[k++] = l[i++];
        }
        while (j < right) {
            a[k++] = r[j++];
        }
    }