“排序

发表于
:thinking:为什么插入排序比冒泡排序更受欢迎？

如何分析一好“排序算法”？

排序算法的执行效率

  • 最好情况，最坏情况，平均情况时间复杂度
  • 时间复杂度的系数，常数，低阶
  • 比较次数和交换（或移动）次数

排序算法的内存消耗

  • 这里引入一个原地排序（Sorted in place）。原地排序是指空间复杂度为O(1)的排序算法

排序算法的稳定性

  • 稳定性：指定的是数组中值相同的元素，在排序之后的相对位置没有发生变化

    例如：

    排序前

    • 2，4，1，8，9，4，5，3

    排序后

    • 1，2，3，4，4，5，8，9

    这里边有两4，在经过排序之后，如果两个4的前后顺序没有发生变化，就将该排序算法称为稳定的排序算法，反之称为不稳定排序算法

那么稳定排序有什么意义呢？

例如：电商交易系统中的“订单”排序。订单两个属性，一是下单的时间，二是订单的金额。如果在一批订单中，按照订单的金额从小到大对订单排序，对于金额相同的订单，而是按照下单时间从早到晚有序。那么该如何处理这个需求呢？

  • 如果采用不稳定排序算法去进行排序，就会相当的麻烦，首先按照金额排序，再在金额相同的订单中按照时间排序，这样需要将相同金额的订单，按照各自小区间排序，实现起来就很复杂。

  • 如果采用稳定的排序算法，先按照时间对订单排序（这里比一定要是用稳定排序算法），再使用稳定排序算法，按照订单的金额重新排序。这样，得到的数据就是按照金额从小到大排序，而在金额相同的订单中是按照下单时间从早到晚排序。

  • 稳定排序算法保证了金额相同的两个对象，在排序之后的前后顺序不变。

时间复杂度为O(n^2)的排序算法

冒泡排序（Bubble Sort）

  • 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

如下图所示：一次冒泡的执行流程

  • 冒泡排序的优化：当某个冒泡操作已经没有数据交换时，表明数组中的所有元素已经有序，就不再需要进行后续的冒泡操作，例如：

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public  void bubbleSort(int[] a, int n) {
    if (n <= 1) return;
    for (int i = 0; i < n; i++) {
        boolean flag = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                //冒泡优化，当再一次冒泡中没有进行数据交换时，证明已经是有序数组
                flag = true;
            }
        }
        if (!flag) break;
    }
问题一：冒泡排序是原地排序算法吗？
  • 冒泡排序只需要涉及相邻数据的交换，只需要常量级的临时空间，空间复杂度为O(1)，是原地排序算法。
问题二：冒泡排序是稳定的排序算法吗？
  • 冒泡排序是交换两个元素的顺序，为了保证稳定性，当相邻元素大小相等时，不做交换，所以是稳定的排序算法。
问题三：冒泡排序的时间复杂度是多少？
  • 最坏情况：需要进行n次冒泡操作，时间复杂度为O(n^2)
  • 最好情况：数组已经有序，只需要进行一次冒泡操作，时间复杂度为O(n)
  • 平均情况：时间复杂度为O(n^2)

插入排序（Insertion Sort）

  • 插入排序的实现过程：将数组划分为，已排序区间和未排序空间。初始的已排序空间只有一个元素，就是数组第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

如下图所示：要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。

  • 插入排序包含两种操作：元素的比较，元素的移动

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void insertSort(int a[], int n) {
       if (n <= 1) return;
       //下标从1开始
       for (int i = 1; i < n; i++) {
           int value = a[i];
           int j = i - 1;
           for (; j >= 0; j--) {
               if (a[j] > value)  
                   a[j + 1] = a[j];
               else  
                   break;
           }
           a[j + 1] = value;
       }
   }
问题一：插入排序是原地排序算法吗？
  • 插入排序不需要额外的存储空间，空间复杂度O(1)，属于原地排序算法
问题二：插入排序是稳定的排序算法吗？
  • 插入排序中，对于相同值的元素，可以选择将后面出现的元素，插入到前面出现元素的后边，这样就可以保证原有前后顺序不变，属于稳定的排序算法。
问题三：插入排序的时间复杂度是多少？
  • 最坏情况：数组是倒序的，每次都需要在数组的第一个位置插入新的数据，需要大量的搬移数据，时间复杂度为O(n^2)
  • 最好情况：数组是有序的，只需要从头到尾遍历已经有序的数据即可。
  • 平均情况：时间复杂度为O(n^2)

选择排序（Selection Sort）

  • 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void selectionSort(int[] a, int n) {
    if (n <= 1) return;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            //更新已排序中最小数的下标
            if (a[j] < a[min]) 
                min = j;
            //如果下标发生改变，数据进行交换
            if (min != i) {
                int value = a[min];
                a[min] = a[i];
                a[i] = value;
            }
        }
    }
}
问题一：插入排序是原地排序算法吗？
  • 空间复杂度为O(1)，属于原地排序算法
问题二：插入排序是稳定的排序算法吗？
  • 选择排序每次都需要在剩余未排序的元素中找出最小值，和前面的元素进行交换，这样就破坏里稳定性，属于不稳定的排序算法。
问题三：插入排序的时间复杂度是多少？
  • 最坏，最好，平均时间复杂度均为O(n^2)

时间复杂度为O(n^2)的排序算法

:thinking:如何在O(n)的时间复杂度查找一个无序数组中的第K大元素？

归并排序（Merge 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
public void margeSort(int[] a, int n) {
    marge_Sort(a, 0, n - 1);
}

public void marge_Sort(int[] a, int l, int r) {
    if (l >= r) {
        return;
    }
    int m = l + ((r - l) >> 1);
    marge_Sort(a, l, m);
    marge_Sort(a, m + 1, r);
    marge(a, l, m, r);
}

public void marge(int[] a, int l, int m, int r) {
    //申请一个与原数组大小相同的临时数组
    int[] tmp = new int[a.length];
    int i = l;
    int j = m + 1;
    int k = 0;
    while (i <= m && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
        }
    }
    //判断哪个数组有剩余的数据
    int start = i;
    int end = m;
    if (j <= r) {
        start = j;
        end = r;
    }
    //将剩余数据拷贝到临时数组
    while (start <= end) {
        tmp[k++] = a[start++];
    }
    //将临时数组中的数据拷贝会原数组，注意边界条件
    for (i = 0; i <= r - l; i++) {
        a[l + i] = tmp[i];
    }
}
问题一：归并排序是稳定排序算法吗？
  • 在合并数组的过程中，在两个有序数组合并一个有序数组，相同的元素可以规定哪个在前面将该元素放在新数组前面，属于稳定的排序算法。
问题二：归并排序的时间复杂度是多少？
  • 最好，最坏，平均时间复杂度均为O(nlogn)

快速排序（Quick Sort）

  • 快排思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。