- 这里的X是排序算法的名称;
- 我们将所有待排数字放在一个数组
A[]
中;
- 大多数情况下,为简单起见,讨论从小到大的排序;
- N是正整数;
- 只讨论基于比较的排序(> = < 都有定义)
- 只讨论内部排序(假设内存空间足够大,所有数据都可以被一次导入到内存中进行排序)
- 稳定性:任意两个相等的数据,排序前后的相对位置不发生改变。 e.g.:假设有两个数据:小明1和小明2,排序前小明1在小明2前面,如果排序后小明1仍在小明2前面,那么这个算法是稳定的。
- 没有一种排序是在任何情况下都表现最好的!根据具体情况选择合适的算法
简单排序Bubble_SortInsertion_Sort时间复杂度下界Selection_Sort
希尔排序:简单插入排序PLUSShell_Sort
堆排序:简单选择排序PLUSHeap_Sort
归并排序:递归和非递归Merge_Sort
不同排序算法对比表排序快速排序:“传说中最快的排序算法”Quick_Sort