你好,游客 登录 注册 搜索
背景:
阅读新闻

7 种常见的排序算法

[日期:2016-06-20] 来源:简书  作者:天空中的球 [字体: ]

排序算法可以说是数据结构与算法当中最为基础的部分,针对的是数组这一数据结构。将数组中的无序数据元素通过算法整理为有序的数据元素即为排序

算法一:插入排序

排序算法
插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

步骤如下:
1. 从第一个元素开始,该元素可以认为已经被排序
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置中
6. 重复步骤2
//MARK:- 插入排序
func insertSort(inout arr: [Int]) -> [Int] {

    for i in 1 ..< arr.count {
        let key = arr[i]
        var j = i - 1
        while j >= 0 && arr[j] > key {
            arr[j + 1] = arr[j]
            j -= 1
        }
        arr[j + 1] = key
    }
    return arr

}

算法二:希尔排序

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

步骤如下:
* 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;
* 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
//MARK:- 希尔排序
func shellSort(inout arr: [Int]) -> [Int] {
    var j: Int
    var gap = arr.count / 2
    while  gap > 0 {

        for i in 0 ..< gap {
            j = i + gap
            while j < arr.count {
                if arr[j] < arr[j - gap] {
                    let temp = arr[j]
                    var k = j - gap
                    while (k >= 0 && arr[k] > temp) {
                        arr[k + gap] = arr[k]
                        k -= gap
                    }
                    arr[k + gap] = temp
                }

                j += gap
            }

        }
        gap /= 2

    }

    return arr
}

备注: 详细的希尔排序解析

算法三:选择排序

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

步骤如下:
* 遍历数组,找到最小的元素,将其置于数组起始位置。
* 从上次最小元素存放的后一个元素开始遍历至数组尾,将最小的元素置于开始处。
* 重复上述过程,直到元素排序完毕。
//MARK:- 选择排序
func selectionSort(inout arr: [Int]) -> [Int] {
    for i in 0 ..< arr.count - 1 {
        var min = i
        for j  in i+1 ..< arr.count {
            if arr[min] > arr[j] {
                min = j
            }
        }
        let temp = arr[min]
        arr[min] = arr[i]
        arr[i] = temp
    }   
    return arr
}

算法四:冒泡排序

冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

步骤如下:
* 比较相邻的元素。如果第一个比第二个大,就交换他们两个,直到把最大的元素放到数组尾部。
* 遍历长度减一,对剩下的元素从头重复以上的步骤。
* 直到没有任何一对数字需要比较时完成。
//MARK:- 冒泡排序
func bubbleSort(inout arr: [Int]) -> [Int] {
    for i in 0 ..< arr.count {
        for j in 0 ..< arr.count - 1 - i {
            if arr[j] > arr[j + 1] {
                let temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    } 
    return arr
}

算法五:归并排序

归并排序

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

步骤如下:
1. 申请空间,创建两个数组,长度分别为两个有序数组的长度
2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
//MARK:- 归并排序
func mergeSort(inout arr: [Int]) -> [Int] {

    func merge (inout arr: [Int], low: Int, mid: Int, high: Int, inout temp: [Int]) {
        var i = low
        var j = mid + 1
        let m = mid
        let n = high
        var k = 0

        while (i <= m && j <= n) {
            if (arr[i] <=  arr[j])
            {
                temp[k] = arr[i]
                k += 1
                i += 1
            }
            else
            {
                temp[k] = arr[j]
                k += 1
                j += 1
            }
        }

        while i <= m {
            temp[k] = arr[i]
            k += 1
            i += 1
        }

        while j <=  n {
            temp[k] = arr[j]
            k += 1
            j += 1
        }

        for f in 0 ..< k {
            arr[low + f] = temp[f]
        }

    }

    func internalMergeSort(inout arr: [Int], low: Int, high: Int, inout temp: [Int]) {
        if high <= low {
            return
        }
        let mid = low + (high - low) / 2
        // 左边有序
        internalMergeSort(&arr, low: low, high: mid, temp: &temp)
        // 右边有序
        internalMergeSort(&arr, low: mid + 1, high: high, temp: &temp)
        // 将两边合起来
        merge(&arr, low: low, mid: mid, high: high, temp: &temp)
    }

    var temp: [Int] = arr// 辅助数组
    internalMergeSort(&arr, low: 0, high: arr.count - 1, temp: &temp)
    return arr
}

算法六:快速排序

快速排序

快速排序(Quicksort)是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

步骤:
* 从数列中挑出一个元素,称为 “基准”(pivot),
* 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
* 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
//MARK:- 快速排序
func quickSort(inout arr: [Int]) -> [Int] {
    func partition(p: Int, _ r: Int) -> Int {
        var i = p - 1
        let key = arr[r]
        for j in p ..< r {
            if arr[j] < key {
                i = i + 1
                let temp = arr[j]
                arr[j] = arr[i]
                arr[i] = temp
            }
        }
        arr[r] = arr[i + 1]
        arr[i + 1] = key
        return i + 1
    }

    func internalQuickSort(p: Int, _ r: Int) {
        if p < r {
            let q = partition(p, r)
            internalQuickSort(p, q - 1)
            internalQuickSort(q + 1, r)
        }
    }
    internalQuickSort(0, arr.count - 1)
    return arr
}

算法七:堆排序

s007.gif

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

步骤如下:
* 按堆的定义将数组R[0..n]调整为堆(这个过程称为创建初始堆),交换R[0]R[n];
* 将R[0..n-1]调整为堆,交换R[0]R[n-1];
* 重复上述过程,直到交换了R[0]R[1]为止。
//MARK:- 堆排序
func heapSort(inout arr: [Int]) -> [Int] {

    func buildheap(inout arr: [Int]) {
        let length = arr.count
        let heapsize = length
        var nonleaf = length / 2 - 1
        while nonleaf >=  0 {
            heapify(&arr, i: nonleaf, heapsize: heapsize)
            nonleaf -= 1
        }

    }

    func heapify(inout arr: [Int], i : Int, heapsize: Int){
        var smallest = i
        let left = 2*i+1
        let right = 2*i+2
        if(left < heapsize){
            if(arr[i]>arr[left]){
                smallest = left
            }
            else {
                smallest = i
            }
        }
        if(right < heapsize){
            if(arr[smallest] > arr[right]){
                smallest = right
            }
        }
        if(smallest != i){
            var temp: Int
            temp = arr[i]
            arr[i] = arr[smallest]
            arr[smallest] = temp
            heapify(&arr,i: smallest,heapsize: heapsize)
        }

    }

    func internalHeapSort(inout arr: [Int]) {
        var heapsize = arr.count
        buildheap(&arr)
        for _ in 0 ..< arr.count - 1 {
            var temp: Int
            temp = arr[0]
            arr[0] = arr[heapsize - 1]
            arr[heapsize - 1] = temp
            heapsize = heapsize - 1
            heapify(&arr, i: 0, heapsize: heapsize)

        }

    }

    internalHeapSort(&arr)
    return arr
}

参考

http://codecloud.net/sort-2208.html

http://wenzhiquan.github.io/2016/03/28/seven_sort/




收藏 推荐 打印 | 录入:elainebo | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款