四种排序

对于无序数组的排序，方法有许多，这里可以以数组{12，23，8，15，33，24，77，55}先说四种。

1.选择排序

顾名思义，选择排序流程如下

1. 选择一个最小（或最大）的数，然后将其排在最前端（或最后端）；
2. 固定住被排列的数并锁住位置；
3. 从未被排列的数中选择最小（或最大）的数，将其排在未被锁住位置的最前端（或最后端）；
4. 若此时未被排列的数不止一个，重复步骤2，3，否则排序完成。

这里个人手动走了一下。

 时间复杂度是O(n²).

2.冒泡排序

冒泡排序流程如下：

1. 从数列左端（或右端）开始依次选择相邻的两个数，将较小（大）的放入前面（后面）
2. 当依次选择并排列至数列的右端（或左端）时，固定数列最右端（或最左端）的数并锁住位置
3. 从数列左端（或右端）开始依次选择相邻的两个数，将较小（大）的放入前面（后面）
4. 当依次选择并排列至数列的最后一个未被锁住位置时，固定数列最右端（或最左端）的数并锁住位置
5. 重复步骤3、4，直到仅剩一个数，排列完成。

这里也手动走了一下。

 数组中的元素一个一个向一侧移动排列，像气泡一个一个冒出水面，这也是它叫冒泡排序的原因。

时间复杂度是O(n²).

3.插入排序

插入排序流程如下：

1. 选择数组最前方（或最后方）的数，将该位置置于半处理状态。
2. 选择数组中未处于半处理的位置中最前方（或最后方）的数，将该数与待处理状态位置的所有数据进行排序，并将该位置置于半处理状态
3. 重复步骤2，直到所有位置均处于半处理状态。

算法比较好理解，名字也是符合操作方法。

 时间复杂度是O(n²).

4.快速排序

这算是比较重要的一种排序了，该排序的时间复杂度较低，算法理解需要一定时间。流程如下：

1. 选择待排序数组左侧（或右侧）的第一个数作为基准。
2. 先从右（或从左）寻找一个比基准数小（或大）的数。如果找到该数，将该数的位置记为j；若未找到，将基准数的位置记为j
3. 再从左（或从右）寻找一个比基准数大（或小）的数。如果找到该数，将该数的位置记为i；若与j相遇，将相遇的数的位置记为i
4. 若j和i的位置不同，交换j与i位置的数值，否则将基准数与j与i相遇位置的数进行交换。
5. 若基准数被交换，则进入下一步，否则重复步骤3、4，直到基准数被交换
6. 将基准数作为一个分界点固定住，将所有分界点（不含分界点）之间以及分界点（不含分界点）与数组边界之间的元素分别视为待排序数组。
7. 重复上述步骤，直到所有待排序数组中仅有一个元素。

有一个特别特别需要注意的地方：

• 若选择左侧的数作为基准，则需要先从右边寻找；若选择右侧的数作为基准，则需要先从左边寻找。

这个好像不太好理解。先挂出手动快速排序吧。

 在第一周循环中，我们选择12作为基准后，12被排到了2号位置。

我们注意到12左侧都不比12大，右侧都不比12小，那么12便被排好了顺序。

12左侧都不比12大，12右侧都不比12小，那么两侧都排好序之后，整个数组也自然被排好了序。

重复上述循环操作后，大数组被分为若干个只有1个元素的小数组，自然排好了序。

时间复杂度不好输入，在上述手稿的最后一行中。通常快速排序比前三种排序要快。