聊聊排序算法

发表于 | 浏览 次

前言

在平时的编程中，可能会遇到对一组数据进行排序，这个时候我们通常就是调用jdk提供的Arrays.sort()方法来帮助我们进行处理排序，往往并不清楚里面到底做了什么，其实Arrays.sort方法是用了排序算法中的一种，快速排序，那么什么是快速排序？有没有其他类型的排序算法呢？

什么是排序

在了解排序算法之前，我们先来了解下什么是排序
在计算机科学中，一个排序算法是一种能将一串数据按照制定排序方式进行排列的一种算法

排序算法

在了解上文提到的快速排序之前，我们先看看有哪些排序算法

冒泡排序

概述

冒泡排序是一种简单的排序算法，它重复的走访要排序的数列，每次比较两个元素，如果他们顺序错误，则进行交换，走访队列的工作就是重复的进行比较知道没有再需要交换的数据，也就是该数列已经排序完成，这个算法的命名是因为越小的元素会经过交换而慢慢的浮到数列的顶端.
冒泡排序对于n个元素的排序需要进行O(n^2)的比较次数，并且可以原地排序

整体工作流程

  1. 比较相邻的两个元素，如果第一个比第二个大，就交换他们两个
  2. 对每一对相邻元素进行同样的操作，从开始的那一对一直比较到结尾的最后一对，这步完成后最后的元素，将是最大元素
  3. 针对所有元素重复以上步骤，除去最后一个元素
  4. 每次持续对越来越少的元素执行上述步骤，直到没有任何一对数字需要比较

时间复杂度

时间复杂度为O(n^2)

空间复杂度

O(n) 辅助空间O(1)

最优时间复杂度

正序有序数列
O(n^2)

最差时间复杂度

逆序有序数列
O(n^2)

数据结构

数组

是否稳定

是

一些可以优化的点

如果冒泡排序在对一个有序队列进行排序的话，那么在一趟排序下来必定没有发生任何一次交换，反过来说也成立，如果一趟排序中没有发生任何一次交换，则说明队列就是有序的，那么这时候我们只需要引入一个标志，如果一趟排序没有交换发生，我们就可以退出循环，不再需要执行后续的循环了，这样可以使得冒泡排序在最优场景正序有序的数据场景，时间复杂度降为O(n)

插入排序

概述

插入排序是一种简单直观的排序算法，它的工作原理是构建有序队列，对于未排序的数据，会在已排序的队列中从后向前进行反向扫描，找到相应的位置并进行插入，插入排序在实现上只需用O(1)的额外空间，因此在从后向前的扫描的过程中，需要反复将已排序元素逐步向后挪位，从而为新元素提供插入空间。
这个过程和我们平时打扑克的时候，将牌进行一步步排序的过程比较相似，拿到一张牌的时候，我们先认为手中的牌堆是有序的，然后新抓的牌在牌堆里面找到合适的位置并进行插入，反复抓牌并重复该过程，直至牌抓完，手中的牌也就成了有序的

整体工作流程

  1. 从第一个元素开始，该元素被认定为已经有序
  2. 取出下一个元素，在已经排序的元素中从后向前进行扫描
  3. 如果该已排序的元素大于刚才取出的元素，则将该元素进行后移
  4. 重复步骤3，直到找到已排序的元素中小于或等于新元素的位置
  5. 将新元素插入到该位置
  6. 重复步骤2-5

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void sort(int[] data) {

        //选定第一位为已排序数列，从下一个元素开始排序,并逐个对新加入元素(数组后面元素)进行插入排序
        for (int i = 1; i < data.length; i++) {
            int newElement = data[i];
            int j = i - 1;
            //从后向前扫描,如果新插入的元素比已排序队列的待比较元素要小，则后移该元素
            //若新插入的元素比带比较元素大，则证明已经找到该元素的位置
            while (j >= 0 && newElement < data[j]) {
                data[j + 1] = data[j];
                j--;
            }
            //将该元素插入到该位置
            data[j + 1] = newElement;

        }
    }

时间复杂度

O(n^2)

最优时间复杂度

正序有序
O(n)

最差时间复杂度

逆序有序
O(n^2)

数据结构

数组

空间复杂度

O(n) 辅助空间 O(1)

是否稳定

是

一些可以优化的点

由于插入排序在已排序队列中找自己的位置的时候是逐次比较的，由于该队列是有序的，那么这里其实可以简单的进行一个优化，在找位置的时候可以通过二分查找法来进行减少比较次数，但是由于交换次数不变，算法的时间复杂度依旧是O(n^2)

选择排序

概述

选择排序是一种简单直观的排序算法，它的工作原理大致如下，首先在未排序的数据中找最大或者最小的元素，存放到排序队列的起始位置，然后再从剩余未排序的元素中寻找最大或者最小元素，然后放在已排序队列的队尾，以此类推，直到所有的元素均排序完毕

选择排序的优点主要跟数据移动有关，如果某个数据已经位于正确的位置上面，则它不会进行移动，选择排序每次交换一对元素，它们之中至少有一个将被移到其最终位置上面，因此对n个元素的表进行排序的话，只会涉及到至多n-1次交换，在所有完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

交换操作比比较所需要的CPU较少，而选择排序比冒泡排序交换次数要少，所以当空间复杂度要求较高的时候，可以考虑选择排序，实际适用的场景相当罕见

