排序算法实现

冒泡排序

-- 冒泡排序（Bubble Sort）
-- 1. 空间复杂度为O（1），原地排序
-- 2. 稳定排序
-- 3. 时间复杂度：最好情况O（n），最坏情况O（n方），平均情况O（n方）
function bubbleSort(array)
    if #array <= 1 then
        return
    end

    for i=1,#array do
        local isChange = false  --提前退出冒泡循环的标志位
        for j=1, #array-i do
            if array[j] > array[j+1] then
                local t = array[j]
                array[j]=array[j+1]
                array[j+1] = t
                isChange = true --有数据交换
            end
        end

        --没有数据交换，结束循环
        if not isChange then
            break
        end
    end
end

插入排序

-- 插入排序（Insertion Sort）
-- 空间复杂度为O（1），原地排序
-- 稳定排序
-- 时间复杂度：最好情况O（n），最坏情况O（n方），平均情况O（n方）
function insertionSort(array)
	if #array <= 1 then
		return
	end

	for i=2, #array do
		local val = array[i]
		local index = i 	-- 插入的位置
		-- 查找插入的位置
		for j = i - 1, 1, -1 do
			if val < array[j] then
				array[j+1] = array[j]
				index = j
			else
				break
			end
		end
		array[index] = val
	end
end

选择排序

-- 选择排序（Selection Sort）
-- 空间复杂度O（1），原地排序
-- 不稳定排序
-- 时间复杂度：最好情况O（n方），最坏情况O（n方），平均情况O（n方）
function selectionSort(array)
	if #array <= 1 then
		return
	end

	for i=1, #array do
		-- 找出最小下标
		local minIndex = i
		for j=i+1,#array do
			if array[j] < array[minIndex] then
				minIndex = j
			end
		end

		-- 将最小值放到已排区间的末尾
		if minIndex > i then
			local t = array[i]
			array[i] = array[minIndex]
			array[minIndex] = t
		end
	end
end

归并排序

--归并排序（Merge Sort）
--空间复杂度O（n）
--稳定排序
--[[事件复杂度:
		T(n) = T(a) + T(b) + n
			 = 2*T(n/2) + n 
			 = 2*(2*T(n/4)+n/2) + n = 4T(n/4) + 2n
			 = 4*(2T(n/8)+n/4) + 2n = 8T(n/8) + 3n
			 ...
			 =2的k方*T(n/2的k方) + kn

		当T(n/2的k方) = T(1)时，也就是n/2的k方=1，得k=log2(n)
		所以T(n) = Cn + nlog2(n), 即时间复杂度为O(nlogn)
		归并排序和有序度无关，最好最坏平均情况都是O(nlogn)
]]--
function mergeSort(array, beginIndex, endIndex)
	--递归终止条件
	if beginIndex >= endIndex then
		return
	end

	--取beginIndex到endIndex的中间位置point
	local point = math.floor((beginIndex+endIndex)/2)
	--分治递归
	mergeSort(array, beginIndex, point)
	mergeSort(array, point+1, endIndex)
	--将array[beginIndex..point]和array[point+1.。endInex]合并到array[beginIndex..endIndex]
	merge(array, beginIndex, point, endIndex)
end
function merge(array, beginIndex, pointIndex, endIndex)
	local tmp = {}	--申请一个临时数组
	local i, j, k = beginIndex, pointIndex+1, beginIndex

	--将两部分数组由小到大存入到临时数组tmp中
	while(i<=pointIndex and j<=endIndex) do
		if array[i] < array[j] then
			tmp[k] = array[i]
			i = i+1
		else
			tmp[k] = array[j]
			j = j+1
		end
		k = k + 1
	end

	--判断哪个子数组有剩余的数据
	local s, e = i, pointIndex
	if j <= endIndex then
		s, e = j, endIndex
	end

	--将剩余的数据存入到临时数组tmp中
	for m=s,e do
		tmp[k]=array[m]
		k = k+1
	end

	--将临时数组tmp的数据拷贝到原数组
	for m=beginIndex, endIndex do
		array[m] = tmp[m]
	end
end

快速排序

--快速排序（Quick Sort）
--空间复杂度O（1），原地排序
--不稳定
--事件复杂度：最好O(logn), 最坏O(n方),平均O(logn)
function quickSort(array, beginIndex, endIndex)
	--递归终止条件
	if beginIndex>= endIndex then
		return
	end

	--获取分区点
	local point = partition(array, beginIndex, endIndex)
	quickSort(array, beginIndex, point-1)
	quickSort(array, point+1, endIndex)
end
function partition(array, beginIndex, endIndex)
	local pivot = array[endIndex]
	local i = beginIndex
	for j=beginIndex, endIndex do
		if array[j] < pivot then
			local t = array[j]
			array[j] = array[i]
			array[i] = t
			i = i + 1
		end
	end

	local t = array[i]
	array[i] = array[endIndex]
	array[endIndex] = t

	return i
end

求无序数组中第K大元素

--求无序数组中第K大元素
function findK(array, beginIndex, endIndex, k)
	--只有一个元素时，它就是结果
	if beginIndex>=endIndex then
		return array[beginIndex]
	end

	--获取分区点，左侧大于分区点值，右侧小于分区点值
	local pivot = sssPartition(array, beginIndex, endIndex)

	--pivot是排好序的位置
	--如果pivot == k，那array[pivot]就是第k大元素；
	--如果pivot<k，则第k大元素在右侧区，递归右侧区；
	--如果pivot>k，则则第k大元素在左侧区，递归左侧区
	if pivot == k then
		return array[pivot]
	elseif pivot<k then
		return findK(array, pivot+1, endIndex, k)
	else
		return findK(array, beginIndex, pivot-1, k)
	end
end
function sssPartition(array, beginIndex, endIndex)
	local pivot = array[endIndex]
	local i = beginIndex
	for j=beginIndex, endIndex do
		if array[j] > pivot then
			local t = array[j]
			array[j] = array[i]
			array[i] = t
			i = i + 1
		end
	end

	local t = array[i]
	array[i] = array[endIndex]
	array[endIndex] = t

	return i
end

--Test
local ttt ={4, 2, 5, 12, 3}
print(findK(ttt, 1, #ttt, 0))