# 「初学笔记」排序算法

# 冒泡排序

每次遍历列表，都得到一个最大的数，这就是冒泡。

冒泡排序算法的主要时间消耗是比较次数。
当i = 1时，比较次数为N - 1；
当i = 2时，比较次数为N - 1；
以此类推。
总共比较次数为(N - 1) + (N - 2) + ... + 2 + 1  = N(N - 1)/2
故冒泡排序算法的时间复杂度为 O(N^{2})。

# 插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

​ 在最理想的情况下（列表已排好序状态），while循环仅仅需要一次比较，故总运行时间为线性；
在最差的情况下（列表为逆序状态），此时内循环指令循环次数为：1+2+...+N-1=N(N-1)/2，
故插入排序算法的时间复杂度为 O(N^{2})。

# 归并排序

将一个列表对半分成左右两个子列表，再分别对左右子列表继续对半分，不断对半分，直到分成左右子列表各一个元素时结束，这时每个子列表都是有序的（一个元素当然有序），再对左右两个有序列表合并成一个有序的列表。这是一个递归过程。

​对于长度为N的列表，归并排序算法将列表分开成子列表一共要步。
每步都是合并有序列表的过程，时间复杂度可以记为 O(log_{2}N)。故归并排序算法的时间复杂度为。其效率是比较高的。

# 快速排序

不断对一组数据进行左右数据分割，使左边的数据全部小于右边的数据。

​快速排序最坏情况下，每次划分选区的基准都是当前无序列表中关键字最小（最大）的记录，时间复杂度为 O(N^{2})。
平均情况下，其时间复杂度为 O(Nlog_{2}N)。

​