首页 > 代码库 > Swift的排序算法总结

Swift的排序算法总结

下面让我们一起来见识一下swift中基于Array的扩展的冒泡排序,选择排序和快速排序吧。

1.冒泡排序

冒泡排序再基础不过了,这里就不再讲其原理了,实在不会可以看下百度百科冒泡排序
既然冒泡排序避免不了数组中两个数据交换,先写一个交换函数

// 交换数组中i和j两个位置的数据
extension Array {
    fileprivate mutating func swap(i:Int,j:Int) { 

        let temp = self[i]
   self[i] = self[j]
   self[j] = temp

    }
}

下面就是排序了也很简单就不多解释了

// MARK: - 冒泡排序
/**
* 通过与相邻元素的比较和交换,把小的数交换到最前面。
*/

extension Array where Element:Comparable {
mutating func bubbleSort() {
    for i in 0..<self.count-1 {
        for j in (i+1...self.count-1).reversed() {
           // 后者小于前者,交换位置,即小的往上升大的往下沉
           if self[j] < self[j-1] {
               swap(i: j, j: j-1)
            }
         }
      } 
   }
}

因为是排序,所以元素必须满足协议是可比较的。
下面快速排序和选择排序也是同样的道理。

2.快速排序

/** 快速排序的算法思想

 *  一趟快速排序的算法是:

 *   1、设置两个变量i、j,排序开始的时候:i=0,j=N-1;

 *   2、以第一个数组元素作为基准数据,赋值给key,即key=A[0];

 *   3、从j开始向前搜索,即由后开始向前搜索(j减1),找到第一个小于key的值A[j],将A[j]和A[i]互换;

 *   4、从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;

 *   5、重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,

 *     使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。

 *     另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

 */

extension Array where Element:Comparable {

    private mutating func quickPartition(left:Int, right:Int)->Int {

        var right = right
   var left = left

        // 记录哪个是基准数
     let base = self[left]

        // 记录基准数位置
     let baseIndex = left

        // 先从右边往左边扫描,找到第一个比base要小的数,但是不能与left相遇
   while left < right && self[right] >= base {
           right = right-1
}

        // 再从左边往右边扫描,找到第一个比base还要大的数,但是不能与right相遇
   while left < right && self[left] <= base {
         left = left+1
}

        // 交换 左边比base大的数和右边比base小的数
    swap(i: left,j: right)

        // 交换左边比base大的数和基准数
    swap(i: baseIndex,j: left)

        // 返回新的基准数
    return left

}

 

/// 快速排序

/// - Parameters:
///   - a: 数组a
///   - left: 左边索引
///   - right: 右边索引

    private mutating func quickSort(left: Int, right: Int) {

        // 排序完毕,退出递归
    if left >= right {
        return
   }

        // 每一趟划分,使左边的比基准小,右边的比基准大,并返回新的基准的位置

        let baseIndex = quickPartition(left: left, right: right)

        // 判断左边是否排完,没排完递归排左边部分
    if baseIndex - 1 > left {
        quickSort(left: left, right: baseIndex - 1)
    }

        // 判断右边是否排完,没排完递归排右边部分
    if baseIndex + 1 < right {
        quickSort(left: baseIndex + 1, right: right)
    }

    }

    mutating func quickSort() {
    quickSort(left: 0, right: self.count-1)

    }

}

3.选择排序

// MARK: - 选择排序

/** 选择排序算法思想
*  每一趟从前往后查找出值最小的索引(下标),最后通过比较是否需要交换。每一趟都将最小的元素交换到最前面。
*  大致过程
*  6, 4, 9, 7, 5(开始)
*  4, 6, 9, 7, 5(第一趟:将最小的4与6交换,使这一趟最小值4放到最前面)
*  4, 5, 9, 7, 6(第二趟:将最小的5与6交换,使这一趟最小值5放到最前面)
*  4, 5, 6, 7, 9(第三趟:将最小的6与9交换,使这一趟最小值6放到最前面)
*  4, 5, 6, 7, 9(第四趟:不需要交换,排序完成)
*/

extension Array where Element:Comparable {

    mutating func selectorSort() {

        var min = 0

        // 只需要n-1趟即可,到最后一趟只有一个元素,一定是最小的了
    for i in 0..<self.count-1 {

            // 每一趟的开始,假设该趟的第一个元素是最小的
    min = i

            // 查找该趟有没有更小的,如果找到更小的,则更新最小值的下标
     for j in i+1..<self.count-1 {

                if self[j] < self[min] {
        min = j

                }
   }

            // 如果该趟的第一个元素不是最小的,说明需要交换
    if min != i {
        swap(i: min, j: i)

           }          
   }

   }  

}

 

Swift的排序算法就总结到这里。

如果大家觉得这篇博文整理得不错,就给点个赞吧。 如果在再哪里整理得有疏忽的地方,还希望各位博友的指点。

感谢各位博友对这篇文章的支持哦!!! 谢谢。

Swift的排序算法总结