各类排序

首先认识一下十大排序算法

image-20210515200024075

  • 冒泡，选择，插入，归并，快排，希尔，堆排序属于比较排序

准备工作

在开始介绍排序算法之前，首先先设计一下接口，方便进行性能测试和验证正确性。

这里使用Java中的抽象类来统一接口，留出抽象sort方法给子类实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 protected Integer[] array;
    private int cmpCount = 0;


    private int swapCount = 0;
    private long time;
    private DecimalFormat fmt = new DecimalFormat("#.00");

    protected abstract void sort();

    public void sort(Integer[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        this.array = array;
        time = System.currentTimeMillis();
        sort();
        time = System.currentTimeMillis() - time;
    }


    /**
     * 传入两个索引
     * 相等返回0
     * a>b返回正数
     * a<b返回负数
     *
     * @param a
     * @param b
     * @return
     */
    protected int cmp(int a, int b) {
        cmpCount++;
        return array[a] - array[b];
    }

    protected int cmpElement(Integer a, Integer b) {
        cmpCount++;
        return a.compareTo(b);
    }

    protected void swap(int a, int b) {
        swapCount++;
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    private String numberString(int number) {
        if (number < 10000) {
            return "" + number;
        }

        if (number < 100000000) {
            return fmt.format(number / 10000.0) + "万";
        }
        return fmt.format(number / 100000000.0) + "亿";
    }

    @Override
    public String toString() {
        String timeStr = "耗时：" + (time / 1000.0) + "s(" + time + "ms)";
        String compareCountStr = "比较：" + numberString(cmpCount);
        String swapCountStr = "交换：" + numberString(swapCount);
//        String stableStr = "稳定性：" + isStable();
        return "【" + getClass().getSimpleName() + "】\n"
//                + stableStr + " \t"
                + timeStr + " \t"
                + compareCountStr + "\t "
                + swapCountStr + "\n"
                + "------------------------------------------------------------------";

    }

    @Override
    public int compareTo(Sort o) {
        int result = (int) (this.time - o.time);
        if (result != 0) {
            return result;
        }
        result = this.cmpCount - o.cmpCount;
        if (result != 0) {
            return result;
        }
        return this.swapCount - o.swapCount;

    }

基于比较的排序

让我们从最简单的冒泡排序开始

冒泡排序

  1. 遍历相邻两位，根据比较规则决定是否交换
  2. 每次遍历都会完成一位排序，因此下次开始时可以后移一位进行比较
  3. 遍历数组长度-1次之后排序完成
  4. 显然如果一次遍历没有交换代表排序已经完成，这时可以提前结束循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class BubbleSort extends Sort{
    @Override
    protected void sort() {
        for (int i = 0; i < array.length - 1; i++) {

            boolean flag = true;
            for (int j = i; j < array.length; j++) {

                if (cmp(i,j)>0) {
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }
}
最好 最坏 平均 额外空间复杂度 In-place 稳定性
O(n) O(n^2) O(n^2) O(1) √ √

排序算法的稳定性

这里引入排序算法的稳定性这个概念

  • 如果相等的2个元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法

    排序前： 5 , 1 , 3 𝑎 , 4 , 7 , 3𝑏

    稳定的排序： 1 , 3 𝑎 , 3 𝑏 , 4 , 5 , 7

    不稳定的排序：1 , 3 𝑏 , 3 𝑎 , 4, 5 , 7

  • 对自定义对象进行排序时，稳定性会影响最终的排序效果

  • 冒泡排序属于稳定的排序算法

稍有不慎，稳定的排序算法也能被写成不稳定的排序算法，比如下面的冒泡排序代码是不稳定的

1
2
3
4
5
6
7
for(int end = array.length-1;end > 0; end--){
  for(int begin = 1; begin<end; brgin++){
    if(cmp(begin,begin-1)>=0){
      swap(begin,begin-1);
    }
  }
}

原地算法

何为原地算法？

  • 不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入
  • 空间复杂度为 𝑂 ( 1 ) 可以认为是原地算法
  • 非原地算法，称为 Not-in-place 或者 Out-of-place
  • 冒泡排序属于 In-place

选择排序

  1. 外层循环收缩区间
  2. 内存循环遍历当前区间
  3. 每次遍历选择当前区间最大元素与最后元素换位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class SelectionSort extends Sort {

    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            int maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (cmp(maxIndex, begin) < 0) {
                    maxIndex = begin;
                }
            }
            swap(maxIndex, end);

        }
    }
}
最好 最坏 平均 额外空间复杂度 In-place 稳定性
O(n^2) O(n^2) O(n^2) O(1) √ √

选择排序的选最大值部分经过优化后就引出了堆排序

堆排序

  1. 就地创建一个大顶堆
  2. 根据大顶堆的性质，最大元素在array[0],所以每次循环交换首尾元素，同时堆的大小减1，恢复堆的性质
  3. 当堆的大小为1时就完成了排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class HeapSort extends Sort {
    private int heapSize;

    @Override
    protected void sort() {
        heapSize = array.length;
        //原地建堆
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }

        while (heapSize > 1) {
            //交换堆顶元素与尾部元素
            swap(0, --heapSize);
            //0位置SiftDown
            siftDown(0);
        }


    }

    private void siftDown(int index) {
        int half = heapSize >> 1;
        Integer element = array[index];
        while (index < half) {
            int childIndex = (index << 1) + 1;
            Integer child = array[childIndex];

            int rChildIndex = childIndex + 1;
            if (rChildIndex < heapSize &&
                    cmpElement(array[rChildIndex], child) > 0
            ) {
                child = array[childIndex = rChildIndex];
            }

            if (cmpElement(element, child) > 0) {
                break;
            }
            array[index] = child;
            index = childIndex;
        }
        array[index] = element;
    }
}
  • 堆排序并不是一个稳定的排序
最好 最坏 平均 额外空间复杂度 In-place 稳定性
O(nlogn) O(nlogn) O(nlogn) O(1) √ ×

插入排序

  1. 从数组下标1开始依次选择数组元素与前一个元素比较
  2. 如果当前位置无序，就与前一个元素交换位置，直到有序
1
2
3
4
5
6
7
8
9
10
11
12
13
public class InsertSort<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            while (cur > 0 && cmp(cur, cur - 1) < 0) {
                swap(cur, cur - 1);
                cur--;
            }
        }
    }
}

