基础排序算法之swift

2018-11-29

最近稍微空闲，发现之前熟悉的基础排序和查找算法忘的差不多了，原理都还能说得清，动手就有些含糊了，所以就有了重新认识一下的想法，顺便复习一下数据结构。

1、快速排序算法

快速排序在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法策略来把一个串行分为两个子串行。

算法步骤：

1 、从数列中挑出一个元素，称为 “基准”，
2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作。
3 、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

code：

  /**
 * 快速排序
 *
 */
func quickSort(array: inout [Int], leftIndex: Int, rightIndex: Int) {
    if leftIndex >= rightIndex  {
        return
    }
    let pivotIndex = quickSortPartition(array: &array, pivotIndex: leftIndex, endIndex: rightIndex)
    //左边部分快排
    quickSort(array: &array, leftIndex: leftIndex, rightIndex: pivotIndex - 1)
    //右边部分快排
    quickSort(array: &array, leftIndex: pivotIndex + 1, rightIndex: rightIndex)
}

/**
 * 分区
 * @params pivotIndex 基准开始的索引
 * @params endIndex   截止索引
 * @return    基准最后的索引
 */
func quickSortPartition(array: inout [Int], pivotIndex: Int, endIndex: Int) -> Int {
    var currentIndex = pivotIndex + 1
    var currentPivotIndex = pivotIndex
    let pivotParma = array[pivotIndex]
    while currentIndex <= endIndex{
        if pivotParma > array[currentIndex] {
            let currentParma = array[currentIndex]
            array.remove(at: currentIndex)
            array.insert(currentParma, at: (pivotIndex > 0 ? pivotIndex - 1 : 0))
            currentPivotIndex += 1
        }
        currentIndex += 1
    }
    return currentPivotIndex
}

2、堆排序算法

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

算法步骤：

1、创建一个堆H[0..n-1]
2、把堆首（最大值）和堆尾互换
3、把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4、重复步骤2，直到堆的尺寸为1

code：

//MARK:func Heapsort(array: inout [Int]) {
    //1.构建大顶堆
    var index = array.count / 2 - 1
    while index >= 0 {
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(array: &array, inde: index, length: array.count)
        index -= 1
    }
    //2.调整堆结构+交换堆顶元素与末尾元素
    var j = array.count - 1
    while j > 0 {
        array.swapAt(0, j)//将堆顶元素与末尾元素进行交换
        adjustHeap(array: &array, inde: 0, length: j)//重新对堆进行调整
        j -= 1
    }
}
//调整堆
func adjustHeap(array: inout [Int], inde: Int, length: Int) {
    var index = inde;
    var tem = array[index]
    var curentIndex = index * 2 + 1
    while curentIndex < length {
        if curentIndex + 1 < length && array[curentIndex] < array[curentIndex + 1] {
            curentIndex += 1;
        }
        if array[curentIndex] > tem {
            array.swapAt(index, curentIndex)
        }else{
            break
        }
        index = curentIndex
        tem = array[index];
        curentIndex = curentIndex * 2 + 1
    }
}

3、归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

算法步骤：

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾

4、冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法步骤：

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

code：

//MARK: 冒泡排序
func bubbleSort(array: inout [Int]) {
    let n = array.count - 2
    for i in 0 ... n {
        for j in 0 ... (n - i) {
            if array[j] > array[j + 1]  {
                array.swapAt(j, j + 1)
            }
        }
    }
}

5、希尔排序

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法步骤：

1、取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；
2、取第二个增量d2<d1重复上述的分组和排序，直至所取的增量
=1(<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

code：

//MARK: 希尔排序
func shellSort(array: inout [Int]) {
    //增量
    var increment = array.count / 2
    while increment > 0 {
        for i in 0 ... increment - 1 {
            var a = i
            //每次增量进行直接插入排序
            while a < array.count {
                var currentINC = increment;
                while a + currentINC < array.count {
                    if array[a] > array[a + currentINC]  {
                        array.swapAt(a, a + currentINC)
                    }
                    currentINC += increment
                }
                a += increment
            }
        }
        increment = increment / 2
    }
}

这是自己的拙见，欢迎指正，🙏。