排序

1. 冒泡排序（Bubble Sort）
2. 插入排序（Insertion Sort）
3. 归并排序（Merge Sort）
4. 快速排序（Quick Sort）
5. 拓扑排序（Topological Sort）
6. 堆排序（Heap Sort）
7. 桶排序（Bucket Sort)

冒泡排序

给定一个数组，我们把数组里的元素通通倒入到水池中，这些元素将通过相互之间的比较，按照大小顺序一个一个地像气泡一样浮出水面。每一轮，从杂乱无章的数组头部开始，每两个元素比较大小并进行交换，直到这一轮当中最大或最小的元素被放置在数组的尾部，然后不断地重复这个过程，直到所有元素都排好位置。其中，核心操作就是元素相互比较。

public class BubbleSort {
    public static void bubbleSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换位置
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = {7, 3, 22, 15, 8};
        bubbleSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

空间复杂度：假设数组的元素个数是 n，由于在整个排序的过程中，我们是直接在给定的数组里面进行元素的两两交换，所以空间复杂度是 O(1)。

时间复杂度：

• 给定的数组按照顺序已经排好：在这种情况下，我们只需要进行 n−1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。
• 给定的数组按照逆序排列：在这种情况下，我们需要进行 n(n-1)/2 次比较，时间复杂度是 O(n2)。这是最坏的情况。
• 给定的数组杂乱无章 在这种情况下，平均时间复杂度是 O(n2)。

由此可见，冒泡排序的时间复杂度是 O(n2)。它是一种稳定的排序算法。（稳定是指如果数组里两个相等的数，那么排序前后这两个相等的数的相对位置保持不变。

插入排序

不断地将尚未排好序的数插入到已经排好序的部分。在冒泡排序中，经过每一轮的排序处理后，数组后端的数是排好序的；而对于插入排序来说，经过每一轮的排序处理后，数组前端的数都是排好序的。

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int current = arr[i]; // 当前要插入的元素
            int j = i - 1; // 已排序区间的最后一个元素的索引