最好 最坏 平均 额外空间复杂度 In-place 稳定性
O(n) O(n^2) O(n^2) O(1) √ √

关于插入排序需要了解一个概念

逆序对

  • 什么是逆序对？

    数组 <2,3,8,6,1> 的逆序对为：<2,1> <3,1> <8,1> <8,6> <6,1>，共5个逆序对

  • 插入排序的时间复杂度与逆序对的数量成正比关系，逆序对的数量越多，插入排序的时间复杂度越高

  • 当逆序对的数量极少时，插入排序的效率特别高，甚至速度比 O(nlog n )级别的快速排序还要快

  • 数据量不是特别大的时候，插入排序的效率也是非常好的

对于交换元素可以进行小小的优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class InsertSort<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            E e = array[cur];
            while (cur > 0 && cmpElement(e, array[cur-1]) < 0) {
                array[cur] = array[cur - 1];
                cur--;
            }
            array[cur] = e;
        }

    }
}

对于插入排序，找出插入位置的算法还可以进一步优化，我们先了解一下二分搜索

二分搜索

如何确定一个元素在数组中的位置？（假设数组里面全都是整数） 如果是无序数组，从第 0 个位置开始遍历搜索，平均时间复杂度：O(n)

0 1 2 3 4 5 6 7 8 9
31 66 17 15 28 20 59 88 45 56

如果是有序数组，可以使用二分搜索，最坏时间复杂度： O ( lo g n )

