描述:交换排序图解中最简单的排序方法
生活例子:水中的气泡,体积大的先浮上来
基本思想:前无序后有序,从头相邻比较不断挤压向后冒泡。
排序过程:①整個待排序区分为无序区和有序区初始有序区为空,无序区包括所有
排序过程:①整个待排序区分为无序区和有序区初始有序区为空,无序区包括所有
复杂度分析:最好的情况下,在一个循环内为正序只需执行一佽,比较了 n-1次时间复杂度为 O(n)。
②快速排序(分区交换排序图解)
描述:对起泡排序的改进记录比较和移动向两端进行,关键码较大的移到後面反之。
过程:①初始化选第一个作为轴值,并将ij分别指向最左右侧位置
②右侧扫描,将轴值记录与j 指向的记录进行比较如果 j 指向的大,则 j--重复扫描,直到j(右侧)记录小将轴值记录与 j位置记录交换,i++
③左侧扫面轴值与i 位置比较,i小则 i++,重复左侧扫描直到 i大,將轴值与 i 位置记录交换j--。
④重复②③直到ij相同。
复杂度分析:最好的情况下每次划分对一个记录定位后,该记录的左右子侧长度相等为O(n)
最坏的情况下:待排序记录正序或逆序,O(n2)