Swift 排序算法实战笔记：冒泡,插入,选择-一一网

这是我参与更文挑战的第20天，活动详情查看：更文挑战

排序对于任何一个程序员来说，可能都不会陌生。在平常的项目中，经常能用到也许大概率是排序算法。大部分编程语言中，也都提供了排序函数（sort），今天总结了几个日常中比较常用的算法。

常见的排序算法有：

冒泡排序
插入排序
选择排序
归并排序

冒泡排序（Bubble Sort）

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

假如我们要对一组数据4，5，6，3，2，1，从小到大进行排序。第一次冒泡操作的详细过程就是这样：

在这里插入图片描述

冒泡排序优化

func bubbleSort(_ array : [Int]){
    var list = array
    //记录循环次数
    var count = 0
    for i in 0..<list.count {
        count = i
        for j in i+1..<list.count{
            if list[i] > list [j] {
                let tmp = list[j]
                list[j] = list[i]
                list[i] = tmp 
            }
        }
    }
    print(list)
    print("count: ",count)
}

var array = [4,5,6,3,2,7]
bubbleSort(array)


[4, 5, 6, 3, 2, 7]
 count:  5

复制代码

数据的交换过程在swift中还有3种写法

交换方式1

  list.swapAt(i, j)
复制代码

交换方式2

   (list[i], list[j]) = (list[j], list[i])
复制代码

交换方式3

  swap(&list[i], &list[j])
复制代码

插入排序（Insertion Sort）

插入排序将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据a插入到已排序区间时，需要拿a与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素a插入。

func insertSort(_ array : [Int])->[Int]{
    var list = array
    //建立一个空数组，符合条件的插入，没插入的尾后添加
    var newList = [list[0]]
    //记录循环的次数
    var count = 0
    for i in 1..<list.count {
        var min : Int? = nil//从小到大排序
        count = i
        for j in 0..<newList.count {
            if list[i] < newList[j] {
                min = i
                newList.insert(list[i], at: j)
                break
            }
        }
        
        if min == nil {
            newList.append(list[i])
        }
    }
    print(newList)
    print("count: ",count)
    return newList
}

var array = [4,5,6,3,2,7]
array = insertSort(array)
print(array)

复制代码

//MARK: 直接插入排序
func directInsertSort(_ arr:inout [Int])
{
    for i in 1..<arr.count
    {
        //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
        for j in stride(from:i - 1,through: 0,by:-1)
        {
            if arr[j] < arr[i] {break}
             //如找到了一个合适的位置
            if j != i - 1
            {
                let temp:Int = arr[i]
                //将比a[i]大的数据向后移
                for k in stride(from: i - 1, to: j, by: -1)
                {
                    arr[k + 1] = arr[k]
                    //将a[i]放到正确位置上
                    arr[k + 1] = temp
                }
            }
        }
    }
}

var array = [4,5,6,3,2,7]
directInsertSort(&array)
print(array)
//[4, 5, 2, 2, 2, 7]

复制代码

选择排序（Selection Sort）

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

func selectionSort(_ array: [Int]) -> [Int] { 
  guard array.count > 1 else { return array }  // 1如果数组为空，或者只有一个数字，无需整理，直接返回

  var a = array                    // 2 拷贝一份数组。这是一个必要过程，因为我们无法在swift里直接修改array参数。

  for x in 0 ..< a.count - 1 {     // 3

    var lowest = x
    for y in x + 1 ..< a.count {   // 4 内循环，用来寻找未排序数组中的最小
      if a[y] < a[lowest] {
        lowest = y
      }
    }

    if x != lowest {               // 5
      swap(&a[x], &a[lowest])
    }
  }
  return a
}
复制代码