排序

冒泡排序

基本思想

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

示例

初始状态：2, 3, 2, 5, 1
2 < 3, pass
3 > 2, 交换位置，变为2, 2, 3, 5, 1
3 < 5, pass
5 > 1, 交换位置，变为2, 2, 3, 1, 5

以上第一次排序之后，最大的数5会排到最后边。重复以上步骤，除了最后一个已经找出来的最大数。这样最大的数会依次像冒泡一样冒到后边。

假设有n个元素，则需要n-1次排序才能将数组排序完毕。

时间复杂度

n * (n-1) / 2 = O(n2)

代码

传送门

快速排序

基本思想

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

示例

一趟排序的过程

1. 初始状态：2(i), 3, 2, 5, 1(j) 关键字：2
2. 第一次交换：1(i), 3, 2, 5, 2(j)
3. 第二次交换：1, 2(i), 2, 5, 3(j)
4. 最终状态：1, 2(i,j), 2, 5, 3

排序的全过程

1. 初始状态：2, 3, 2, 5, 1 关键字：2
2. 一次排序后：(1), 2, (2, 5, 3)
3. 分别快速排序：(1), 2, (2), (5, 3) -> (1), 2, (2), (3, 5)
4. 有序序列：1, 2, 2, 3, 5

代码

传送门