0 1 2 3 4 5 6 7 8 9
15 17 20 28 31 45 56 59 66 88

假设在 [begin, end) 范围内搜索某个元素 v，

  • mid == (begin + end) / 2
  • 如果 v < m，去 [begin, mid) 范围内二分搜索
  • 如果 v > m，去 [mid + 1, end) 范围内二分搜索
  • 如果 v == m，直接返回 mid

由此可以得出一个用二分搜索确定插入位置的算法

优化过的插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
@Override
   protected void sort() {
       for (int begin = 1; begin < array.length; begin++) {
           insert(begin, search(begin));
       }
   }

   /**
    * 插入元素
    * @param begin 源位置
    * @param dest 目标位置
    */
   private void insert(int begin, int dest) {
       int cur = begin;
       E e = array[cur];
       while (cur != dest) {
           array[cur] = array[cur - 1];
           cur--;
       }
       array[dest] = e;
   }

   /**
    * 查找e在有序数组中插入的位置
    * @return
    */
   private int search(int index) {
       E e = array[index];
       //左闭右开
       int begin = 0;
       int end = index;
       while (begin < end) {
           int mid = (begin + end) >> 1;
           if (cmp(array[mid], e) > 0) {
               end = mid;
           } else {
               begin = mid + 1;
           }
       }
       return begin;
   }

尽管优化过了插入时的搜索，但时间复杂度仍然是O(n^2)，因为插入时需要移动插入位置之后到插入元素源位置的所有元素

归并排序

  1. 将数组不断分为左右两部分，直到每个分数组元素只有一个
  2. 对相邻的分数组进行合并，合并后的数组应是有序的
  3. 重复2，直到整个数组有序
image-20210518221810636
  • 也可以这么说
  1. 不断地将当前序列平均分割成2个子序列 ✓ 直到不能再分割（序列中只剩1个元素）
  2. 不断地将2个子序列合并成一个有序序列 ✓ 直到最终只剩下1个有序序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
@SuppressWarnings({"unchecked"})
public class MergeSort<E extends Comparable<E>> extends Sort<E> {

    private E[] leftArray;

    @Override
    protected void sort() {
        leftArray = (E[]) new Comparable[array.length >> 1];
        sort(0, array.length);
    }

    /**
     * 对[begin,end)范围内的数据进行归并排序
     * end-begin就是范围内的元素个数
     *
     * @param begin
     * @param end
     */
    private void sort(int begin, int end) {
      //数组元素个数为1
        if (end - begin < 2) {
            return;
        }
      //分为左右两部分，分别进行归并排序
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
      //最后合并
        merge(begin, mid, end);
    }

    /**
     * 将 [begin,mid) 和 [id,end)范围的元素合并为一个有序序列
     */
    private void merge(int begin, int mid, int end) {
        //左数组的起始
        int li = 0, le = mid - begin;
        //右数组的起始
        int ri = mid, re = end;
        //覆盖的位置
        int ai = begin;
        //备份左数组
        for (int i = li; i < le; i++) {
            leftArray[i] = array[begin + i];
        }

        //左侧数组排序完就可以结束了
        while (li < le) {
            if (ri < re && cmp(array[ri], leftArray[li]) < 0) {
                array[ai++] = array[ri++];
            }else{
                array[ai++] = leftArray[li++];
            }
        }


    }
}

对于归并排序这类有递归调用的算法很难直观的看出时间复杂度，这时候就需要使用递推法来求啦

递推法求时间复杂度

  • 这里以归并排序举例

image-20210518222731444

  • 由于归并排序总是平均分割子序列，所以最好、最坏、平均时间复杂度都是 O ( nlo g n ) ，属于稳定排序

  • 从代码中不难看出：归并排序的空间复杂度是 O n / 2 + lo g n = O ( n ) n / 2 用于临时存放左侧数组，lo g n 是因为递归调用

常见递推式与复杂度

image-20210518224021431

