概述
冒泡排序
function BubbleSort(arr)
local len = #arr;
for i = 1,len do
for j = 1,len-i do
if (a[j] < a[j+1]) then
a[j],a[j+1] = a[j+1],a[j];
end
end
end
end
插入排序
function InsertSort(arr)
local len = #arr
for i = 2,len do
local temp = arr[i]
local j = i-1
while(j >= 1 and temp > arr[j]) do
arr[j+1] = arr[j]
j = j-1;
end
arr[j+1] = temp;
end
end
选择排序
function SelectSort(arr)
local len = #arr
for i = 1,len-1 do
local maxNum = arr[i]
local maxIndex = i
for j = i,len do
if(arr[j] > maxNum) then
maxNum = arr[j]
maxIndex = j
end
end
if(i~=maxIndex) then
arr[i],arr[maxIndex] = arr[maxIndex],arr[i]
end
end
end
快速排序
function QuickMainSort(arr,left,right)
if(left>=right) then
return
end
local i = left
local j = right
local temp = arr[left]
while(i<j) do
while(temp>=arr[j] and i<j ) do
j=j-1
end
while(temp<=arr[i] and i<j ) do
i=i+1
end
if(i<j) then
arr[i],arr[j] = arr[j],arr[i]
end
end
arr[left] = arr[i]
arr[i] = temp
QuickMainSort(arr,left,i-1)
QuickMainSort(arr,i+1,right)
end
function QuickSort(arr)
QuickMainSort(arr,1,#arr)
end
归并排序
function Merge(arr,left,mid,right)
if(left>=right) then
return
end
local tab_temp ={}
local i=left
local k=mid+1
while(i<=mid and k<=right) do
if(arr[i]>arr[k]) then
table.insert(tab_temp,arr[i])
i=i+1
else
table.insert(tab_temp,arr[k])
k=k+1
end
end
while(i<=mid) do
table.insert(tab_temp,arr[i])
i=i+1
end
while(k<=right) do
table.insert(tab_temp,arr[k])
k=k+1
end
for j=left,right do
arr[j]=tab_temp[j-left+1]
end
end
function MergeMain(arr,left,right)
if(left<right) then
local mid = (left+right)//2
MergeMain(arr,left,mid)
MergeMain(arr,mid+1,right)
Merge(arr,left,mid,right)
end
end
function MergeSort(arr)
MergeMain(arr,1,#arr)
end
希尔排序
function ShellSort(arr)
local len = #arr
for gap=1,3 do --这里可以倒序 gap从3到1 令4-gap = gap;
for i=1,4-gap do
for j=i+4-gap,len do
local temp = arr[j]
local k = j-4+gap;
while(k>=1 and temp>arr[k]) do
arr[k+4-gap] = arr[k]
k=k-4+gap;
end
arr[k+4-gap] = temp
end
end
end
end
堆排序
function HeapBulid(arr,root,size)
local left = root*2
local right = root*2+1
local largest = root
if(left<=size and arr[left] < arr[largest]) then
largest = left
end
if(right<=size and arr[right] < arr[largest])then
largest = right
end
if(largest~=root) then
arr[root],arr[largest] = arr[largest],arr[root]
HeapBulid(arr,largest,size)
end
end
完整测试代码
function ArrInit(arr)
arr={3,1,9,4,5,2,7,9,6,11,65,89,32,45,94,0,66}
return arr
end
function ShowArr(arr)
local len = #arr;
for i = 1,len do
io.write(arr[i])
io.write(" ")
end
io.write("n");
end
function BubbleSort(arr)
local len = #arr;
for i = 1,len do
for j = 1,len-i do
if (a[j] < a[j+1]) then
a[j],a[j+1] = a[j+1],a[j];
end
end
end
end
function InsertSort(arr)
local len = #arr
for i = 2,len do
local temp = arr[i]
local j = i-1
while(j >= 1 and temp > arr[j]) do
arr[j+1] = arr[j]
j = j-1;
end
arr[j+1] = temp;
end
end
function SelectSort(arr)
local len = #arr
for i = 1,len-1 do
local maxNum = arr[i]
local maxIndex = i
for j = i,len do
if(arr[j] > maxNum) then
maxNum = arr[j]
maxIndex = j
end
end
if(i~=maxIndex) then
arr[i],arr[maxIndex] = arr[maxIndex],arr[i]
end
end
end
function QuickMainSort(arr,left,right)
if(left>=right) then
return
end
local i = left
local j = right
local temp = arr[left]
while(i<j) do
while(temp>=arr[j] and i<j ) do
j=j-1
end
while(temp<=arr[i] and i<j ) do
i=i+1
end
if(i<j) then
arr[i],arr[j] = arr[j],arr[i]
end
end
arr[left] = arr[i]
arr[i] = temp
QuickMainSort(arr,left,i-1)
QuickMainSort(arr,i+1,right)
end
function QuickSort(arr)
QuickMainSort(arr,1,#arr)
end
function Merge(arr,left,mid,right)
if(left>=right) then
return
end
local tab_temp ={}
local i=left
local k=mid+1
while(i<=mid and k<=right) do
if(arr[i]>arr[k]) then
table.insert(tab_temp,arr[i])
i=i+1
else
table.insert(tab_temp,arr[k])
k=k+1
end
end
while(i<=mid) do
table.insert(tab_temp,arr[i])
i=i+1
end
while(k<=right) do
table.insert(tab_temp,arr[k])
k=k+1
end
for j=left,right do
arr[j]=tab_temp[j-left+1]
end
end
function MergeMain(arr,left,right)
if(left<right) then
local mid = (left+right)//2
MergeMain(arr,left,mid)
MergeMain(arr,mid+1,right)
Merge(arr,left,mid,right)
end
end
function MergeSort(arr)
MergeMain(arr,1,#arr)
end
function ShellSort(arr)
local len = #arr
for gap=1,3 do --这里可以倒序 gap从3到1 令4-gap = gap;
for i=1,4-gap do
for j=i+4-gap,len do
local temp = arr[j]
local k = j-4+gap;
while(k>=1 and temp>arr[k]) do
arr[k+4-gap] = arr[k]
k=k-4+gap;
end
arr[k+4-gap] = temp
end
end
end
end
function HeapBulid(arr,root,size)
local left = root*2
local right = root*2+1
local largest = root
if(left<=size and arr[left] < arr[largest]) then
largest = left
end
if(right<=size and arr[right] < arr[largest])then
largest = right
end
if(largest~=root) then
arr[root],arr[largest] = arr[largest],arr[root]
HeapBulid(arr,largest,size)
end
end
function HeapSort(arr)
local len = #arr;
local i=len//2
while(i>=1) do
HeapBulid(arr,i,len)
i=i-1;
end
local j=len
while(j>1) do
arr[1],arr[j] = arr[j],arr[1]
j=j-1
HeapBulid(arr,1,j)
end
end
--Main Test
a={}
a=ArrInit(a)
io.write("NoSort:n")
ShowArr(a)
BubbleSort(a)
io.write("BubbleSort:n")
ShowArr(a)
a=ArrInit(a)
InsertSort(a)
io.write("InsertSort:n")
ShowArr(a)
a=ArrInit(a)
SelectSort(a)
io.write("SelectSort:n")
ShowArr(a)
a=ArrInit(a)
QuickSort(a)
io.write("QuickSort:n")
ShowArr(a)
a=ArrInit(a)
MergeSort(a)
io.write("MergeSort:n")
ShowArr(a)
a=ArrInit(a)
ShellSort(a)
io.write("ShellSort:n")
ShowArr(a)
a=ArrInit(a)
HeapSort(a)
io.write("HeapSort:n")
ShowArr(a)
a=ArrInit(a)
最后
以上就是文静冷风为你收集整理的Lua语言实现7种排序（冒泡排序，插入排序，选择排序，快速排序，归并排序，堆排序）的全部内容，希望文章能够帮你解决Lua语言实现7种排序（冒泡排序，插入排序，选择排序，快速排序，归并排序，堆排序）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复