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

冒泡排序

原理：

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

时间复杂度:

///冒泡函数代码实现
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 将新元素插入到下一位置中
5. 重复步骤2~5

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

时间复杂度:

///插入排序的实现
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记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推

时间复杂度： ，不稳定

选择排序的交换操作介于 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. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

时间复杂度： ,不稳定

/*
 堆排序
 */

//调整一个根节点和左右节点的位置
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
    }
    
    
}


复制代码

归并排序

原理：

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

时间复杂度：

///归并排序的实现
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
    }
}


复制代码

快速排序

原理：

时间复杂度：

///快速排序的实现
///大于基数的数放在右边，小于基数的数放在左边
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)
    
}

复制代码

计数排序

原理：

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

时间复杂度：

//计数排序的实现
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. 通过遍历桶数组，得到一个顺序的数组

时间复杂度：

///桶排序
///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
    }
    
    
}

复制代码