<file_sep>local swap = function(array, index1, index2)
    local temp = array[index2]
    array[index2] = array[index1]
    array[index1] = temp;
end

local heapadjust = function(array, parent, len)
    local child = 1;
    local value = array[parent];
    child = 2 * parent
    while (child <= len) do
        if (child < len and array[child] < array[child + 1]) then
            child = child + 1 
        end
        if (value < array[child]) then
            array[parent] = array[child]
        else
            break
        end 
        parent = child
        child = 2 * parent
    end
    array[parent] = value
end

-- 函数说明：堆排序，堆积是一个近似完全二叉树的结构（二叉堆），
-- 并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。。
--
-- @param   {array} array 数组
-- @param   {int}   len 数组长度
--
-- @return 空
local heapsort = function(array, len)
    local i = math.floor(len / 2)
    for i = i, 1, -1 do
        heapadjust(array, i, len)
    end

    for i = len, 1, -1 do
        swap(array, 1, i);
        heapadjust(array, 1, i - 1);
    end
end

return heapsort
--[[
local arr = {40, 32, 52, 22, 32, 55, 10}
heapsort(arr, #arr)

       40
   32      52       ->
22   32  55   10
--------------------------------
       40
   32      55       ->
22   32  52   10
--------------------------------
       55
   32      52       -> 
22   32  40   10
--------------------------------
now frist index is max.
loop:
    swap(frist, last) get max
    heapadjust(1, len - 1)
]]--
<file_sep>-- 函数说明：数组拷贝
--
-- @param   {array} src 源数组
-- @param   {int}   srcPos 源数组拷贝起始index
-- @param   {array} dest 目标数组
-- @param   {int}   destPos 目标数组起始index
-- @param   {int}   length 拷贝长度
--
-- @return 空
local arraycopy = function(src, srcPos, dest, destPos, length)
    if(length <= 0 ) then return end
    for index = length - 1, 0, -1 do
        dest[destPos + index] = src[srcPos + index]
    end
end

-- 函数说明：合并排序，从中间分隔，左右两边的数都是递归排好序的，在合并的时候就可以递增比较合并了。
--
-- @param   {array} src 需要排序的数组
-- @param   {array} buffer 缓存数组
-- @param   {int}   start 排序的起始index
-- @param   {int}   mid 排序的中间index
-- @param   {int}   end_ 排序的结束index
--
-- @return 空
local merge = function(source, buffer, start, mid, end_)
    local i = start
    local k = start
    local j = mid + 1
    while (i <= mid and j < end_ + 1) do
        if (source[i] > source[j]) then
            buffer[k] = source[j]
            k = k + 1
            j = j + 1
        else
            buffer[k] = source[i]
            k = k + 1
            i = i + 1
        end
    end
    if (i ~= mid + 1) then
        arraycopy(source, i, source, i + (j - mid - 1), mid - i + 1)
    end
    arraycopy(buffer, start, source, start, i - start + j - mid - 1)
end

local mergeSort

-- 函数说明：合并排序
--
-- @param   {array} array 需要排序的数组
-- @param   {array} temp 缓存数组
-- @param   {int}   start 排序的起始index
-- @param   {int}   end_ 排序的结束index
--
-- @return 空
mergeSort = function(array, temp, start, end_)
    if(start < end_) then
        local midIndex = math.floor((start + end_) / 2)
        mergeSort(array, temp, start, midIndex)
        mergeSort(array, temp, midIndex + 1, end_)
        merge(array, temp, start, midIndex, end_)
    end
end

-- local array = {3, 4, 2, 1, 5, 7, 9 , 332, 1, 32, 434, 332}
-- {3, 4, 2, 1, 5, 7, 9 , 332, 1, 32, 434, 332} -> {1, 1, 2, 3, 4, 5, 9, 32, 332, 332 ,434}
-- {3, 4, 2, 1, 5, 7}{9 , 332, 1, 32, 434, 332} -> {1, 2, 3, 4, 5, 7}{1, 9, 32, 332, 332, 434}
-- {3, 4, 2}{1, 5, 7} -> {2, 3 ,4}{1, 5, 7}
-- {3, 4}{2} -> {2, 3, 4}
-- {3}{4}
-- 从中间分隔，左右两边的数都是递归排好序的，在合并的时候就可以递增比较合并了。
-- local temp = {}
-- mergeSort(array, temp, 1, #array)
<file_sep>-- 函数说明：插入排序
--
-- @param   {array} array 需要排序的数组
-- @param   {int}   s 排序的起始index
-- @param   {int}   e 排序的结束index
--
-- @return 空
local insert_sort = function(array, s, e)
    local start_ = 1
    local end_ = #array
    if(s and e) then start_, end_ = s, e end

    for i = start_, end_, 1 do
        local insert_data = array[i]
        local j = i
        while (j > start_) do
            if(array[j - 1] > insert_data) then
                array[j] = array[j - 1]
            else
                break;
            end
            j = j - 1
        end

        if(j ~= i) then
            array[j] = insert_data
        end
    end
end

return insert_sort

<file_sep>local insert_sort = require('insert_sort')
local swap = function(array, index1, index2)
    local temp = array[index2]
    array[index2] = array[index1]
    array[index1] = temp;
end

local partition = function(array, low, high, pivot_index)
    local pivot_value = array[pivot_index]
    swap(array, low, pivot_index)

    while (low < high) do
        while (low < high and array[high] >= pivot_value) do
            high = high - 1 
        end
        if (low < high) then
            array[low] = array[high]
            low = low + 1
        end

        while (low < high and array[low] <= pivot_value) do
            low = low + 1
        end
        if(low < high) then
            array[high] = array[low]
            high = high - 1
        end
    end
    array[low] = pivot_value
    return low
end

local select
local K_GROUP_SIZE = 5

-- 函数说明：BFPRT 算法解决的问题十分经典，即从某n个元素的序列中选出第 k 小（第 k 大）的元素，通过巧妙的分析，BFPRT 可以保证在最坏情况下仍为线性时间复杂度。
--
-- @param   {array} array 数组
-- @param   {int}   left 数组起点
-- @param   {int}   right 数组终点
-- @param   {int}   k 第几大
--
-- @return 空
select = function(array, left, right, k)
    local size = right - left + 1
    if (size <= K_GROUP_SIZE) then
        insert_sort(array, left, right)
        return array[k + left - 1]
    end

    local num_group = math.ceil(size / K_GROUP_SIZE)

    for i = 0, num_group - 1, 1 do
        local sub_left = left + i * K_GROUP_SIZE
        local sub_right = sub_left + K_GROUP_SIZE - 1
        if (sub_right > right) then
            sub_right = right
        end
        insert_sort(array, sub_left, sub_right)
        local median = sub_left + math.floor((sub_right - sub_left) / 2);
        swap(array, left + i, median);

    end

    local pivot_index = left + math.floor((num_group - 1) / 2)

    select(array, left, left + num_group - 1, math.floor((num_group + 1) / 2))

    local mid_index = partition(array, left, right, pivot_index)
    local _ith = mid_index - left + 1

    if (k == _ith) then
        return array[mid_index]
    elseif (k < _ith) then
        return select(array, left, mid_index - 1, k)
    else 
        return select(array, mid_index + 1, right, k - _ith)
    end
end

return select
-- local arr = {15, 16, 7, 8, 29, 10, 11, 12, 13}
-- local value = select(arr, 1, #arr, 4)
<file_sep>-- low值做拆分的pivotekey，将数字拆分成两块。
-- pivotkey在多次交换后，会形成左边比pivotekey小，右边pivotekey大。
-- {4, 5, 1, 3, 8, 7} pivotkey: 4
-- 4, 5, 1, 3, 8, 7 ->
-- l        .  .  h
-- 3, 5, 1, 3, 8, 7 ->
-- l  .     h
-- 3, 5, 1, 5, 8, 7 ->
-- l  .  h
-- 3, 1, 1, 5, 8, 7 -> (while end)
--       lh
-- 3, 1, 4, 5, 8, 7 -> (pivotkey is 4, left lower, right bigger)
local partition = function(array, low, high)
    local pivotkey = array[low]

    while (low < high) do
        while (low < high and array[high] > pivotkey) do
            high = high - 1
        end

        if (low < high) then
            array[low] = array[high]
            low = low + 1
        end

        while (low < high and array[low] <= pivotkey) do
            low = low + 1
        end

        if(low < high) then
            array[high] = array[low]
            high = high - 1
        end
    end
    array[low] = pivotkey
    return low
end

local quicksort

-- 函数说明：快速排序
--
-- @param   {array} array 需要排序的数组
-- @param   {int}   low 排序的起始index
-- @param   {int}   high 排序的结束index
--
-- @return 空
quicksort = function(array, low, high)
    if (low < high) then
        local middle = partition(array, low, high)
        if (low < middle - 1) then
            quicksort(array, low, middle - 1)
        end
        if (middle + 1 < high) then
            quicksort(array, middle + 1, high)
        end
    end
end

return quicksort

<file_sep># 一些基础算法
>>
## 参考文献
- [http://alfred-sun.github.io/blog/2015/03/11/ten-basic-algorithms-for-programmers](http://alfred-sun.github.io/blog/2015/03/11/ten-basic-algorithms-for-programmers "Blog Archive")

## 简单描述
- 线性查找：[bfprt_search](https://github.com/SpectatorWang/algorithms/blob/master/bfprt_search.lua)
- 二分查找：[binary_search](https://github.com/SpectatorWang/algorithms/blob/master/binary_search.lua)
- 堆排序：[heap_sort](https://github.com/SpectatorWang/algorithms/blob/master/heap_sort.lua)
- 插入排序：[insert_sort](https://github.com/SpectatorWang/algorithms/blob/master/insert_sort.lua)
- 合并排序：[merge_sort](https://github.com/SpectatorWang/algorithms/blob/master/merge_sort.lua)
- 快速排序：[quick_sort](https://github.com/SpectatorWang/algorithms/blob/master/quick_sort.lua)<file_sep>-- 函数说明：二分查找算法，在有序数组中查找某一特定元素的搜索算法。
--
-- @param   {array} array 数组
-- @param   {int}   value 需要查询的数
--
-- @return 空
local binary_search = function(array, value)
    local low = 1
    local high = #array
    local mid = 1
    while (low <= high) do
        -- 如果使用 (low + high) / 2 有可能计算 low + high 的时溢出
        mid = math.ceil(low + (high - low) / 2)
        if(value == array[mid]) then
            return mid
        end
        if(value < array[mid]) then
            high = mid - 1
        else
            low = mid + 1
        end
    end
    return 0
end
return binary_search
-- local array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 15, 354}
-- local index = binary_search(array, 15)