时间复杂度

O(n^2)

最优时间复杂度

正序有序
O(n^2)

最差时间复杂度

逆序有序
O(n^2)

数据结构

数组

空间复杂度

O(n) + 辅助空间O(1)

是否稳定

不稳定

快速排序

概述

快速排序，又称分区交换排序，简称快排，在需要对n个元素进行排序的时候需要O(nlogn)次比较，最坏的时候需要O(n^2)次比较，但这并不常见

工作流程

  1. 从数列中挑选一个基准值(通常会选定起始元素)
  2. 对数列进行分割，将所有小于基准值的放在基准值左侧，大于基准值的元素放在基准值右侧
  3. 递归地对基准值两侧的队列重复1,2步骤

代码实现

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
public static void sort(int[] data, int head, int tail) {
        int startIndex = head;
        int endIndex = tail;
        //递归终止条件，如果分区中元素只有 0 或1 个则已经有序
        if (tail - head <= 1) {
            return;
        }
        int selectedElement = data[startIndex];
        if (head < tail) {
            //按基准值进行分区,左面的分区都小于等于基准值,右面的分区都大于基准值
            while (head < tail) {
                //从右向左找第一个小于等于基准值的元素
                if (data[tail] <= selectedElement) {
                    //找到后，再从左至右找第一个大于基准值的元素，并交换它们
                    if (data[head] > selectedElement) {
                        swap(data, head, tail);
                    } else {
                        head++;
                    }
                } else {
                    tail--;
                }
            }
            //head和tail指针重合,此时说明除了指针处所有元素已经交换完毕,则交换基准值和head指针处元素
            swap(data, startIndex, head);
            //分区后对左右两个子分区进行递归，重复上述操作
            sort(data, startIndex, head - 1);
            sort(data, head + 1, endIndex);
        }
    }

    public static void swap(int[] data, int head, int tail) {
        if (data[head] > data[tail]) {
            //对两个元素进行交换
            data[head] = data[head] + data[tail];
            data[tail] = data[head] - data[tail];
            data[head] = data[head] - data[tail];

        }
    }

时间复杂度

O(nlogn)

最优时间复杂度

O(nlogn)

最差时间复杂度

O(n^2)

空间复杂度

快速排序所使用的空间，需要依照使用的版本决定。使用原地分割的快速排序版本，在任何递归调用前都会使用固定的额外空间，如果需要产生O(logn)次嵌套递归调用，则需要O(logn)的空间

是否稳定

否

一些可以优化的点

基准值选定问题，如果待排序数据是乱序的，基准值是第一个或者最后一个都没问题，但是如果是已经排好序的数据，如果选定第一个或者最后一个为基准值，分区的时候就会出现基准值分区后，只有一个分区有元素

希尔排序

概述

希尔排序，可以称为递减增量的排序算法，是插入排序的一种高效的改进版本
希尔排序是基于插入排序以下两点性质提出改进方法的：

  1. 插入排序在对几乎已经排好序(正序有序)的数据操作时，操作效率高，可以达到线性排序的效率(O(n))
  2. 插入排序一般来说是低效的，因为插入排序每次只能向前移动一位

希尔排序实际上是一个分组排序的过程，每一次通过一个步长对整个数列进行分组，对每个分组内的数据进行插入排序，然后缩小步长，再对每个分组内的数据进行插入排序，直到最后每个分组内的元素只有一个的时候，对该数列的排序演变为普通的插入排序，此时的数列经过方才的过程已经几乎接近有序队列，这时候再使用插入排序效率几乎能达到插入排序的最优时间复杂度即线性排序

在数量较少的时候，希尔排序甚至比堆排序和快速排序要快，但是涉及到大量数据的时候希尔排序还是要比快速排序要慢

工作流程

  1. 选定步长，并建立分组
  2. 对每一个分组进行插入排序操作
  3. 将步长按照一定的规则进行处理，这里步长规则选为每次除以2
  4. 重复步骤1 2 直至步长变为最小步长1
  5. 步长变为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
public void sort(int[] data) {
        //对数列按照gap进行分组,当gap>=1时,对每组元素进行插入排序
        for (int gap = data.length /2; gap >= 1; gap/=2) {
            //分组遍历处理
            int groups = data.length / gap;
            for (int i = 0; i <= groups; i++) {
                //对每一组中的元素进行插入排序
                insertSortAlgorithm.sort(data,i,gap);
            }
        }
    }

-------------------------------------------------------------------
//insertSortAlgorithm.sort()
public void sort(int[] data,int start, int gap) {
        for (int i = start + gap; i < data.length; i += gap) {
            int newElement = data[i];
            int j = i - gap;
            while (j >= 0 && newElement < data[j]) {
                data[j + gap] = data[j];
                j -= gap;
            }
            data[j+gap] = newElement;
        }
    }

平均时间复杂度

根据步长序列选定规则决定

最优时间复杂度

O(n)

最差时间复杂度

根据步长序列选定规则决定

步长选定规则 时间复杂度
n /2^i O(n^2)
2^k -1 O(n^3/2)
2^i * 3^j O(nlog^2n)

是否稳定

不稳定

未完待续——

堆排序

概述

时间复杂度

是否稳定

归并排序

概述

时间复杂度

是否稳定