编程入门教程第十章 排序 - 图文

排序的另一种分类选择排序：

–简单选择、树形选择、堆排序

交换排序：

–起泡排序、快速排序

插入排序：

–简单插入、折半插入、表插入、希尔排序

归并排序基数排序

ypb@ustc.edu.cn29中国科学技术大学各种排序的综合比较表算法

平均时间

最坏情况

最好情况

辅助空间

稳定性

有序性影响

选择O(n2)O(n2)O(n2)O(1)Y无

插入O(n2)起泡O(n2)

O(n2)O(n2)

O(n)O(n)

O(1)O(1)

YY

好好

快速O(nLogn)O(n2)O(nLogn)O(Logn)NYNY

坏无无无

归并O(nLogn)O(nLogn)O(nLogn)O(n)堆

O(nLogn)O(nLogn)O(nLogn)O(1)

O(n*d)

O(n*d)

O(n)

基数O(n*d)

ypb@ustc.edu.cn30中国科学技术大学