实现
每一轮，从数组头部开始，每两个元素比较大小并进行交换，直到这一轮当中最大或最小的元素被放置在数组的尾部，然后不断地重复这个过程，直到所有元素都排好位置。其中，核心操作就是元素相互比较。
例题
给定数组 [2, 1, 7, 9, 5, 8]，要求按照从左到右、从小到大的顺序进行排序。
从左到右依次冒泡，把较大的数往右边挪动即可。
-
首先指针指向第一个数，比较第一个数和第二个数的大小，由于 2 比 1 大，所以两两交换，[1, 2, 7, 9, 5, 8]。
-
接下来指针往前移动一步，比较 2 和 7，由于 2 比 7 小，两者保持不动，[1, 2, 7, 9, 5, 8]。到目前为止，7 是最大的那个数。
-
指针继续往前移动，比较 7 和 9，由于 7 比 9 小，两者保持不动，[1, 2, 7, 9, 5, 8]。现在，9 变成了最大的那个数。
-
再往后，比较 9 和 5，很明显，9 比 5 大，交换它们的位置，[1, 2, 7, 5, 9, 8]。
-
最后，比较 9 和 8，9 比 8 大，交换它们的位置，[1, 2, 7, 5, 8, 9]。经过第一轮的两两比较，9 这个最大的数就像冒泡一样冒到了数组的最后面。
接下来进行第二轮的比较，把指针重新指向第一个元素，重复上面的操作，最后，数组变成了：[1, 2, 5, 7, 8, 9]。
在进行新一轮的比较中，判断一下在上一轮比较的过程中有没有发生两两交换，如果一次交换都没有发生，就证明其实数组已经排好序了。
代码示例
void sort(int[] nums) { //定义一个布尔变量 hasChange，用来标记每轮遍历中是否发生了交换 boolean hasChange = true; //每轮遍历开始，将 hasChange 设置为 false for (int i = 0; i < nums.length - 1 && hasChange; i++) { hasChange = false; //进行两两比较，如果发现当前的数比下一个数还大，那么就交换这两个数，同时记录一下有交换发生 for (int j = 0; j < nums.length - 1 - i; j++) { if (nums[j] > nums[j + 1]) { swap(nums, j, j + 1); hasChange = true; } } } }
空间复杂度
假设数组的元素个数是 n，由于在整个排序的过程中，我们是直接在给定的数组里面进行元素的两两交换，所以空间复杂度是 O(1)。
时间复杂度
-
给定的数组按照顺序已经排好
在这种情况下，我们只需要进行 n−1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。
-
给定的数组按照逆序排列
在这种情况下，我们需要进行 n(n-1)/2 次比较，时间复杂度是 O(n2)。这是最坏的情况。
-
给定的数组杂乱无章
在这种情况下，平均时间复杂度是 O(n2)。
由此可见，冒泡排序的时间复杂度是 O(n2)。它是一种稳定的排序算法。（稳定是指如果数组里两个相等的数，那么排序前后这两个相等的数的相对位置保持不变。）
归并排序（Merge Sort）
实现
核心是分治，一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。
排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。
代码示例
void sort(int[] A, int lo, int hi) { // 判断是否只剩下最后一个元素 if (lo >= hi) return; // 从中间将数组分成两个部分 int mid = lo + (hi - lo) / 2; // 分别递归地将左右两半排好序 sort(A, lo, mid); sort(A, mid + 1, hi); // 将排好序的左右两半合并 merge(A, lo, mid, hi); } void merge(int[] nums, int lo, int mid, int hi) { // 复制一份原来的数组 int[] copy = nums.clone(); // 定义一个 k 指针表示从什么位置开始修改原来的数组，i 指针表示左半边的起始位置，j 表示右半边的起始位置 int k = lo, i = lo, j = mid + 1; while (k <= hi) { if (i > mid) { nums[k++] = copy[j++]; } else if (j > hi) { nums[k++] = copy[i++]; } else if (copy[j] < copy[i]) { nums[k++] = copy[j++]; } else { nums[k++] = copy[i++]; } } }
例题
利用归并排序算法对数组 [2, 1, 7, 9, 5, 8] 进行排序。
首先不断地对数组进行切分，直到各个子数组里只包含一个元素。
接下来递归地按照大小顺序合并切分开的子数组，递归的顺序和二叉树里的前向遍历类似。
-
合并 [2] 和 [1] 为 [1, 2]。
-
子数组 [1, 2] 和 [7] 合并。
-
右边，合并 [9] 和 [5]。
-
然后合并 [5, 9] 和 [8]。
-
最后合并 [1, 2, 7] 和 [5, 8, 9] 成 [1, 2, 5, 8, 9]，就可以把整个数组排好序了。
合并数组 [1, 2, 7] 和 [5, 8, 9] 的操作步骤如下。
-
把数组 [1, 2, 7] 用 L 表示，[5, 8, 9] 用 R 表示。
-
合并的时候，开辟分配一个新数组 T 保存结果，数组大小应该是两个子数组长度的总和
-
然后下标 i、j、k 分别指向每个数组的起始点。
-
接下来，比较下标i和j所指向的元素 L[i] 和 R[j]，按照大小顺序放入到下标 k 指向的地方，1 小于 5。
-
移动 i 和 k，继续比较 L[i] 和 R[j]，2 比 5 小。
-
i 和 k 继续往前移动，5 比 7 小。
-
移动 j 和 k，继续比较 L[i] 和 R[j]，7 比 8 小。
这时候，左边的数组已经处理完毕，直接将右边数组剩余的元素放到结果数组里就好。
合并之所以能成功，先决条件必须是两个子数组都已经分别排好序了。
空间复杂度
由于合并 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)。
快速排序（Quick Sort）
实现
快速排序也采用了分治的思想，首先选定一个基准值（基准值的选择尤为关键），然后把原始数组分为两个子数组，一个是小于基准元素的子数组，另一个是大于基准元素的子数组。
例题
对数组 [2, 1, 7, 9, 5, 8] 进行排序
-
选定基准元素为7
-
将数组中小于7的元素形成一个较小子数组，将大于7的元素形成一个较大子数组。注意：快速排序是直接在原始数组里进行各种交换操作，所以当子数组被分割出来的时候，原始数组里的排列也被改变了。
-
然后接着在较小的子数组里选 2 作为基准值，在较大的子数组里选 8 作为基准值，继续分割子数组。
-
继续将元素个数大于 1 的子数组进行划分，当所有子数组里的元素个数都为 1 的时候，原始数组也被排好序了。
代码示例
void sort(int[] nums, int lo, int hi) { if (lo >= hi) return; // 判断是否只剩下一个元素，是，则直接返回 // 利用 partition 函数找到一个随机的基准点 int p = partition(nums, lo, hi); // 递归地对基准点左半边和右半边的数进行排序 sort(nums, lo, p - 1); sort(nums, p + 1, hi); } int partition(int[] nums, int lo, int hi) { // 随机选择一个数作为基准值，nums[hi] 就是基准值 swap(nums, randRange(lo, hi), hi); int i, j; // 从左到右用每个数和基准值比较，若比基准值小，则放到指针 i 所指向的位置。循环完毕后，i 指针之前的数都比基准值小 for (i = lo, j = lo; j < hi; j++) { if (nums[j] <= nums[hi]) { swap(nums, i++, j); } } // 末尾的基准值放置到指针 i 的位置，i 指针之后的数都比基准值大 swap(nums, i, j); // 返回指针 i，作为基准点的位置 return i; }
时间复杂度
最优情况：被选出来的基准值都是当前子数组的中间数。
这样的分割，能保证对于一个规模大小为 n 的问题，能被均匀分解成两个规模大小为 n/2 的子问题（归并排序也采用了相同的划分方法），时间复杂度就是：T(n) = 2×T(n/2) + O(n)。
把规模大小为 n 的问题分解成 n/2 的两个子问题时，和基准值进行了 n-1 次比较，复杂度就是 O(n)。很显然，在最优情况下，快速排序的复杂度也是 O(nlogn)。
最坏情况：基准值选择了子数组里的最大或者最小值
每次都把子数组分成了两个更小的子数组，其中一个的长度为 1，另外一个的长度只比原子数组少 1。
算法复杂度为 O(n2)。
提示：可以通过随机地选取基准值来避免出现最坏的情况。
空间复杂度