数据结构与算法（三）—— 常见排序算法和swift实现

Shuqy
1,132 阅读8分钟

目录

  1. 冒泡排序
  2. 插入排序
  3. 选择排序
  4. 堆排序
  5. 归并排序
  6. 快速排序
  7. 计数排序
  8. 桶排序

冒泡排序

原理：

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

时间复杂度:O(n^2)

///冒泡函数代码实现
func bubbleSort(_ arr: inout [Double]) {
    for i in 0 ..< arr.count {
        for j in 0 ..< arr.count - i {
            if j+1 < arr.count {
                if arr[j] > arr[j+1] {
                    let temp = arr[j]
                    arr[j] = arr[j+1]
                    arr[j+1] = temp
                    
                }
            }
           
        }
    }
}

插入排序

原理：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到下一位置中
  6. 重复步骤2~5

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

时间复杂度:O(n^2)

///插入排序的实现
func insertSort(_ arr: inout [Double]) {
    //从第1位开始作为要插入的数
    for i in 1 ..< arr.count  {
        let temp = arr[i]
        var j = i - 1
    
        while (j >= 0 && temp < arr[j]) {
            //与已排序的数逐一比较，大于temp时，该数移后
            arr[j + 1] = arr[j]
            j -= 1
        }
        if j != i - 1 {
            //在相应的位置插入（因为上面j-1跳出while循环,所以这里是j+1）
            arr[j + 1] = temp
        }
       
    }
}

选择排序

原理：

对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推

时间复杂度：O(n^2) ，不稳定

选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。 比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

///选择排序
func selectionSort(_ arr: inout [Double]) {
    
    for i in 0 ..< arr.count-1 {
        
        var min = i
        //找出最小值的位置
        for j in i+1 ..< arr.count {
            if arr[min] > arr[j] {
                min = j
            }
        }
        //如果最小值的下标不是i，就交换
        if min != i {
            let temp = arr[i]
            arr[i] = arr[min]
            arr[min] = temp
        }

    }
    
}

堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

原理：

  1. 将无序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
  2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
  3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

   

时间复杂度：O(nlogn),不稳定

/*
 堆排序
 */

//调整一个根节点和左右节点的位置
func adjustHeap(arr:inout [Double],i: Int,length: Int) {

    let temp = arr[i]
    var tempNum = i
    var left = 2 * i + 1

    while left < length {
        
        ///如果右节点存在，且大于左节点，取右节点
        if left+1 < length && arr[left + 1] > arr[left]{
            left += 1
        }
        ///如果父节点已经大于子节点
        if temp >= arr[left] {
            break
        }
        
        arr[tempNum] = arr[left]
        tempNum = left
        left = 2*left + 1
    }
    arr[tempNum] = temp
}

//互换数组元素
func swapArr(arr: inout [Double],index1: Int,index2:Int) {
    let temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
}

///堆排序
func heapSort(_ arr: inout [Double]) {
    
    ///创建初始化堆
    var i = arr.count/2
    while i >= 0 {
        adjustHeap(arr: &arr, i: i, length: arr.count)
        i -= 1
    }
    
    var j = arr.count - 1
    while j > 0 {
        swapArr(arr: &arr, index1: 0, index2: j)
        adjustHeap(arr: &arr, i: 0, length: j)
        j -= 1
    }
    
    
}

归并排序

原理：

将无序的序列分成子序列，将子序列排序在合成有序的序列。

例如：初始状态：6,202,100,301,38,8,1

  1. 第一次归并后：{6,202},{100,301},{8,38},{1}
  2. 第二次归并后：{6,100,202,301}，{1,8,38}
  3. 第三次归并后：{1,6,8,38,100,202,301}

时间复杂度：O(nlogn)

///归并排序的实现
func mergeSort(_ arr: inout [Double]) {
    var temp = Array<Double>(repeating:0, count: arr.count)
    helperSort(arr: &arr, left: 0, right: arr.count-1,temp: &temp)
}

///分
func helperSort(arr: inout [Double], left: Int, right: Int, temp: inout [Double]) {
    
    if left < right {
        let mid = (left + right)/2
        ///递归分数组左边元素
        helperSort(arr: &arr, left: left, right: mid,temp: &temp)
        ///递归分数组右边元素
        helperSort(arr: &arr, left: mid+1, right: right,temp: &temp)
        ///递归合并子数组
        merge(arr: &arr, left: left, right: right, mid: mid, temp: &temp)
    }
}

///合
func merge(arr: inout [Double], left: Int, right: Int, mid: Int, temp: inout [Double]) {
    var i = left //
    var j = mid + 1
    var t = 0 //临时数组下标
    
    ///把左边和右边的元素按顺序放进temp
    while i <= mid && j <= right {
        if arr[i] <= arr[j] {
            temp[t] = arr[i]
            t += 1
            i += 1
        }else {
            temp[t] = arr[j]
            t += 1
            j += 1
        }
    }
    
    ///将左边剩余元素放进temp中
    while i <= mid {
        temp[t] = arr[i]
        t += 1
        i += 1
    }
    //将右边剩余元素放进temp中
    while j <= right {
        temp[t] = arr[j]
        t += 1
        j += 1
    }


    //将temp中的元素全部拷贝到原数组中
    i = left
    t = 0
    while i <= right {
        arr[i] = temp[t];
        i += 1
        t += 1
    }
}