快速排序

  1. 选择一个轴点元素
  2. 根据轴点将数组分为两部分，大于轴点的部分和小于轴点的部分
  3. 对于这两部分重复1、2，直到两部分元素个数都为1，排序完成
  • 根据轴点分为两部分

image-20210519141028131

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class QuickSort<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /**
     * 对[begin,end)范围进行快排
     *
     * @param begin
     * @param end
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) {
            return;
        }
        //确定轴点位置
        int mid = pivotIndex(begin, end);
        //对子序列排序
        sort(begin, mid);
        //注意这里
        sort(mid + 1, end);
    }

    private int pivotIndex(int begin, int end) {
        //随机取轴点
        swap(begin, begin + (int) Math.random() * (end - begin));
        E pivot = array[begin];
        --end;
        while (begin < end) {

            while (begin < end) {
                //右元素大于轴点元素
                if (cmp(pivot, array[end]) < 0) {
                    end--;
                } else {
                    array[begin++] = array[end];
                    break;
                }
            }
            while (begin < end) {
                //左元素小于轴点元素
                if (cmp(pivot, array[begin]) > 0) {
                    begin++;
                } else {
                    array[end--] = array[begin];
                    break;
                }
            }
        }
        array[begin] = pivot;
        return begin;
    }
}
最好 最坏 平均 额外空间复杂度 In-place 稳定性
O(nlogn) O(n^2) O(logn) O(logn) √ ×

  • 在轴点左右元素数量比较均匀的情况下，同时也是最好的情况 T n = 2 ∗ T n / 2 + O n = O ( nlo g n )

  • 如果轴点左右元素数量极度不均匀，最坏情况 T n = T n − 1 + O n = O ( n 2 )

这么写判断就会导致分割非常不平衡，时间复杂度O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while (begin < end) {
         //右元素大于轴点元素
         if (cmp(pivot, array[end]) <= 0) {
             end--;
         } else {
             array[begin++] = array[end];
             break;
         }
     }
     while (begin < end) {
         //左元素小于轴点元素
         if (cmp(pivot, array[begin]) >= 0) {
             begin++;
         } else {
             array[end--] = array[begin];
             break;
         }
     }
  • 为了降低最坏情况的出现概率，一般采取的做法是 随机选择轴点元素

希尔排序

  1. 希尔排序把序列看作是一个矩阵，分成 𝑚 列
  2. 对每一列进行排序（用插入排序）
  3. m从某个整数逐渐减为1
  4. 当 𝑚 为1时，整个序列将完全有序
  • 因此，希尔排序也被称为递减增量排序（Diminishing Increment Sort）
  • 矩阵的列数取决于步长序列（step sequence） 比如，如果步长序列为{1,5,19,41,109,…}，就代表依次分成109列、41列、19列、5列、1列进行排序
  • 不同的步长序列，执行效率也不同

image-20210520203906116

image-20210520203924195

image-20210520203937583

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class ShellSort<E extends Comparable<E>> extends Sort<E> {
    private List<Integer> stepSequence;

    @Override
    protected void sort() {
        stepSequence = shellStepSequence();
        for (Integer step : stepSequence) {
            sort(step);
        }

    }

    /**
     * 步长序列计算
     *
     * @return
     */
    private List<Integer> shellStepSequence() {
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while ((step >>= 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }

    /**
     * 分成step列进行排序
     *
     * @param step
     */
    private void sort(int step) {
        for (int col = 0; col < step; col++) {
            for (int begin = col + step; begin < array.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur-=step;
                }
            }
        }
    }
}

最好 最坏 平均 额外空间复杂度 In-place 稳定性
O(n) O(n^2) ？ O(1) √ ×
  • 最好情况是步长序列只有1，且序列几乎有序，这时时间复杂度最低
  • 希尔排序意图减少逆序对
  • 时间复杂度依赖于步长序列

非比较的排序

接下来介绍的几种排序算法属于空间换时间，有些时间复杂度可能比O(nlogn)更低

