排序算法

插入、选择、冒泡排序的时间复杂度都是 $O(n^2)$, 快排、归并排序的时间复杂度都是 $O(nlog_n)$, 这五个都是基于比较的排序算法。

分析排序算法

执行效率

对于排序算法的执行效率的分析，一般会从这几个方面来衡量。

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

内存消耗

算法的内存消耗可以通过空间复杂度来度量，排序算法也是如此。

针对排序算法的空间复杂度，有一个新的概念：原地排序（Sorted in place），特指空间复杂度为 O(1) 的排序算法。

稳定性

待排序的序列存在值相同的元素，经过排序之后，相等元素之间原有的先后顺序不变，这种排序算法就叫做 稳定的排序算法。

直接插入排序

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

前 i-1 个元素是有序的，第 i 个元素一次从第 i-1 个元素往前比较，直到找到第一个比第 i 个元素小的元素，而后插入，插入位置及其后的元素一次向后移动

当给出一组无序的元素时，首先，应该将第一个元素看作是一个有序的序列，而后从第二个元素开始，按插入排序规则，依次与前面的元素进行比较，直到找到第一个小于它的值，才插入。示例如下图：

直接插入排序

/**
* 直接插入排序
*  [0,i-1] 有序，从 [0,i-1] 中找到第一个小于 arr[i] 的元素
* @param arr 待排序数组
*/
public static void insertedSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) { // [0,i-1] 有序，
        int target = arr[i];
        int j = i - 1;
        for (; j >=0 ; j--) {
            if (arr[j] > target) {
                arr[j + 1] = arr[j];
            }else{
                break;
            }
        }
        arr[j + 1] = target;
    }
}

• 插入排序是原地排序算法
• 插入排序是稳定排序算法 （对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的顺序不变）

简单选择排序

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

n 个记录进行简单选择排序的基本方法是：通过 n-i ($1\leq i \leq n$) 次关键字之间的比较，从 n-i+1 个记录中选出关键字最小的记录，并和第 i 个记录进行交换，当 i 等于 n 时所有记录有序排列。

本质就是每次选择出最小的元素进行交换，主要是选择过程，交换过程只有一次。

每一次排序需要多次比较，只需要经过一次交换。

选择排序

/**
 * 选择排序
 * @param arr 待排序数组
 */
public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) { // 维护有序数组，i 表示待交换元素
        int minIndex = i;
        for (int j = i ; j < arr.length; j++) {
            if(arr[j]<arr[minIndex]){
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);
    }
}

• 选择排序是原地排序算法
• 选择排序是一种不稳定的排序算法，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

冒泡排序

首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录，以此类推，直到第 n-1 个关键字记录和第 n 个记录的关键字比较过为止。

上述过程称为一趟冒泡排序，其结果是关键字最大的记录被交换到第 n 个记录的位置上。

然后进行第二趟冒泡排序，对前 n-1 个记录进行同样的操作，其结果是关键字次大的记录被交换到第 n-1 个记录的位置上。

最多进行 n-1 躺，所有记录有序排列。

若在某躺冒泡排序过程中没有进行相邻位置元素交换处理，则可结束排序过程。

外层循环记录躺数，从 n-1 开始，递减。 内层循环进行比较，从 0 到 n-i-1

冒泡排序

/**
 * 冒泡排序
 * @param arr 待排序数组
 */
public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length-1; i++) {
        boolean swapped = false;
        for (int j = 0; j < arr.length-i-1; j++) {
            if(arr[j]>arr[j+1]){
                swap(arr, j, j+1);
                swapped = true;
            }
        }
        if(!swapped){
            break;
        }
    }
}

• 冒泡排序是原地排序算法
• 冒泡排序是稳定的排序算法（当相邻两个元素相等的时候， 不做交换，相同大小的元素在排序前后不改变位置，所以冒泡排序是稳定的排序算法。

归并排序

归并排序的核心思想很简单。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样这个数组都有序了。

归并排序使用的就是分治思想，顾名思义，就是分而治之，将一个大问题分解成小的问题来解决。小的问题解决了，大问题也就解决了。

分治算法一般都是采用递归实现的，分治是一种解决问题的处理思想，递归是一种编程技巧

写递归代码需要先分析出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。

归并排序递推公式和终止条件

// 递推公式
merge_sort(p...r) = merge(merge_sort(p...q),merge_sort(q+1...r));
// 终止条件
p>=r 不需要再继续分解

merge_sort(p...r) 表示，给下标 p 到 r 之间的数组排序。我们将这个排序问题转化成两个子问题 merge_sort(p...q) 和 merge_sort(q+1...r)，其中下标 q 等于 p 和 r 的中间位置，也就是 (p+r)/2。 当两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样下标从 p 到 r 之间的数据就也排好序了。

