写在前面
- 推荐一个排序可视化网站：VisuAlgo
- 代码里所有输出都是通过下面这个输出函数输出的
function outNum( needOutNum )
for k,v in ipairs(needOutNum) do
print(v)
end
end
- lua里的#到这都成注释了= =||||，所以就不贴代码了，直接贴图
一、选择排序
1. 原理
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
2. 代码实现
选择排序
二、冒泡排序
1. 原理
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
2. 代码实现
冒泡排序
3. 优化代码
- 记录最后一次交换的位置，下一次交换就从这结束
-
记录是否交换，如果没有交换证明已经有序了
冒泡排序优化
三、插入排序
1. 原理
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
2. 代码实现
插入排序
四、希尔排序
1. 原理
- 将整个待排元素序列分割成若干个子序列，分别进行插入排序
- 依次缩减增量再进行排序
- 待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序
2. 代码实现
希尔排序
五、归并排序
1. 原理
- 递归将数组两两划分
- 对划分的数组分别进行排序
- 合并排序好的数组
2. 代码实现
- 递归版
function mergeSortTest(needSortTable)
local tempTable = {}
local mergeTable = function (left,right)
tempTable = {}
local middle = math.floor((right + left)/2)
local i = left
local j = middle + 1
local t = 1
while (i<=middle and j<=right) do
if needSortTable[i] <= needSortTable[j] then
tempTable[t] = needSortTable[i]
i = i + 1
t = t + 1
else
tempTable[t] = needSortTable[j]
j = j + 1
t = t + 1
end
end
while(i<=middle) do
tempTable[t] = needSortTable[i]
i = i + 1
t = t + 1
end
while(j<=right) do
tempTable[t] = needSortTable[j]
j = j + 1
t = t + 1
end
for i=1,t-1 do
needSortTable[left] = tempTable[i]
left = left + 1
end
end
local function divideTable (left,right)
if left < right then
local middle = math.floor((right + left)/2)
divideTable(left,middle)
divideTable(middle+1,right)
mergeTable(left,right)
end
end
divideTable(1,#needSortTable)
outNum(needSortTable)
end
- 非递归版
function mergeSortNonRecursiveTest(needSortTable)
local tempTable = {}
local mergeTable = function (left,middle,right)
tempTable = {}
local i = left
local j = middle + 1
local t = 1
while (i<=middle and j<=right) do
if needSortTable[i] <= needSortTable[j] then
tempTable[t] = needSortTable[i]
i = i + 1
t = t + 1
else
tempTable[t] = needSortTable[j]
j = j + 1
t = t + 1
end
end
while(i<=middle) do
tempTable[t] = needSortTable[i]
i = i + 1
t = t + 1
end
while(j<=right) do
tempTable[t] = needSortTable[j]
j = j + 1
t = t + 1
end
for i=1,t-1 do
needSortTable[left] = tempTable[i]
left = left + 1
end
end
local i = 1
while(i<#needSortTable) do
local left = 1
local middle = left + i - 1
local right = middle + i
while(right<=#needSortTable) do
mergeTable(left,middle,right)
left = right + 1
middle = left + i - 1
right = middle + i
end
--如果middle大于数组长度，说明没有right部分，不需要合并了
if (left<=#needSortTable and middle<=#needSortTable) then
mergeTable(left,middle,#needSortTable)
end
i = i + i
end
outNum(needSortTable)
end
六、快速排序
1. 原理
- 挑选基准值：从数列中挑出一个元素
- 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成
- 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序
2. 代码实现
快速排序
七、桶排序
1. 原理
- 设置一个定量的数组当作空桶子
- 寻访序列，并且把项目一个一个放到对应的桶子去
- 对每个不是空的桶子进行排序
- 从不是空的桶子里把项目再放回原来的序列中
2. 代码实现
桶排序
八、堆排序
1. 原理
- 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
2. 代码实现
堆排序
九、基数排序
1. 原理
- 求数据的最大位数
- 从个位数开始对每位数进行排序，存放在桶中
- 从不是空的桶子里把值再放回原来的序列中
2. 代码实现
function radixSortTest( needSortTable )
local function getMaxNumOfDigits(unsortedTable)
local temp = 0
local num = 0
for k,v in ipairs(unsortedTable) do
temp = math.max(temp,v)
end
while temp >10 do
num = num + 1
temp = temp/(math.pow(10,num))
end
return num
end
local maxNum = getMaxNumOfDigits(needSortTable)
for i=0,maxNum do
local tempList = {0,0,0,0,0,0,0,0,0,0}
local outPutList = {}
local curNum = math.pow(10,i)
for k,v in ipairs(needSortTable) do
if (v/curNum)%10+1 <= 10 then
tempList[math.floor(v/curNum)%10+1] = tempList[math.floor(v/curNum)%10+1] + 1
end
end
local k = 1
while k + 1 < #tempList do
tempList[k+1] = tempList[k+1] + tempList[k]
k = k + 1
end
for j = #needSortTable,1,-1 do
local num = math.floor(needSortTable[j]/curNum)%10 + 1
if tempList[num] > 0 then
outPutList[tempList[num]] = needSortTable[j]
tempList[num] = tempList[num] - 1
end
end
for q = 1,#needSortTable do
needSortTable[q] = outPutList[q]
end
end
outNum(needSortTable)
end
