阅读 315

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

目录

  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
    }
    
    
}

复制代码
关注下面的标签,发现更多相似文章
评论