常见的九大排序

发表于 | 分类于 |

前言：

这几天一直在整理排序的东西，然后发现还是有很多东西的。以前一直没怎么接触过桶排序（计数排序、基数排序），然后在整理排序的时候，认真的学习了一下，还有就是这篇博客其实两天前就计划写了的，嘿嘿嘿~因为小蚊子太懒辣~每次都说晚上来写，结果都咕咕掉了，今天终于痛心疾首！决定认真的记录一下了。

冒泡排序（Bubble Sort）：

1.基本思想：

从无序序列头部开始，进行两两比较，根据大小交换位置，知道最后将大（小）的数据元素交换到无需队列的队尾，从而成为有序列表的一部分；下一次继续这个过程，直到所有数据元素都排好序

2.运行过程：

冒泡排序算法的运作如下：

$(1)$比较相邻的元素。比如第一个比第二个大（小），就交换它们两个。

$(2)$对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（小）的数。

$(3)$针对所有的元素重复以上的步骤，除了最后已选出的元素（有序）。

$(4)$持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。

3.算法实现（核心代码）：

1
2
3
4
5
6
7
8
9
10
11
12
public int[] bubbleSort(int[] A, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (A[j] > A[j + 1]) {
                int temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
            }
        }
    }
    return A;
}

选择排序（Selection Sort）:

1.基本思想：

对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小（大）则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较，如果后面的元素比他要小(大）则用变量$k$记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小（大）的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小（大）的数了。然后找到数组中第二小（大）的数，让他跟数组中第二个元素交换一下值，以此类推。

2.运行过程：

$(1)$定义一个变量tmp记录待替换元素位置。

$(2)$比较待替换元素与当前元素的位置；若待替换元素大（小），则将tmp下标移到当前元素

$(3)$待替换元素与其后所有元素比较结束之后，交换待替换元素和tmp下标所记录的元素位置

$(4)$针对每一个元素重复以上操作，直到所有元素都有序。

3.算法实现（核心代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int[] selectionSort(int[] A) {
    for (int i = 0; i < A.length - 1; ++i) {
        int tmp = i;
        for (int j = i + 1; j < A.length; ++j) {
            if (A[tmp] > A[j])
                tmp = j;
        }
        if (tmp != i) {
            int temp = A[tmp];
            A[tmp] = A[i];
            A[i] = temp;
        }
    }
    return A;
}

插入排序（Insertion Sort）：

1.基本思想：

每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的元素中适当位置上，直到全部插入完为止。

2.运行过程：

$(1)$从第一个元素开始，该元素可以认为已经被排序。

$(2)$取出下一个元素，在已经排序的元素序列中从后向前扫描。

$(3)$如果该元素（已排序）大（小）于新元素，就将该元素移到下一位置。

$(4)$重复上述步骤，直到找到已排序元素小（大）于或等于新元素的位置。

$(5)$将新元素插入到下一位置中。

$(6)$重复上述步骤，直到所有元素有序。

3.算法实现（核心代码）：

1
2
3
4
5
6
7
8
9
10
11
public static int[] insertionSort(int[] A, int n) {
    for (int i = 1; i < A.length; ++i) {
        int tmp = A[i];
        int j;
        for (j = i - 1; j >= 0 && tmp < A[j]; --j) {
            A[j + 1] = A[j];
        }
        A[j + 1] = tmp;
    }
    return A;
}

希尔排序（Shell’s Sort）：

希尔排序是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。

1.基本思想：

先取一个小于$n$的整数$d_1$作为第一个增量，把元素的全部记录分组。所有距离为$d_1$的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量$d_2 < d_1$重复上述的分组和排序，直至所取的增量$d_t = 1(d_t < d_{t-1}… < d_2 < d_1)$，即所有记录放在同一组中进行直接插入排序为止。

2.运行过程：

$(1)$先取一个正整数$d_1 < n$，把所有序号相隔$d_1$的数组元素放在一组，组内进行直接插入排序。

$(2)$然后取$d_2 < d_1$，重复上述分组和排序操作。

$(3)$直到$d_i = 1$，即所有记录放进一个组中排序为止。

3.算法实现（核心代码）：

1
2
3
4
5
6
7
8
9
10
11
12
public static int[] shellSort(int[] A, int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < A.length; ++i) {
            for (int j = i - gap; j >= 0 && A[j] > A[j + gap]; j -= gap) {
                int tmp = A[j];
                A[j] = A[j + gap];
                A[j + gap] = tmp;
            }
        }
    }
    return A;
}