归并排序

 /**
 * 归并排序调用函数
 * @param arr 待排序数组
 */
public static void quickSort(int[] arr) {
    int[] temp = new int[arr.length];
    quickSort(arr, temp,0, arr.length-1);
}
/**
 * 归并排序主函数
 * @param arr 待排序数组
 * @param left 左边
 * @param right 右边
 */
public static void quickSort(int[] arr, int[] temp,int left, int right) {
    if(left >= right){
        return;
    }
    int mid = left + (right - left) / 2;
    quickSort(arr, temp,left, mid);
    quickSort(arr,temp, mid + 1, right);
    merge(arr,temp, left, mid, right);
}

/**
 * 合并两个已排序的子数组
 * @param arr 数组
 * @param left 左
 * @param mid 中
 * @param right 右
 */
public static void merge(int[] arr, int[] temp, int left, int mid, int right) {
    // 将元素从 arr 拷贝到 temp
    for (int i = 0; i < arr.length; i++) {
        temp[i] = arr[i];
    }
    // 定义变量，跟踪左右数组，以及 arr
    int i = left, j = mid + 1,k = left;
    while (i <= mid && j <= right) {
        if (temp[i] <= temp[j]) {
            arr[k++] = temp[i++];
        }else {
            arr[k++] = temp[j++];
        }
    }
    //判断那个子数组中有剩余的数据
    int start = i;
    int end = mid;
    if (j<right) {
        start = j;
        end = right;
    }
    while (start <= end) {
        arr[k++] = temp[start++];
    }
}

• 归并排序稳不稳定主要看 merge 函数，在合并过程中，对于值相同的元素，原来的元素还放在考前的位置上，所以具有稳定性。
• 归并排序的时间复杂度是 $O(nog_n)$; 空间复杂度是 $O(n)$

快速排序

QuickSort 利用的也是分治思想。

如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。

遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的。中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

快排递推公式

递推公式
quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1...r)
终止条件
p>=r

快速排序

/**
 * 快速排序
 *
 * @param arr 待排序数组
 */
public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length-1);
}

/**
 * 快速排序
 * @param arr 待排序数组
 * @param l 左
 * @param r 右
 */
private static void quickSort(int[] arr, int l, int r) {
    if (l >= r) {
        return;
    }
    int q = partition(arr,l,r); // 获取分区点
    quickSort(arr,l,q-1);
    quickSort(arr,q+1,r);
}

/**
 * 分区函数，在 l 和 r 之间选取一个分区点 pivot ，将小于 pivot 的元素放在 pivot 左边，大于的放在右边。
 * 1. 定义一个变量追踪小于 pivot 的元素。
 * @param arr 待排序数组
 * @param l 左
 * @param r 右
 * @return 分区点索引
 */
private static int partition(int[] arr, int l, int r) {
        int pivot = arr[r];
        int i = l; // 追踪小于等于 pivot 的元素
        for (int j = l; j < r; j++) {
            if (arr[j] < pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        // 交换 i 和 pivot 的位置
        swap(arr, i, r);
        return i;
}

分区的处理有点类似选择排序，通过游标 i 把 A[p...r-1] 分成两部分 A[p...i-1] 的元素都是小于 pivot 的，叫做 “已处理区间”，A[i,r-1]是 “未处理区间” ，每次从未处理区间中取一个元素 A[j]，与 pivot 对比，如果小于 pivot ，则将其加入到已处理区间的尾部，也就是 A[i] 的位置。

因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6,8,7,6,3,5,9,4 , 在经过第一次分区操作后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。

快速排序和归并排序的区别

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排则正好相反，它的处理过程是由下到上的，先分区，然后再处理子问题。

归并排序虽然是稳定的、时间复杂度为 $O(nlog_n)$ 的排序算法，但是它是非原地排序算法。合并函数无法在原地执行。

快速排序通过巧妙地原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

快速排序最坏情况下的时间复杂度是 $O(n^2)$, 归并在最坏情况下时间复杂度还是 $O(nlog_n)$

两者最好情况的时间复杂度都是 $O(nlog_n)$。

快速排序的空间复杂度主要取决于递归调用栈的深度。最好、平均情况都是 $O(logn)$，最坏情况是 $O(n)$.

求无序数组中的第 k 大元素。

快排核心思想就是分治和分区，我们可以利用分区的思想，来解答 O(n) 时间复杂度内求无序数组中的第 K 大元素。比如，4， 2， 5， 12， 3 这样一组数据，第 3 大元素就是 4。

我们选择数组区间 A[0...n-1] 的最后一个元素 A[n-1] 作为 pivot ，对数组 A[0...n-1] 原地分区，这样数组就分成了三部分 ，A[0...p-1]、A[p]、A[p+1,n-1]

如果 p+1 = K,那么 A[p] 就是要求解的元素；如果 K >p,说明第 K 大元素出现在 A[p+1...n-1] 区间，再按照上面的思路递归地在 A[p+1...n-1] 这个区间查找。同理，如果 K<p, 那我们就在 A[0...p-1] 区间查找。

上述时间复杂度为 O(n)

/**
 * 求一个序列中的第 k 大元素
 *
 * @param arr  无序序列
 * @param k    第 k 大元素
 */
public static int findKthLargest(int[] arr, int k) {
    //调整 k, 因为索引从 0 ，开始，所以第 k 大元素其实是倒数第 k 个元素
    return quickSelect(arr, 0, arr.length - 1, arr.length - k);
}

private static int quickSelect(int[] arr, int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }
    int pivotIndex = partition(arr, left,right);
    if (k == pivotIndex) {
        return arr[k];
    } else if(k> pivotIndex){ // 继续在右半边查找
        return quickSelect(arr, pivotIndex + 1, right, k);
    }else{
        return quickSelect(arr, left, pivotIndex - 1, k);
    }
}
private static int partition(int[] arr, int left, int right) {
    // 选择最后一个元素作为 pivot
    int pivot = arr[right];
    int i = left; // 追踪小于等于 pivot 的元素
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            swap(arr,i,j);
            i++;
        }
    }
    swap(arr, i, right);
    return i;
}

