Lua 快速排序

快排

-- local list = {10, 3, 1111, 23, 9, 34, 100, 123, 5, 32, 75, 66, 44, 67, 12}
local list = {10, 3, 1111, 23, 9, 34}
-- local list = {10, 3, 23}

self:quickSort(list, 1, #list)
dump(list, "list===")

function MainScene:quickSort(arr, lowIndex, heightIndex)
    if lowIndex >= heightIndex then
        return
    end
    local temp = arr[lowIndex]
    local i = lowIndex
    local j = heightIndex
    while (i < j)
    do
        while (i<j and temp < arr[j])
        do
            j = j -1
        end
        arr[i] = arr[j]

        while (i<j and arr[i] < temp)
        do
            i = i +1
        end
        arr[j] = arr[i]
    end
    arr[i] = temp

    self:quickSort(arr, lowIndex, i)
    self:quickSort(arr, i+1, heightIndex)
end

在一个数组中快速找出第K大的数

local list = {10, 13, 1111, 23, 9, 34, 100, 123, 5, 32, 75, 66, 44, 67, 12}
-- local list = {5, 10, 3, 23, 32}

local k = 4
local k_max = self:quickSort_K_max(list, 1, #list, k)
print("k_max---》", k_max)


function MainScene:quickSort(arr, lowIndex, heightIndex)
    -- local arr = clone(list)
    if lowIndex >= heightIndex then
        print("----------")
        return
    end
    local temp = arr[lowIndex]
    local i = lowIndex
    local j = heightIndex
    while (i < j)
    do
        while (i<j and temp <= arr[j])
        do
            j = j -1
        end
        arr[i] = arr[j]

        while (i<j and arr[i] < temp)
        do
            i = i +1
        end
        arr[j] = arr[i]
    end
    arr[i] = temp
    -- self:quickSort(arr, lowIndex, i)
    -- self:quickSort(arr, i+1, heightIndex)
    return i
end

function MainScene:quickSort_K_max(arr, lowIndex, heightIndex, k)

    if lowIndex >= heightIndex then
        return arr[lowIndex]
    end
    local mid = self:quickSort(arr, lowIndex, heightIndex)
     if mid == k then
        return arr[mid]
    elseif (mid > k) then
        return self:quickSort_K_max(arr, lowIndex, mid, k)
    elseif (mid < k) then
        return self:quickSort_K_max(arr, mid+1, heightIndex, k)
    end
end