堆排序（Heapsort）：

1.基本思想：

若以升序排序说明，把数组转换成最大堆积(Max-Heap Heap)，这是一种满足最大堆积性质(Max-Heap Property)的二叉树：对于除了$root$之外的每个节点 $i$, $A[parent(i)] ≥ A[i]$。

重复从最大堆积取出数值最大的节点(把$root$节点和$last$节点 交换，把交换后的$last$节点移出堆)，并让残余的堆积维持最大堆积性质。

2.运行过程：

$(1)$根据数组元素，建立最大（小）堆。

$(2)$取出最大（小）堆中的$root$节点与$last​$节点交换。

$(3)$调整恢复最大（小）堆。

$(4)$重复上述步骤，直至最大（小）堆中只有一个节点。

3.算法实现（核心代码）：

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
public static int[] heapSort(int[] A, int n) {
    int beginIndex = n / 2;
    //建堆
    for (int i = beginIndex; i >= 0; --i) {
        maxHeapify(A, i, n);
    }
    for (int i = n - 1; i > 0; --i) {
        int tmp = A[0];
        A[0] = A[i];
        A[i] = tmp;
        maxHeapify(A, 0, i);
    }
    return A;
}

private static void maxHeapify(int[] a, int i, int n) {
    int l = i * 2 + 1;
    int r = i * 2 + 2;
    int Max = i;
    if (l < n && a[l] > a[Max])
        Max = l;
    if (r < n && a[r] > a[Max])
        Max = r;
    if (Max != i) {
        int tmp = a[Max];
        a[Max] = a[i];
        a[i] = tmp;
        maxHeapify(a, Max, n);
    }
}

归并排序（Merge Sort）：

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

1.基本思想：

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2.运行过程：

$(1)$申请空间，使其大小为两个已排序序列之和，该空间用来存放合并后的序列。

$(2)$设定两个指针，最初位置分别为两个已经排好序列的起始位置。

$(3)$比较两个指针所指向的元素，选择相对小（大）的元素放入合并空间，并移动指针到下一位置。

$(4)$重复上述操作，直到所有元素直接复制到合并序列尾。

3.算法实现（核心代码）：

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
public static int[] mergeSort(int[] A, int n) {
    mergeSort_process(A, 0, A.length - 1);
    return A;
}

private static void mergeSort_process(int[] a, int l, int r) {
    if (l == r)
        return;
    int mid = (l + r) / 2;
    mergeSort_process(a, l, mid);
    mergeSort_process(a, mid + 1, r);
    merge(a, l, mid, r);
}

private static void merge(int[] a, int l, int mid, int r) {
    int[] tmp = new int[r - l + 1];
    int ll = l;
    int rr = mid + 1;
    int index = 0;
    while (ll <= mid && rr <= r) {
        if (a[ll] <= a[rr])
            tmp[index++] = a[ll++];
        else {
            tmp[index++] = a[rr++];
        }
    }
    while (ll <= mid)
        tmp[index++] = a[ll++];
    while (rr <= r)
        tmp[index++] = a[rr++];
    for (int i = 0; i < tmp.length; ++i)
        a[l + i] = tmp[i];
}

快速排序（Quick Sort）：

快速排序是对冒泡排序的一种改进。

1.基本思想：

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

2.运行过程：

$(1)$从元素中任取一个数据作为关键数据（$key$）。

$(2)$所有小于$key$的元素，都移到$key$的左边；所有大于$key$的元素都移到$key$的右边。

