|
交换排序的基本思想两两比较待排序记录的关键字发现两个记录的次序相反时即进行交换直到没有反序的记录为止 冒泡排序 冒泡排序将当前未排序的记录自上而下依次对相邻的两个记录进行比较若为逆序则将两个结点交换即大者下沉小者上冒将序列照此方法从头到尾处理一遍称做一趟冒泡排序这一趟冒泡排序的效果是将最大的记录下沉到最终位置若某一趟排序过程没有任何记录交换发生则排序过程结束 冒泡排序算法 若文件的初始状态是正序的冒泡排序最好的时间复杂度为O(n)若初始文件是反序的冒泡排序的最坏时间复杂度为O(n)算法的平均时间复杂度为O(n) 冒泡排序是就地排序且是稳定的 |
