排序

相关排序方式

• 选择、插入、归并、快速等等

选择排序

• 定义
  选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

• 时间复杂度
  O(n^2): n 表示数组的长度

• 是否原址
  是（不需要借助其他数组）

• 程序实现

    public void sort(int A[]) {
        for (int i = 0; i < A.length; i ++) {
            int min = i;
            for (int j = i + 1; j < A.length; j ++) {
                if (A[j] < min) {
                    min = j;
                }
            }
            // 最小值放到索引 i 的位置
            int temp = A[min];
            A[i] = A[min];
            A[min] = temp;
        }
    }

插入排序

• 定义
  插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

• 时间复杂度
  O(n^2): n 表示数组的长度

• 是否原址
  是（不需要借助其他数组）

• 程序实现

    public void sort(int A[]) {
        for (int i = 1; i < A.length; i ++) {
            for (int j = i; j > 0 && A[j] < A[j - 1]; j --) {
                // 交换下标j与下标j-1的值
                int temp = A[j];
                A[j] = A[j - 1];
                A[j - 1] = temp;
            }
        }
    }

• 缺点
  在最坏的情况（数组逆序），数组元素移动的次数为O(n^2)
• 与选择排序的对比
  1. 都是维护两个数组：左边的有序，右边的无序
  2. 插入排序在写入左边的数组时，需要寻找插入点。选择排序则是在现在右边找到最小的，然后直接写入左边数组的末尾。
  3. 插入排序在写入左边数组时，插入点后面的元素都要后移一位

归并排序

• 定义
  归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
  归并排序使用分治法，将原问题分解为类似原问题的子问题。

• 时间复杂度
  O(nlogn): n 表示数组的长度

• 是否原址
  否（需要借助其他数组）

• 程序实现

/**
     * 归并排序
     * @param A 数组
     * @param p 要操作的起始位置
     * @param r 要操作的终点位置
     */
    public void mergeSort(int A[], int p, int r) {
        if (p >= r) {
            return;
        }
        // 分解为两个子问题
        int q = (p + r) / 2;
        mergeSort(A, p, q);
        mergeSort(A, q + 1, r);
        // 归并
        merge(A, p, q, r);
    }

    public void merge(int A[], int p, int q, int r) {
        int n1 = q - p + 1; // 数组左部长度
        int n2 = r - q; // 数组左部长度
        // 将数组copy到新数组中
        int B[] = new int[n1 + 1];
        int C[] = new int[n2 + 1];
        System.arraycopy(A, p, B, 0, n1);
        System.arraycopy(A, q + 1, C, 0, n2);
        // 新数组的最后一位设置为最大值, 防止数组越界。这里应该设置为正无穷大，但需要用double。
        // 这里先用int的最大值。所以数组不可以存在大于int最大值的元素
        B[n1] = Integer.MAX_VALUE;
        C[n2] = Integer.MAX_VALUE;

        // 归并两个新数组
        int i = 0, j = 0;
        for (int k = p; k <= r; k ++) {
            if (B[i] <= C[j]) {
                A[k] = B[i];
                i ++;
            } else {
                A[k] = C[j];
                j ++;
            }
        }
    }

• 缺点
  需要额外的内存空间开销

快速排序

• 定义
  快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
  (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
  (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
  (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
  (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

• 与归并排序的对比
  归并：分解-》排序-》归并......
  快速：粗略排序（数组分为做大右小两部分）-》分解（左右两部分）-》粗略排序......

• 时间复杂度
  最好：O(nlogn): n 表示数组的长度
  最坏：O(n^2)：数组本身就是有序的
  平均：O(nlogn)

• 是否原址
  是（不需要借助其他数组）

• 程序实现

 /**
     * 快速排序
     * @param A 数组
     * @param p 要操作的起始位置
     * @param r 要操作的终点位置
     */
    public void quickSort(int A[], int p, int r) {
        if (p >= r) {
            return;
        }

        // 将数组分解为左右两部分(两部分都是无序的，但右边的都比左边的大)，
        // 并获取中间索引
        int q = partTition(A, p, r);

        // 将左右两部分递归排序
        quickSort(A, p, q - 1);
        quickSort(A, q + 1, r);
    }

    public int partTition(int A[], int p, int r) {
        int q = p;

        // 这里将r设置为主元（在数组
        for (int u = p; u < r; u ++) {
            if (A[u] < A[r]) {
                int temp = A[q];
                A[q] = A[u];
                A[u] = temp;
                q ++;
            }
        }
        int temp = A[q];
        A[q] = A[r];
        A[r] = temp;
        return q;
    }

• 缺点
  若排序时，主元为最大的，为最差情况，递归次数最多。
  比如，数组本身有序，主元为最后一个元素，那么拆分后的左右两个数组，其中一个为原数组长度-1，每次拆分-1，最多需要拆分2n-1次