常用排序算法

前言

之前对排序算法理解不是很深刻，也容易把几个算法混在一起，所以整理了几个常用的排序算法，并尝试在自己的理解上给几个算法优化了下。

冒泡排序

冒泡应该是最好理解的排序算法，所以把它放在第一个讲。冒泡的思想是：两两比较相邻记录，步骤为:
1、从第一个元素开始往后遍历数组，并与每个元素对比，如果比其他元素小则交换元素
2、从第二个元素开始往后遍历数组，并与每个元素对比，如果比其他元素小则交换元素
3、......

用代码实现为：

func bubbleSort(var arr:[Int]) -> [Int]{
    for i in 0..<arr.count {
        for var j = i+1; j < arr.count; j++ {
            if arr[i] > arr[j] {
                let guide = arr[j]
                arr[j] = arr[i]
                arr[i] = guide
            }
        }
    }
    return arr
}

这是最传统的冒泡排序，需要执行的步骤为 n + (n-1) + (n-2) + (n-3) + ......+ 1= (n+1)*n/2,所以时间复杂度为O(n^2)。

传统的冒泡排序只是暴力遍历数组，逐个比较大小，只要比当前值小的就会交换，将当前位置排好的过程中，对于接下来的排序没有任何的帮助，所以需要做一些改善。

如果在遍历的时候从后往前遍历，然后将较小的数往前面排，这样的话在接下来的排列过程中，就会更有优势，因为你在把当前位置排列好的同时将某些相对小的元素也排到了前面，在数据较多的时候能大大减少数据两两交换的次数。
口头描述比较抽象，还是看代码吧

func betterBulleSort(var arr:[Int]) -> [Int]{
    for i in 0..<arr.count {
        //从后往前遍历，这里是与传递冒泡不一样的地方
        for var j = arr.count - 1; j>0 && j>=i; j-- {
            //如果前面的元素比当前的大，就把当前元素往前移
            if arr[j-1] > arr[j] {
                let guide = arr[j-1]
                arr[j-1] = arr[j]
                arr[j] = guide
            }
        }
    }
    return arr
}

除此之外，如果待排序的数组为

2,1,3,4,5,6,7,8

在第一次1和2交换位置之后整个数组就是有序的了，接下来的所有比较都是浪费的。这种情况下可以设置一个flag，增加一个flag为真才继续遍历的控制，代码实现为：

func bestBubbleSort(var arr:[Int]) -> [Int]{
    var flag = true
    for i in 0..<arr.count {
        //如果flag为假则说明接下来的每个数都是有序的
        if !flag { break }

        for var j = arr.count - 1; j>0 && j>=i; j-- {
            //每次遍历都默认flag为false
            flag = false
            if arr[j-1] > arr[j] {
                let guide = arr[j-1]
                arr[j-1] = arr[j]
                arr[j] = guide
                //当有发生位置交换，设置flag为真，表明接下来的数可能是无序
                flag = true
            }
        }
    }
    
    return arr
}

简单排序

简单排序的核心思想：找准时机、再做替换
和冒泡相比，冒泡每次都做替换，简单排序是遍历数组后找到最小元素的下标后再做替换。

func simpleSort(var arr:[Int]) -> [Int] {
    var minIndex = 0
    for i in 0..<arr.count {
        minIndex = i
        //遍历找到最小元素所在的下标
        for var j = i+1; j<arr.count; j++ {
            if arr[j]<arr[minIndex] { minIndex = j }
        }
        //如果最小元素下标不是当前下标就交换
        if minIndex != i {
            let guide = arr[i]
            arr[i] = arr[minIndex]
            arr[minIndex] = guide
        }
    }
    
    return arr
}

简单排序的时间复杂度也是O(N^2)
虽然简单排序和冒泡排序的时间复杂度一样，但是简单排序在性能方面还是好很多的，交换次数没像冒泡那么频繁。

直接插入排序

直接插入排序的基本操作是将一个无序的数插入到有序的表中，从而得到一个有序的表。
步骤：
1、将需要插入的数取出赋值给哨兵。
2、向前遍历表，每个元素都与哨兵比较大小，如果比哨兵大，则将这个元素向后移动一个位置，知道找到比哨兵小的元素，将哨兵放入该位置。
看看代码实现：

