排序算法

1. 介绍

　　排序算法是将一串数据按照某种特定排序方式（规则）进行排序的算法。分为内部排序和外部排序。

　　内部排序：指排序数据存储在内存中，依照依照某种排序方式（规则）进行排序。内部排序不适合太大的数据。内部排序的八中排序算法：冒泡排序、选择排序、插入排序、希尔排序、堆排序、归并排序、快速排序、基数排序。排序算法输出必须遵寻以下原则：

1. 输出结果为递增序列（递增是针对所需的排序顺序而言）
2. 输出结果是原输入的一种排列、或是重组

　　外部排序是指大文件的排序，即待排序的数据存储在外部存储器中（硬盘），待排序的文件无法一次写入内存中，需要在内存和外部存储器之间进行一次或者多次的数据交互，以完成整个文件的排序。

2. 分析

• 冒泡排序 -- 时间复杂度 ：O(n²)

　　　　

冒泡排序算法示意图 Bubble sort animation sort-0.1　　　

　　　冒泡排序算法的运作如下：

1. 1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
   2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
   3. 针对所有的元素重复以上的步骤，除了最后一个。
   4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

• 选择排序 -- 时间复杂度 ：O(n²)

　　

选择排序算法示意图 Bubble sort animation sort-0.2　　　　

　　　　选择排序算法的运作如下：　　

1. 1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
   2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
   3. 以此类推，直到所有元素均排序完毕

插入排序 -- 时间复杂度 ：O(n²)

希尔排序 -- 时间复杂度 ：O(n^1.25)

堆排序 -- 时间复杂度 ：O(n log n)

归并排序 -- 时间复杂度 ：O(n log n)

快速排序 -- 时间复杂度 ：O(n log n)

基数排序 -- 时间复杂度 ：O(n)