排序算法总结

sort

Posted by Jow on June 19, 2019

目录

  1. 插入排序
  2. 选择排序
  3. 冒泡排序
  4. 分治法 –归并排序
  5. 快速排序
  6. 堆排序
  7. 希尔排序
  8. 二叉树排序
  9. 基数排序
  10. 桶排序
  11. 计数排序
  12. 排序算法的稳定性

Like a good player to fight, then for your dream and what you love.

插入排序

就像抓扑克牌一样,每次将新拿到的牌插入到正确的位置,在其之后的牌顺序往后移动一位。

1
2
3
4
5
6
7
8
9
10
11
local arr = { 2, 5, 2, 1, 65, 7, 43, 35, 723, 234 }
for i = 2, #arr do
    local key = i - 1
    local keyValue = arr[i]
    while key > 0 and arr[key] > keyValue do --now small to big, change '>' to '<' then will get big to small
        arr[key + 1] = arr[key]
        key = key - 1
    end
    arr[key + 1] = keyValue
end

选择排序

每次选择一个数字放到正确的位置上:

举个例子,序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
local arr = { 2, 5, 2, 1, 65, 7, 43, 35, 723, 234 }
for i = 1, #arr do
    local key = i
    local keyValue = arr[i]
    for j = i + 1,  #arr do
        if arr[j] < keyValue then --now small to big, change '<' to '>' then will get big to small
            key = j
            keyValue = arr[j]
        end
    end
    arr[key] = arr[i]
    arr[i] = keyValue
end

冒泡排序

每次相邻的两个元素进行比较,将最大或者最小的元素进行沉淀。

优化一:如果某一轮两两比较中没有任何元素交换,这说明已经都排好序了,算法结束,可以使用一个Flag做标记,默认为false,如果发生交互则置为true,每轮结束时检测Flag,如果为true则继续,如果为false则返回。

优化二:某一轮结束位置为i,但是这一轮的最后一次交换发生在lastSwap的位置,则lastSwap到i之间是排好序的,下一轮的结束点就不必是i++了,而直接到lastSwap

1
2
3
4
5
6
7
8
local arr = { 2, 5, 2, 1, 65, 7, 43, 35, 723, 234 }
for i = 1, #arr do
    for j = 1, #arr - i do
        if arr[j] > arr[j + 1] then
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
        end
    end
end

分治法

很多有用的算法在结构上是递归的,为解决一个给定的问题,算法一次或者多次递归的调用其自身以解决紧密相关的若干子问题。

这些算法典型的遵循分治法的思想,将原问题分解为几个规模较小但类似于原问题的子问题,递归的求解这些子问题,然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时都有三个步骤:

  1. 分解原问题为若干个子问题
  2. 解决这些子问题,递归的求解各个子问题,然而子问题规模足够下则直接求解
  3. 合并这些子问题的解成原问题的解

归并排序算法:

  1. 分解待排序的n个元素成n/2个元素的子序列
  2. 使用归并排序递归的排序两个子序列
  3. 合并两个已排序的子序列

在这里需要排序的元素个数变成一个的时候就需要进行合并了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
local arr = { 2, 5, 2, 1, 65, 7, 43, 35, 723, 234 }

local merge = function(arr, p, q, r)
    local arr1 = {}
    local arr2 = {}
    table.move(arr, p, q, 1, arr1)
    table.move(arr, q + 1, r, 1, arr2)
    local i = 1
    local j = 1
    for k = p, r do
        if not arr2[j] or arr1[i] and arr1[i] > arr2[j] then --now small to big, change '>' to '<' then will get big to small
            arr[k] = arr1[i]
            i = i + 1
        else
            arr[k] = arr2[j]
            j = j + 1
        end
    end
end

local split
split = function(arr, p, r)
    if p < r then
        local q = math.floor((p + r) / 2)
        split(arr, p, q)
        split(arr, q + 1, r)
        merge(arr, p, q, r)
    end
end

