排序算法总结

插入排序

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

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的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

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

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

分治法

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

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

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

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

归并排序算法：

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

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

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，比较平均，不会产生极端。

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排序是不稳定的。

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

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

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)

二叉树排序

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

基数排序

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

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 个桶中

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

计数排序

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

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

排序算法的稳定性

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

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

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

sort

目录