排序算法

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

图示

不稳定的排序算法:

简单选择排序、快速排序、希尔排序、堆排序

稳定的排序算法

冒泡排序、直接插入排序、归并排序、基数排序

时间复杂度

冒泡排序:O(n^2)
简单选择排序:O(n^2)
直接插入排序:O(n^2)
快速排序是不稳定的。最理想情况算法时间复杂度O(nlogn)，最坏O(n^2)。
堆排序:O(nlogn)
归并排序:是O(nlogn)
希尔排序:O(n^1.25)
基数排序:O(d(rd+n))

各排序算法的简单描述

• 冒泡排序:从无序区通过交换找出最大元素放到有序区前端。
• 简单选择排序:在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少。
• 直接插入排序:把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。
• 堆排序:从堆顶把根卸出来放在有序区之前，再恢复堆。
• 归并排序:把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。
• 快速排序:在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。
• 桶排序:将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
• 基数排序:一种多关键字的排序算法，可用桶排序实现。