$(3)$重复上述步骤，直到所有子集只剩下一个元素为止。

3.算法实现（核心代码）：

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
public static int[] quickSort(int[] A, int n) {
    quickSort_process(A, 0, A.length - 1);
    return A;
}

private static void quickSort_process(int[] a, int l, int r) {
    if (l > r) {
        return;
    }
    int tmp = a[l];
    int i = l;
    int j = r;
    while (i != j) {
        while (a[j] >= tmp && i < j) {
            --j;
        }
        while (a[i] <= tmp && i < j) {
            ++i;
        }
        if (i < j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    a[l] = a[i];
    a[i] = tmp;

    quickSort_process(a, l, i - 1);
    quickSort_process(a, i + 1, r);
}

计数排序（Counting Sort）：

计数排序是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为$Ο(n+k)$（其中$k$是整数的范围），快于任何比较排序算法。但是这个是牺牲空间换取时间的做法。

1.基本思想：

$(1)$限制条件：输入的线性表的元素属于有限偏序集$S$

$(2)$思想：它创建一个长度为这个数据范围的数组，数组中每个元素记录要排序数组中对应记录的出现个数，最后再按照个数依次取出元素。

2.运行过程：

$(1)$找出待排序的数组中最大的元素，创建数组$C$（记录待排序数组中每个元素的个数，长度即为最大元素值）。

$(2)$统计数组中每个值为$i$的元素出现的次数，存入数组$C$的第$i$项。

$(3)$对所有的计数累加（从$C​$中的第一个元素开始，每一项和前一项相加）。

$(4)$反向填充目标数组：将每个元素$i$放在新数组的第$C[i]$项，每放一个元素就将$C[i]$减去1。

3.算法实现（核心代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int[] countingSort(int[] A, int n) {
    int Max = Arrays.stream(A).max().getAsInt();
    int mask[] = new int[Max + 1];
    for (int i = 0; i < A.length; ++i) {
        mask[A[i]] += 1;
    }
    for (int i = 0, j = 0; i < mask.length; ++i) {
        while (mask[i] > 0) {
            A[j++] = i;
            mask[i] -= 1;
        }
    }
    return A;
}

基数排序（Radix Sort）：

1.基本思想：

将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

2.运行过程：

$(1)$将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补$0$。

$(2)$从最低位开始，依次进行一次排序，排序之后，继续对排序之后的数组进行下一位排序。

$(3)$重复上面步骤，直至最高位排序完成之后。

3.算法实现（核心代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int[] radixSort(int[] A, int n) {
    int Max = Arrays.stream(A).max().getAsInt();
    for (int exp = 1; Max / exp > 0; exp *= 10) {
        count_sort(A, exp);
    }
    return A;
}

private static void count_sort(int[] a, int exp) {
    int output[] = new int[a.length];
    int mask[] = new int[10];
    for (int i = 0; i < a.length; ++i) {
        mask[(a[i] / exp) % 10]++;
    }
    for (int i = 1; i < mask.length; ++i) {
        mask[i] += mask[i - 1];
    }
    for (int i = a.length - 1; i >= 0; --i) {
        output[--mask[(a[i] / exp) % 10]] = a[i];
    }
    for (int i = 0; i < a.length; ++i) {
        a[i] = output[i];
    }
}

时间/空间复杂度、稳定性比较：

时间复杂度 空间复杂度 稳定性
冒泡排序 $O(N^2)$ $O(1)$ 稳定
选择排序 $O(N^2)$ $O(1)$ 不稳定
插入排序 $O(N^2)$ $O(1)$ 稳定
希尔排序 $O(N*logN)$ $O(1)$ 不稳定
堆排序 $O(N*logN)$ $O(1)$ 不稳定
归并排序 $O(N*logN)$ $O(N)$ 稳定
快速排序 $O(N*logN)$ $O(logN)$~$O(N)$ 不稳定
计数排序 $O(N)$ $O(M)$($M$为所选桶的数量) 稳定
基数排序 $O(N)$ $O(M)$($M$为所选桶的数量) 稳定