split(arr, 1, #arr)

分治算法的运行时间来自于基本模式的三个步骤,假设T(n)为规模为n的一个问题的运行时间,如果规模足够小,运行时间为常量O(1),

假设把原问题分解成a个子问题,每个问题的规模就是原问题的1/b。所以对于一个n/b的子问题运行时间为T(n/b)的时间所以需要aT(n/b)的时间求解a个子问题。设分解问题时间D(n),合成C(n),所以总时间:

T(n) = {O(1);足够小的时候

aT(n/b) + D(n) + C(n) 其他}

在归并排序中,a和b都为2,所以可以把上面的式子变成:

c 和 2T(n/2) + cn。

T(n) = cn + 2T(n/2) = 4T(n/4) + cn/2 + cn/2 + cn就这样了像二叉树一样,一直分治下去,知道第lg2 + 1层 n/n==1,运行时间为c。

又因为每一层的运行时间都为cn所以总运行时间为 :cnlgn + cn

快速排序

快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。

在选择key的时候默认一般选择第一个元素,但是这样做算法不够稳定,我们可以在选择key值的时候使用随机算法,随机产生一个位于q,r之间的整数作为分隔值,然后对两侧进行移动。随机算法一般用在输入的时候,对输入进行随机排序,这样产生的期望值是lgn,比较平均,不会产生极端。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
local arr = { 2, 5, 2, 1, 65, 7, 43, 35, 723, 234 }
local quickSort
quickSort = function(arr, q, r)
    if q < r then
        local i = q
        local j = r
        local key = i
        local keyValue = arr[i]
        while i < j do
            while i < j do
                if arr[j] < keyValue then
                    arr[key], arr[j] = arr[j], arr[key]
                    key = j
                    keyValue = arr[j]
                    break
                else
                    j = j - 1
                end
            end
            while i < j do
                if arr[i] > keyValue then
                    arr[key], arr[i] = arr[i], arr[key]
                    key = i
                    keyValue = arr[i]
                    break
                else
                    i = i + 1
                end
            end
        end
        quickSort(arr, q, key - 1)
        quickSort(arr, key + 1, r)
    end
end

local function randomizedPartition(A, p, r)
    local m = math.random(p, r)
    A[r],A[m] = A[m],A[r]
    return A
end

堆排序

我们知道堆的结构是节点i的孩子为2i和2i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没 有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

希尔排序

希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小, 插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元 素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

在最内层的循环排序就是插入排序。

希尔排序就是优化过的插入排序,当然是针对于大量数据的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
local arr = { 2, 5, 2, 1, 65, 7, 43, 35, 723, 234 }

local d = #arr
repeat
    d = math.floor(d / 2)
    for i = 1, d do
        for j = i + d, #arr, d do
            local key = j - d
            local keyValue = arr[j]
            while key > 0 and arr[key] > keyValue do --now small to big, change '>' to '<' then will get big to small
                arr[key + d] = arr[key]
                key = key - d
            end
            arr[key + d] = keyValue
        end
    end
until (d == 1)

二叉树排序

和堆排序很像,利用二叉搜索树每次输出最小的元素。这样的删除操作不会影响二叉搜索树的结构。

基数排序

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优 先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。 在下面的例子中我的最高位是百位,就不再计算了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
local arr = { 2, 5, 2, 1, 65, 7, 43, 35, 723, 234 }

for i = 1, 3 do
    local bucket = { {}, {}, {}, {}, {}, {}, {}, {}, {}, {} } --初始化10个桶
    for j, v in ipairs(arr) do
        local index = v
        if i > 1 then
            index = math.floor(v / (10) ^ (i - 1)) -- attention
        end
        index = index % 10
        table.insert(bucket[index + 1], v)
    end
    arr = {}
    for i, v in ipairs(bucket) do
        for j, k in ipairs(v) do
            table.insert(arr, k)
        end
    end
end

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:

在额外空间充足的情况下,尽量增大桶的数量

使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。

计数排序

计数排序通过使用额外的存储空间来实现排序。使用一个等于排序最大值的空间。通过直接向额外的空间添加计数个数,然后进行累加,就可以得到每个数字的位置。这种排序最好直到最大值是多少。且不要太大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
local arr = { 2, 5, 3, 0, 2, 3, 0, 3 }
local arrSort = { 0, 0, 0, 0, 0, 0, 0, 0 }

local extraArr = { 0, 0, 0, 0, 0, 0 }
for i, v in ipairs(arr) do
    extraArr[v + 1] = extraArr[v + 1] + 1
end

for i = 2, #extraArr do
    extraArr[i] = extraArr[i - 1] + extraArr[i]
end

for i = #arr, 1, -1 do
    arrSort[extraArr[arr[i] + 1]] = arr[i] --记得加一,因为存的时候加了一,通过arr[i]来作为index访问extraArr,进而找到存arrsort的位置
    extraArr[arr[i] + 1] = extraArr[arr[i] + 1] - 1 --注意减一,这样重复的数字才能不放在一起
end

排序算法的稳定性

判断一个排序算法是否稳定,两个相同的数字排完序之后,之前在前面的还是在前面,那么这个排序算法就是稳定的。

堆排序、快速排序、希尔、计数、直接选择排序是不稳定的排序算法。

基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。