阅读 19

排序算法笔记之冒泡排序

###冒泡排序

  • 冒泡排序的执行流程
    • 从头开始以此比较相邻两个元素的大小,每轮比较过后当前轮次最大(或最小)元素会冒泡到最末尾的位置
    • 排除尾部已经有序的序列,循环执行冒泡操作直至完毕。
for end in (1...(array.count - 1)).reversed() {
            for begin in 0..<end {
                cmpCount += 1
                if array[begin] > array[begin+1]{
                    swapCount += 1
                    let temp = array[begin]
                    array[begin] = array[begin+1]
                    array[begin+1] = temp
                }
            }
        }
复制代码
  • 冒泡排序的优化
    • 当数组全部有序后,提前终止循环.
for end in (1...(array.count - 1)).reversed() {
            var flag = true
            for begin in 0..<end {
                cmpCount += 1
                if array[begin] > array[begin+1]{
                    swapCount += 1
                    let temp = array[begin]
                    array[begin] = array[begin+1]
                    array[begin+1] = temp
                    flag = false
                }
            }
            if flag == true {
                break
            }
        }
复制代码
  • 每次排列后尾部已经有序,记录有序元素的位置,减少比较次数
for var end in (1...(array.count - 1)).reversed() {
            var lastSwapIndex = 1
            for begin in 0..<end {
                cmpCount += 1
                if array[begin] > array[begin+1]{
                    let temp = array[begin]
                    array[begin] = array[begin+1]
                    array[begin+1] = temp
                    lastSwapIndex = begin
                    swapCount += 1
                }
            }
            end = lastSwapIndex
        }

复制代码
  • 冒泡排序的稳定性

属于稳定的排序算法,前提是在比较元素大小和交换元素位置时,不使用 <= || >= 运算符

  • 冒泡排序的时间复杂度和空间复杂度
    • 时间复杂度
    采用两轮for循环,时间复杂度为O(n^2)
    • 空间复杂度
    O(1)
  • 原地算法
    • 概念:不依赖或依赖少数的额外资源,仅依靠输出覆盖输入
    • 空间复杂度为O(1)的算法可以认为是原地算法
    • 冒泡排序即位原地算法

代码及单元测试:https://github.com/yukifeng/suanfaStudy