private static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

public static void main(String[] args) {
    int[] arr = {6, 1, 3, 5, 7, 2, 4, 9, 11, 8};
    int kthLargest = findKthLargest(arr, 3);
    System.out.println("kthLargest = " + kthLargest);
}

堆和堆排序

堆（Heap）这种数据结构的应用场景非常多，最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为 $O(nlog_n)$ 的排序算法。

对于 n 个元素的关键字序列 $\{K_1,K_2,...,K_n\}$，当且仅当满足下列关系时称其为堆，其中 $2i$ 和 $2i+1$ 需不大于 n。

$$\begin{cases} K_i \leq K_{2i} \\ K_i \leq K_{2i+1}\\ \end{cases} \ \ \ or \ \ \ \begin{cases} K_i \geq K_{2i} \\ K_i \geq K_{2i+1}\\ \end{cases}$$

堆排序的基本思想是：对一组待排序记录的关键字，首先按堆的定义排成一个序列（即建立初始堆），从而得到可以输出堆顶的最大关键字（对于大根堆而言），然后将剩余的关键字再调整成新堆，便得到次大的关键字，如此反复，直到全部关键字排成有序序列为止。

初始堆的建立方法是：将待排序的关键字分放到一棵完全二叉树的各个节点上（此时完全二叉树并不一定具备堆的特性），显然，所有 $i > \lfloor \frac{n}{2} \rfloor$ 的节点 $K_i$ 都没有子节点，以这样的 $K_i$ 为根的子树已经是堆，因此初始建堆可从完全二叉树的第 $i = \lfloor \frac{n}{2} \rfloor$ 个节点 $K_i$ 开始，通过调整，逐步使得以 $K_{\lfloor \frac{n}{2} \rfloor }$、$K_{\lfloor \frac{n}{2} \rfloor-1}$、$K_{\lfloor \frac{n}{2} \rfloor-2}$、...、$K_2$、$K_1$ 为根的子树满足堆的定义。

为序列 (55,60,40,10,80,65,15,5,75) 建立大根堆的过程如下图所示。

首先将给出的数组按完全二叉树规则建立，而后，找到此完全二叉树的 最后一个非叶子节点（也即最后一课子树），比较 此非叶子节点和其两个孩子的大小，若小，则与其孩子节点中最大的节点进行交换；依据此规则再去找倒数第二个非叶子节点；这是只有一层的情况，当涉及多层次时又打破了之前的堆，因此，又要进行变换。（从上到下）

提示

初始堆是一个完全二叉树。大根堆是用来求最大值，小根堆用来求最小值。

建立初始堆之后，开始排序，每次取走堆顶元素（必然是最大的），而后将堆中最后一个元素移入堆顶，而后 按照初始建堆中的方法与其孩子节点比较大小，依次向下判断交换成为一个新的堆，再取走堆顶元素，重复此过程。

堆排序适用于在多个元素中找出前几名的方案设计，因为堆排序是选择排序，而且选择出前几名的效率很高。