快速排序

原理：

已知数组：A[n]

  1. 设置两个变量i、j，排序开始的时候：i = 0，j = N-1
  2. 以第一个数组元素作为关键数据，赋值给key，即key = A[0]
  3. 从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]的值赋给A[i]
  4. 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]的值赋给A[j] 5.重复第3、4步，直到i = j

时间复杂度：O(nlogn)


///快速排序的实现
///大于基数的数放在右边，小于基数的数放在左边
func quicklySort(arr: inout [Double], left: Int, right: Int) {
    
    if left >= right {
        return
    }
    
    let num = arr[left] //取第一个数作为基数
    var l = left
    var r = right
    
    while l < r {
        //从右边遍历
        while l < r && arr[r] >= num{
            r -= 1
        }
        arr[l] = arr[r]
       
        while l < r && arr[l] <= num{
            l += 1
        }
        arr[r] = arr[l]

    }
    
    arr[l] = num

    quicklySort(arr: &arr, left: left, right: l - 1)
    quicklySort(arr: &arr, left: l + 1 , right: right)
    
}

计数排序

原理：

首先要排序的数都是整数

  1. 找出最大值max和最小值min
  2. 创建一个大小为max-min+1的数组Temp，每个元素的值都为0
  3. 遍历数，找到Temp对应的下标的元素加1，即统计数出现的次数
  4. 通过遍历Temp，根据统计的每个数的次数，相对应的排序

计数排序是一种非比较类型的算法，所以没有O(nlogn)的下限，是通过牺牲空间换时间的算法。

时间复杂度：O(n)

//计数排序的实现
func countSort(_ arr: inout [Int]) {
    if arr.count <= 1 {
        return
    }
    //找出最大值和最小值
    var max = arr[0]
    var min = arr[0]
    for num in arr {
        if num >= max {
            max = num
        }
        
        if min >= num{
            min = num
        }
    }
    let len = max - min + 1
    var temp = Array<Int>(repeatElement(0, count: len))
    //统计每个数出现的次数
    for num in arr {
        temp[num - min] = temp[num - min] + 1
    }
    print(temp)
    var nextIndex = 0;
    for  i  in  0 ..< temp.count {
        var val = temp[i]
        while val > 0  {
            arr[nextIndex] = i + min;
            nextIndex = nextIndex + 1
            val = val - 1
        }
    }

    
}

桶排序

原理：

  1. 找出最大值max和最小值min
  2. 给定一个桶的数量，创建一个桶数组（二维数组），每个桶的范围为（max-min+1）/桶的数量
  3. 遍历数，把数值添加到对应范围的桶中，如果桶中有其他数值，按要求排序
  4. 通过遍历桶数组，得到一个顺序的数组

时间复杂度：O(n)

///桶排序
///bucketCount是桶的大小
func bucketSort(_ arr: inout [Double], bucketCount:Int) {
 
    if arr.count <= 1 || bucketCount <= 0 {
        return
    }
    //找出最大值和最小值
    var max = arr[0]
    var min = arr[0]
    for num in arr {
        if num >= max {
            max = num
        }
        
        if min >= num{
            min = num
        }
    }
    
    //每个桶的数值范围
    let space = (max - min + 1) / Double(bucketCount)
    var buckets = Array<Array<Double>>(repeating: [Double](), count: bucketCount)
    //将数值放到对应范围的桶中
    for i in 0 ..< arr.count {
        ///数值对应的桶
        let index = Int((arr[i] - min) / space)
        //
        if buckets[index].isEmpty {
            buckets[index].append(arr[i])
        }else {
            ///从小到大排序
            for j in 0 ..< buckets[index].count {
                if arr[i] > buckets[index][j] {
                    buckets[index].insert(arr[i], at: j + 1)
                }
            }
          
        }
        
    }
    
    ///排序所有的桶
    var n  = 0
    var index = 0
    while n < buckets.count {
        let bucket = buckets[n]
        if !bucket.isEmpty {
            arr.insert(contentsOf: bucket, at: index)
            index += bucket.count
        }
        n = n + 1
    }
    
    
}
avatar
文章
阅读
粉丝
相关推荐
总是跳转到国内版(cn.bing.com)？New Bing使用全攻略
474k阅读
 · 
146点赞
20个常见的前端算法题，你全都会吗？
38k阅读
 · 
829点赞
一些简单的算法和数据结构（排序算法）
1.0k阅读
 · 
77点赞
为什么 React 的 Diff 算法不采用 Vue 的双端对比算法？
67k阅读
 · 
1.2k点赞
排序算法-冒泡排序和选择排序
16k阅读
 · 
289点赞