数组-冒泡排序

采用冒泡方式对数组进行排序

冒泡百科:冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它要重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小,首字母从Z到A)错误就把他们交换过来.走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成.
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

摘一个示例做个说明.
示例 1：
输入: [0,5,9,3,12,7]
输出: [0,3,5,7,9,12]

算法原理:

1. 比较相邻的元素.如果第一个比第二个大,就交换他们两个
2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.在这一点最后的元素应该会是最大的数
3. 针对所有的元素重复以上的步骤,除了最后一个.
4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数组需要比较
5. 算法演示 冒泡排序示例.gif

算法分析:

1. 时间复杂度
   文件的初始状态是正序:一次扫描即可完成排序.所需的关键字比较次数C和记录移动次数M均达到最小值:C_min = n - 1, M_min = 0.所以冒泡排序最好的时间复杂度为O(n).
   文件的初始状态是反序:需要n-1趟排序.每趟排序需要进行 n - i 次关键字的比较.且每次比较都必须移动记录三次来达到交换记录为之.在这种情况下,比较和移动均达到最大值: C_max = n(n - 1) / 2 = O(n²), M_max = 3n(n - 1) / 2 = O(n²) .此时泡沫排序的最坏时间复杂度为O(n²).
   综上,冒泡排序总的平均时间复杂度为O(n²).
2. 算法稳定性
   冒泡排序就是把最小的元素往前调或者最大的元素往后调.比较的是相邻的两个元素比较,交换也发生在这两个元素之间.所以两个元素相等,是不会进行交换的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的顺序没有改变.
   综上,冒泡排序是一种稳定排序算法.

代码实现-Swift版本:

func bubbleSort(nums: inout [Int]){
    for i in 0 ..< nums.count {
        for j in 0 ..< nums.count - 1 - i {
            if nums[j] > nums[j + 1] {
                // 系统交换方法
                nums.swapAt(j, j + 1)
            }
        }
    }
}

算法优化:

• 问题:
  数据的顺序排好之后,冒泡算法仍然回继续执行下一轮的比较,直到length - 1次,后面的比较没有意义.
• 方案:
  设置标志位flag,如果发生了交换flag设置为true,如果没有发生交换就设置为false.
  这样当这一轮比较结束后如果flag仍未false,即这一轮没有发生交换,说明数据的顺序已经排好了,没有必要继续循环.

优化代码:

func bubbleSortOptimize(nums: inout [Int]){
    var flag: Bool
    for i in 0 ..< nums.count {
        flag = false
        for j in 0 ..< nums.count - 1 - i {
            if nums[j] > nums[j + 1] {
                nums.swapAt(j, j + 1)
                flag = true
            }
        }
        if !flag {
            break
        }
    }
}

测试用例:

var nums = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

参考:

• 冒泡百科
• 一像素

考察要点:

• 数组
• 排序