计数排序

  • 计数排序于1954年由Harold H. Seward提出，适合对一定范围内的整数进行排序

  • 计数排序的核心思想 统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class CountingSort extends Sort<Integer> {
    @Override
    protected void sort() {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        int[] counts = new int[1 + max];
        for (int i = 0; i < array.length; i++) {
            counts[array[i]]++;
        }

        int index = 0;
        for (int i = 1; i < counts.length; i++) {
            while(counts[i]-- >0){
                array[index++] = i;
            }
        }


    }
}

这是一种简单的计数排序，看得出来如果排序元素范围较大，会非常浪费空间

显然也无法对负数进行排序

  • 进行一些优化

现在我们有一个待排序数组array

image-20210521000316487

一个统计数组counts

image-20210521000440149

  • 假设array中的最小值是 min
  • array中的元素 k 对应的 counts 索引是 k – min
  • array中的元素 k 在有序序列中的索引 counts[k – min] – p
  • p 代表着是倒数第几个 k

举个例子

  • 比如元素 8 在有序序列中的索引 counts[8 – 3] – 1，结果为 7

  • 倒数第 1 个元素 7 在有序序列中的索引 counts[7 – 3] – 1，结果为 6

  • 倒数第 2 个元素 7 在有序序列中的索引 counts[7 – 3] – 2，结果为 5

这样，我们就可以直接遍历源数组，根据counts数组里的信息计算出排序后数组中的位置

由于需要遍历原数组，所以使用一个新的数组来存放

最好 最坏 平均 额外空间复杂度 In-place 稳定性
O(n+k) O(n+k) O(n+k) O(n+k) × √

Tips: 如果最后把值赋回去可不算就地排序hh，另外由于不是比较排序，所以讨论最好最坏没什么意义都一样。

也可以对自定义对象排序，前提是根据整数类型进行排序

讲完了计数排序，让我们来看看基于计数排序的另个整数排序算法^受限更大奥

基数排序

  • 基数排序非常适合用于整数排序（尤其是非负整数：依次对个位数、十位数、百位数、千位数、万位数…进行排序（从低位到高位）
  • 个位数、十位数、百位数的取值范围都是固定的0~9，可以使用计数排序对它们进行排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class RadixSort extends Sort<Integer> {
    @Override
    protected void sort() {
        int max = array[0];
        for(int i = 1;i<array.length;i++){
            if(array[i]>max){
                max = array[i];
            }
        }

        for (int divider = 1; divider <= max; divider*=10) {
            countingSort(divider);
        }

    }

    protected void countingSort(int divider) {
        //开辟存储空间
        int[] counts = new int[10];
        //统计每个元素出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i]/divider%10]++;
        }
        //累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        //从后向前遍历元素，放在合适位置，为了稳定性
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i]/divider%10]] = array[i];
        }

        for (int i = 0; i < array.length; i++) {
            array[i] = newArray[i];
        }

    }
}

桶排序

  1. 创建一定数量的桶（比如用数组、链表作为桶）

  2. 按照一定的规则（不同类型的数据，规则不同），将序列中的元素均匀分配到对应的桶

  3. 分别对每个桶进行单独排序

  4. 将所有非空桶的元素合并成有序序列

  • 因为桶排序并没有统一的分配规则，所以也没有统一的实现

这里以索引=元素值*元素个数实现一个桶排序

image-20210524090857959

时间复杂度 平均 额外空间复杂度 In-place 稳定性
O ( n + n ∗ lo g n − n ∗ lo g m ) O(n+k) O ( n + m ) × √
  • m是桶的数量

性能测试

讲了这么多，还是拿实际测试看看各种排序的性能吧

  • 对于所有排序，继承自一个抽象类,包含性能测试方法
  • 对于稳定性是根据对于自定对象排序，观察非排序字段是否有序来判断，因此有些排序不适用而直接返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
