浅谈排序算法

1，了解排序算法

算法目的：

①，输入：一组无序的n个数值；②，输出：有序列的n数值

算法优劣通过什么评判：

①，稳定: 如果a=b，a在b前面，排序完成后，a仍在b前面

②，不稳定：如果a=b，a在b前面，排序完成后，a跑到了b后面

③，内排序：所有排序操作都在内存中完成

④，外排序：如果数据太大，会把数据放在磁盘中，通过磁盘和内存的数据传输才能进行排序

⑤，时间复杂度: 一个算法执行所耗费的时间

⑥，空间复杂度: 运行完一个程序所需内存的大小

2，罗列八种排序方法思路

冒泡排序：

①，比较相邻的元素。如果第一个比第二个大，就交换它们两个的位置

②，对每一对相邻元素作都这样比较，一轮下来最大数就排到了最后的位置

③，因为一轮比较只能确定一个最大数，所以要进行多轮比较（不要再次比较已经确定大小的数值），直到排序完成

选择排序：

①，假定第一个数为最小的数，然后依次与后面的数进行比较

②，如果找到比它小的，那么就假定新找到的这个数最小

③，重复1,2步至找到数列中最小的数，然后把它和最起始位置的数调换位置

④，一轮下来只能找到一个最小的数，所以要找多轮（因为每一轮都能确定一个最小的数，所以每下一轮都要忽略这些已经确认的数值，从下一个位置开始作为起点）一直到排序完成

插入排序：

①，从起始第一个数值开始，认定该数值为最小，且已经被排序了

②，.取出下一个数值，在已经排序的数值序列中从后向前比较

③，如果取出的那个数值比较小，就将比较大的元素移到下一位置，一直找到比取出的数值还要小或者一般大的那个数值，将取出的数值插入其后面

④，当取出最后一个数值，并插入完毕后，排序完成

快速排序：

①，从数列中挑出一个数值，称为 "基准"

②，剩余的数值都要和基准比较，所有数值比基准值小的摆放在基准前面，所有数值比基准值大的摆在基准的后面（相同的数可以到任一边），这时基准的位置就已经排好了，而且把数列分成了两个区域。分区之间的数值互不比较，因为前面区域的数值一定比基准后面小。

③，分区里面的数值继续重复1,2步，直到排序完成。

堆排序：

①，堆排序可以用完全二叉树的形式展示出来，我们以排序最大堆为例

②，首先我么从最底层开始比较大小，由于最底层最少有一组分支，所以我们要已每一组分支为单位分别比较大小

③，每组分支比较大的那个成员，我们需要把它与它的父级进行比较，如果大于，就与父级交换位置。

④，第一层比完了，比第二层，重复第3步，一直到堆顶。

⑤，那么好，整个数据结构中最大的那个成员就找到了。

⑥，我们知道，完全二叉树可以用数组的方式展示，因为我们要从小到大排序，所以呢，上面步骤结束后堆顶的那个成员就要把它放到数组的最后面，也就是完全二叉树的最下层的最右枝丫上，所以首位与末位交换位置，末位就固定下来了。

⑦，进行第二轮比较，在比较之前我们需要忽略掉最末位的那个成员了，因为它最大，所以他的位置固定了，就不带它玩了，

那么好，重复步骤2~6，直到二叉树消失，排序完成

计数排序：

①，现在有一个数组a，和一个空数组b

②，首先将数组a的成员依次放入到数组b中，

③，在这个过程中数组a的成员在这个数组b中以下标形式呈现，相对应的键值则代表成员进入的次数

④，当所有成员导入完毕，大小的顺序就已经排好了

⑤，最后将把它们按顺序导出（如果有多次进入数组b的成员，要全部导出，直到键值为0），即排序完毕

桶排序：

①，现有一个数组a，数组a中有n个数组（桶），每个桶都设置好对应的数据范围

②，遍历需要排序的数据，并且把数据一个一个放到对应范围的桶里去

③，对每个不是空的桶进行排序（可用其他排序方法）

④，从不是空的桶里把排好序的数据拼接起来，排序完毕

基数排序：

①，现有一个数组b，数组b中有十个对象作为桶

②，遍历需要进行排序的数据，从每个数值的“最低位开始”对号入桶（数字跑不出0-9的范围，对号如桶就是数组b对应下标的桶）

③，按照数组b下标的顺序放出桶中的数据（这个过程中，桶中数据要按照队列顺序依次出来）

④，最低位排完就排上一位，一直到最高位。