·冒泡排序

冒泡排序的思想

冒泡排序的思想是每次将最大的一下一下运到最右边，然后将最右边这个确定下来。再来确定第二大的，再确定第三大的...
对于数组 a [ ] ,具体的来说，每次确定操作就是从左往右扫描，如果 a [ i ] > a [ i + 1] ,我们就执行swap ( a [ i ] , a [ i + 1 ] ) 将两项交换，然后再往右检查，这样可以找出最大的并将其丢到最右边。

第一次确定操作是将a [ 1 ] ~ a [ n ] 中最大的放到 a [ n ] ;

第二次确定操作是将 a [ 1 ] ~ a [ n - 1 ] 中最大的放到 a [ n - 1 ] 。
依此类推（类似地，如果你想先把最小的放到左边也是可以的），时间复杂度为 O ( n ^ 2 )

由于排序过程中，数字像冒泡泡一样从左往右换过去，故名冒泡排序。

冒泡排序的实现

冒泡排序一般用双重循环来实现。在这里i表示每次操作的右边界，也是存放当前操作最大值的位置。虽然j的范围是到 i - 1 ,实际上 j + 1 会到 i ,所以可以使得操作是正确的。

例题讲解

用冒泡排序解决：

·选择排序

选择排序的思想

选择排序的思想和冒泡排序类似，是每次找出最大的然后直接放到右边对应位置，然后将最右边这个确定下来（而不是一个一个地交换过去）。再来确定第二大的，再确定第三大的...
对于数组 a [ ] ,具体的来说，每次确定操作（假设当前要确定的是 i 位置）就是从左往右扫描，计算出最大元素的下标 max_id ,最后执行一次 swap ( a [ max_id ] , a [ i] ) 将两项交换即可。第一次确定操作是将a [ 1 ] ~ a [ n ] 中最大的放到 a [ n ] ;
第二次确定操作是将 a [1] ~ a [ n - 1 ] 中最大的放到 a [ n - 1 ] 。
依此类推（类似地，如果你想先把最小的放到左边也是可以的），时间复杂度为O(n^2)。

选择排序的实现

选择排序一般用双重循环来实现。max_id 表示最大元素的下标。这里要注意的细节是 j 的范围是[1，i ] ，而在冒泡排序中j的范围是 [ 1，i - 1 ]。

例题讲解

用选择排序解决：

·插入排序

插入排序的思想

插入排序是一种简单直观的排序算法，其基本思想是将待排序的元素逐个插入到已排序序列的合适位置中，使得已排序序列逐渐扩大，从而逐步构建有序序列，最终得到完全有序的序列。
它类似于我们打扑克牌时的排序方式，将一张张牌插入到已经有序的手牌中。时间复杂度为O(n^2)。

插入排序的实现

插入排序一般用双重循环来实现。初始时我们认为长度为1的数组a [ 1 ] 是有序的（显然），然后将 a [ 2 ] 插入到合适的位置，使得 a [ 1 ~ 2 ] 有序，然后将 a [ 3 ] 插入，使得 a [ 1 ~ 3 ] 有序...直至a[1~n]有序。

例题讲解

用选择排序解决：

·快速排序

快速排序而的思想

快速排序是一种基于分治法的排序方法，原理是将一个数组分成两个子数组，其中一个子数组的所有元素都小于另一个子数组的元素，然后递归地对这两个子数组进行排序。
快速排序的思想是通过不断地将数组分成两个子数组，递归地对子数组进行排序，最终得到
一个有序的数组。这个过程通过选择合适的基准和分区操作来实现。
快速排序拥有更好的时间复杂度O(nlogn),且不需要额外空间。

快速排序的实现

这是快速排序的递归主体 QuickSort()。传入参数为要排序的数组和区间的左右端点。
 Partition函数会将数组 a [ l ] ~ a [ r ] 这个区间中某个基准数字放到正确的位置并将这个位置返回。
在确定了 mid 的位置之后，可以保证 a [ l ] ~ a [ mid-1]都< a [mid] < a [mid+1] ~ a[r],于是只需要将左右两边分别向下递归地排序即可。

这是Partition函数（分区函数），用于将比pivot小的放到左边，大的放到右边，最后返回pivot所处的位置。

例题讲解

用快速排序解决，前面讲过的几种排序方法的时间复杂度都是O(n^2),所以只能解决规模在1e3左右的问题，快速排序拥有较好的时间复杂度O(nlogn),所以可以解决更大规模的问题（约1e5)。

代码如下：

·归并排序

归并排序的思想

归并排序和快速排序类似，也是一种基于分治法的排序方法。
原理是将一个数组分成两个子数组，将子数组向下递归的排序后（当数组中仅有一个元素值无需再排序了，直接返回)，得到两个有序数组，然后进行O(n)的合并，最终合并成有序的原数组。
快速排序拥有较好的时间复杂度O(nlogn),但需要额外的空间用于合并数组。

归并排序的实现

这是归并排序的递归主体MergeSort()。传入参数为要排序的数组和区间的左右端点。
递归出口：当区间大小为1时，直接返回即可。
在确定了mid的位置之后，可以保证 a [ l ] ~ a [ mid ] 和 a [ mid + 1 ] ~ a [ r ] 都是有序的，于是只需要扫一遍将两个有序数组合并即可。
合并过程需要分类考虑一下，其中 pl 表示左半边的下标，pr 表示右半边的下标，pb 表示临时存放的数组的下标。

合并完成后要将b复制回a。

例题讲解

用归并排序解决：

代码如下：