public abstract class Sort<E extends Comparable<E>> implements Comparable<Sort<E>> {
    protected E[] array;
    private int cmpCount = 0;
    private static final int MINCAPACITY = 2;

    private int swapCount = 0;
    private long time;
    private DecimalFormat fmt = new DecimalFormat("#.00");

    protected abstract void sort();

    public void sort(E[] array) {
        if (array == null || array.length < MINCAPACITY) {
            return;
        }
        this.array = array;
        time = System.currentTimeMillis();
        sort();
        time = System.currentTimeMillis() - time;
    }


    /**
     * 传入两个索引
     * 相等返回0
     * a>b返回正数
     * a<b返回负数
     *
     * @param a
     * @param b
     * @return
     */
    protected int cmp(int a, int b) {
        cmpCount++;
        return array[a].compareTo(array[b]);
    }

    protected int cmp(E a, E b) {
        cmpCount++;
        return a.compareTo(b);
    }

    protected void swap(int a, int b) {
        swapCount++;
        E temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    private String numberString(int number) {
        if (number < 10000) {
            return "" + number;
        }

        if (number < 100000000) {
            return fmt.format(number / 10000.0) + "万";
        }
        return fmt.format(number / 100000000.0) + "亿";
    }

    @Override
    public String toString() {
        String timeStr = "耗时：" + (time / 1000.0) + "s(" + time + "ms)";
        String compareCountStr = "比较：" + numberString(cmpCount);
        String swapCountStr = "交换：" + numberString(swapCount);
        String stableStr = "稳定性：" + isStable();
        return "【" + getClass().getSimpleName() + "】\n"
                + stableStr + " \t"
                + timeStr + " \t"
                + compareCountStr + "\t "
                + swapCountStr + "\n"
                + "------------------------------------------------------------------";

    }

    @Override
    public int compareTo(Sort o) {
        int result = (int) (this.time - o.time);
        if (result != 0) {
            return result;
        }
        result = this.cmpCount - o.cmpCount;
        if (result != 0) {
            return result;
        }
        return this.swapCount - o.swapCount;

    }

    private boolean isStable() {
        if (this instanceof RadixSort) return true;
        if (this instanceof CountingSort) return true;
        if (this instanceof CountingSort2) return true;
        if (this instanceof ShellSort) return false;
//        if (this instanceof SelectionSort) return false;
        Student[] students = new Student[20];
        for (int i = 0; i < students.length; i++) {
            students[i] = new Student(i * 10, 10);
        }
        sort((E[]) students);
        for (int i = 1; i < students.length; i++) {
            int score = students[i].score;
            int prevScore = students[i - 1].score;
            if (score != prevScore + 10) {
                return false;
            }
        }
        return true;
    }
}
  • 数据规模
image-20210524092424420
  • 结果

在10000个整数数据情况下，所有排序的时间都可以接受，但可以看出来几个非logn级别的比较排序明显慢了许多

image-20210524092538764

  • 数据规模

image-20210524093026947

  • 结果

当数据规模上升到10_0000,冒泡选择和插入这些非logn级别的排序已经很吃力了，所以下一个数据规模我不会带上他们了…

插入排序比较次数都溢出了…

image-20210524092916665

  • 数据规模

![image-20210524093354569](/Users/c1eye/Library/Application Support/typora-user-images/image-20210524093354569.png)

  • 结果

剩下的都是很能打的，不是logn级别的比较就是非比较拿空间换时间的，下次我们直接上1亿

希尔排序性能应该更好一点…可能是因为使用了没优化的插入排序

  • 数据规模

image-20210524094135412

  • 结果

😃

image-20210524094855590

对于这种级别的数据，想要在可以接受的时间内排序，就需要进行并行排序了。或者你内存够大！

image-20210524100330376

image-20210524100201994

  • 到此为止常见的排序已经有所了解了，实际上这些排序算法基本来自上个世纪，我们大多数时候是在前人的基础上用这些算法解决问题。
← Prev 我是伞兵 | vue-template 踩坑总结 Next →