            // 将当前元素与已排序区间的元素逐一比较，找到合适的位置插入
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j]; // 向后移动元素
                j--;
            }
            arr[j + 1] = current; // 插入当前元素到正确的位置
        }
    }

    public static void main(String[] args) {
        int[] arr = {7, 3, 22, 15, 8};
        insertionSort(arr);
        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

归并排序

核心是分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。归并排序将分治的思想体现得淋漓尽致。

**实现：**一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。 排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。

代码如下：

public class MergeSort {
    public static void mergeSort(int[] arr, int low, int high, int[] tmp) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(arr, low, mid, tmp); // 对左边序列进行归并排序
            mergeSort(arr, mid + 1, high, tmp); // 对右边序列进行归并排序
            merge(arr, low, mid, high, tmp); // 合并两个有序序列
        }
    }

    public static void merge(int[] arr, int low, int mid, int high, int[] tmp) {
        int i = 0;
        int j = low;
        int k = mid + 1; // 右边序列起始索引
        while (j <= mid && k <= high) {
            if (arr[j] < arr[k]) {
                tmp[i++] = arr[j++];
            } else {
                tmp[i++] = arr[k++];
            }
        }
        while (j <= mid) {
            tmp[i++] = arr[j++];
        }
        while (k <= high) {
            tmp[i++] = arr[k++];
        }
        for (int t = 0; t < i; t++) {
            arr[low + t] = tmp[t];
        }
    }

    public static void main(String[] args) {
        int[] arr = {11, 44, 23, 67, 88, 65, 34, 48, 9, 12};
        int[] tmp = new int[arr.length

空间复杂度
由于合并 n 个元素需要分配一个大小为 n 的额外数组，合并完成之后，这个数组的空间就会被释放，所以算法的空间复杂度就是 O(n)。归并排序也是稳定的排序算法。

时间复杂度
归并算法是一个不断递归的过程。
举例：数组的元素个数是 n，时间复杂度是 T(n) 的函数。
解法：把这个规模为 n 的问题分成两个规模分别为 n/2 的子问题，每个子问题的时间复杂度就是 T(n/2)，那么两个子问题的复杂度就是 2×T(n/2)。当两个子问题都得到了解决，即两个子数组都排好了序，需要将它们合并，一共有 n 个元素，每次都要进行最多 n-1 次的比较，所以合并的复杂度是 O(n)。由此我们得到了递归复杂度公式：T(n) = 2×T(n/2) + O(n)。

对于公式求解，不断地把一个规模为 n 的问题分解成规模为 n/2 的问题，一直分解到规模大小为 1。如果 n 等于 2，只需要分一次；如果 n 等于 4，需要分 2 次。这里的次数是按照规模大小的变化分类的。

以此类推，对于规模为 n 的问题，一共要进行 log(n) 层的大小切分。在每一层里，我们都要进行合并，所涉及到的元素其实就是数组里的所有元素，因此，每一层的合并复杂度都是 O(n)，所以整体的复杂度就是 O(nlogn)。

建议：归并算法的思想很重要，其中对两个有序数组合并的操作，在很多面试题里都有用到，建议大家一定要把这个算法练熟。

快速排序

快速排序也采用了分治的思想。把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。

1. 按照快速排序的思想，首先把数组筛选成较小和较大的两个子数组。
2. 随机从数组里选取一个数作为基准值，比如 7，于是原始的数组就被分成了两个子数组。注意：快速排序是直接在原始数组里进行各种交换操作，所以当子数组被分割出来的时候，原始数组里的排列也被改变了。
3. 接下来，在较小的子数组里选 2 作为基准值，在较大的子数组里选 8 作为基准值，继续分割子数组。
4. 继续将元素个数大于 1 的子数组进行划分，当所有子数组里的元素个数都为 1 的时候，原始数组也被排好序了。

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = low - 1; // i 是小于基准的元素的索引
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high); // 将基准元素放到正确的位置
        return i + 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {7, 3, 22, 15, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

时间复杂度

1. 最优情况：被选出来的基准值都是当前子数组的中间数。
   这样的分割，能保证对于一个规模大小为 n 的问题，能被均匀分解成两个规模大小为 n/2 的子问题（归并排序也采用了相同的划分方法），时间复杂度就是：T(n) = 2×T(n/2) + O(n)。
   把规模大小为 n 的问题分解成 n/2 的两个子问题时，和基准值进行了 n-1 次比较，复杂度就是 O(n)。很显然，在最优情况下，快速排序的复杂度也是 O(nlogn)。
2. 最坏情况：基准值选择了子数组里的最大或者最小值
   每次都把子数组分成了两个更小的子数组，其中一个的长度为 1，另外一个的长度只比原子数组少 1。
   举例：对于数组来说，每次挑选的基准值分别是 9、8、7、5、2。
   解法：划分过程和冒泡排序的过程类似。
   算法复杂度为 O(n2)。
   提示：可以通过随机地选取基准值来避免出现最坏的情况。

空间复杂度
和归并排序不同，快速排序在每次递归的过程中，只需要开辟 O(1) 的存储空间来完成交换操作实现直接对数组的修改，又因为递归次数为 logn，所以它的整体空间复杂度完全取决于压堆栈的次数，因此它的空间复杂度是 O(logn)。

拓扑排序

和前面介绍的几种排序不同，拓扑排序应用的场合不再是一个简单的数组，而是研究图论里面顶点和顶点连线之间的性质。拓扑排序就是要将这些顶点按照相连的性质进行排序。
要能实现拓扑排序，得有几个前提：

• 图必须是有向图

• 图里面没有环

拓扑排序一般用来理清具有依赖关系的任务。
举例：假设有三门课程 A、B、C，如果想要学习课程 C 就必须先把课程 B 学完，要学习课程 B，还得先学习课程 A，所以得出课程的学习顺序应该是 A -> B -> C。

例题分析
有一个学生想要修完 5 门课程的学分，这 5 门课程分别用 1、2、3、4、5 来表示，现在已知学习这些课程有如下的要求：

• 课程 2 和 4 依赖于课程 1

• 课程 3 依赖于课程 2 和 4

• 课程 4 依赖于课程 1 和 2

• 课程 5 依赖于课程 3 和 4

那么这个学生应该按照怎样的顺序来学习这 5 门课程呢？

解题思路
可以把 5 门课程看成是一个图里的 5 个顶点，用有向线段按照它们的相互关系连起来，于是得出下面的有向图。
首先可以看到，这个有向图里没有环，无论从哪个顶点出发，都不会再回到那个顶点。并且，这个图里并没有孤岛的出现，因此，我们可以对它进行拓扑排序。
方法就是，一开始的时候，对每个顶点统计它们各自的前驱（也就是入度）：1(0)，2(1)，3(2)，4(2)，5(2)。

选择其中一个没有前驱（也就是入度为 0）的顶点，在这道题里面，顶点 1 就是我们要找的那个点，将它作为结果输出。同时删除掉该顶点和所有以它作为起始点的有向边，更新顶点的入度表。
接下来，顶点 2 就是下一个没有前驱的顶点，输出顶点 2，并将以它作为起点的有向边删除，同时更新入度表。
再来，顶点 4 成为了没有前驱的顶点，输出顶点 4，删除掉它和顶点 3 和 5 的有向边。
然后，顶点 3 没有了前驱，输出它，并删除它与 5 的有向边。
最后，顶点 5 没有前驱，输出它，于是得出最后的结果为：1，2，4，3，5。

一般来说，一个有向无环图可以有一个或多个拓扑排序的序列。

代码示例：

void sort() {
    Queue<Integer> q = new LinkedList(); // 定义一个队列 q
    //将所有入度为0的顶点加入到队列q
for(intv=0;v&lt;V;v++){
if(indegree[v]==0)q.add(v);
}

//循环，直到队列为空
while(!q.isEmpty()){
intv=q.poll();
//每次循环中，从队列中取出顶点，即为按照入度数目排序中最小的那个顶点
print(v);

//将跟这个顶点相连的其他顶点的入度减1，如果发现那个顶点的入度变成了0，将其加入到队列的末尾
for(intu=0;u&lt;adj[v].length;u++){
if(--indegree[u]==0){
q.add(u);
}
}
}
}