func directInsertSort(var arr:[Int]) -> [Int] {
    var guide = 0
    for i in 1..<arr.count {
        //如果当前元素比前面元素大说明现在为有序状态
        if arr[i-1] < arr[i] { continue }
        
        //取出需要排序的元素
        guide = arr[i]
        //向前遍历表，每个元素与哨兵比较大小
        for var j=i-1; j>=0 && arr[j]>guide; j-- {
            //比哨兵大的元素向后移动
            arr[j+1] = arr[j]  
        }
        //将哨兵插入合适位置
        arr[j+1] = guide
    }

    return arr
}

直接插入排序的时间复杂度为O(n^2)

希尔排序

希尔排序（Shell Sort）可以看成是对直接插入排序的优化，相对于直插法，它比较的步长变长了，基本思路为，将一个以一定的步长分割为多个组，每个组分别使用直插法进行排序，之后缩短步长，继续这个操作，直到步长为1为止。希尔排序使得排序算法的时间复杂度突破了O(n^2)的限制。

假设有这样一组数

[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]

共16个元素如果我们以步长为5开始进行排序
先将这组数一五为步长，分为几组，第一组为[a0,a5,a10,a15]，第二组为[a2,a6,a11],第三组为......，分完组应该是这样的：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后用直插法对每列进行排序，得到：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

经过第一次排序得到的数组为：

[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]

可以看出第一个元素10已经在正确的位置上了，接下来已3为步长再次对数组进行分组：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后再以步长为1进行排序，这里就是直接插入排序了

代码实现为：

func shell(var arr:[Int]) -> [Int] {
    //指定步长
    var gap = arr.count
    var temp = 0
    var j = 0
    
    do{
        gap /= 2
        
        for i in gap..<arr.count
         {
            if arr[i] > arr[i-gap] { continue }
            
            temp = arr[i]
            for j = i-gap; j>0 && arr[j]>temp;j-=gap {
               arr[j+gap] = arr[j]
            }
            arr[j+gap] = temp
        }
    }while(gap>1)
    
    return arr
}

希尔算法的步长是决定时间复杂度的关键，但是究竟应该选择什么样的步长才是最好的，目前还是一个数学难题。不过大量的研究数据表明，步长与时间复杂度存在以下关系：

步长与时间复杂度关系

快速排序

快速排序应该是排序算法中最经典的了，最早是由图灵奖的获得者Tony Hoare设计出来的。它与冒泡排序比较相似，也是通过不断比较得出有序的表，但是相对于冒泡，快排中增大了记录的比较和移动距离，将关键字较大的记录直接移动到后面，关键字较小的记录从后面移动到前面，从而大大减少了总的比较次数和移动交换次数。

快排的基本思想是：通过一趟排序将待排序的表分为两部分，即比关键字小的部分和比关键字大的部分，然后再对这两个部分重复操作，直到整个序列有序

文字描述难免有些抽象，来看看代码怎么实现吧，在看代码过程中请记住快排序的基本思想，会有助于理解

func quickSort(var arr:[Int], var low:Int, var high:Int) -> [Int]{
    
    //递归退出条件
    if low < high {
        /*!
         *1、获取flag值的下标和已经初略排序好的数组：
         *flag前（后）面的元素比flag值小（大），
         */
        let pivot = partition(arr, low: low, high: high).0
        arr = partition(arr, low: low, high: high).1
        /*!
         *2、递归，flag前后两部分继续此操作，直到有序为止
         */
        arr = quickSort(arr, low: low, high: pivot-1)
        arr = quickSort(arr, low: pivot+1, high: high)
    }
    
    return arr
}

func partition(var arr:[Int], var low:Int, var high:Int) -> (Int,[Int]) {
    var flag = arr[low]
    var guide:Int?
    /*!
     *两头开工，遍历数组，
     *将比key大的移动到后面，
     *比key小的移动到前面
     */
    while (low < high){
        //往前遍历
        while low<high && arr[high]>flag { high-- }
        arr = swapeObject(arr, low: low, high: high)
        //往后遍历
        while low<high && arr[low]<flag{ low++ }
        arr = swapeObject(arr, low: low, high: high)
    }
    
    return ((arr as NSArray).indexOfObject(flag),arr)
}

//MARK: 交互元素
func swapeObject(var arr:[Int], low:Int, high:Int) -> [Int]{
    let guide = arr[high]
    arr[high] = arr[low]
    arr[low] = guide
    
    return arr
}