前言
冒泡、冒泡改進、雞尾酒、快速……
話說，用lua做這些算法不會很奇怪嗎？也許有lua子產品可以進行更快的排序吧！在寫這篇也算是學習（複習）一下lua了，在實作了幾個排序後可能會加一下特殊點的文法。
（用的是sublime text編譯）
基本顯示
print('hello lua developer\n基本顯示')
a={1,8,9,10,'a',3,2,6,7,4,5,'hello'} --lua資料結構，表table,可代替類
print(#a)
--[[
多行注釋
#a表示求a中的數字或字元串的個數
..表示字元串的拼接
]]
for i=1,#a do --單行注釋 預設步長為1
io.write(i..'>') --輸出後沒換行
for j=1,i do
io.write(a[j]..' ')
end
print() --輸出後有換行
end
輸出為
hello lua developer
基本顯示
12
1>1
2>1 8
3>1 8 9
4>1 8 9 10
5>1 8 9 10 a
6>1 8 9 10 a 3
7>1 8 9 10 a 3 2
8>1 8 9 10 a 3 2 6
9>1 8 9 10 a 3 2 6 7
10>1 8 9 10 a 3 2 6 7 4
11>1 8 9 10 a 3 2 6 7 4 5
12>1 8 9 10 a 3 2 6 7 4 5 hello
[Finished in 0.1s]
冒泡排序
一組亂序的資料，通過兩兩相鄰的交換直到全部排序完成！
就像氣泡從水裡升起一樣！
如果外部索引從頭到尾刷過去，那麼内部索引就像上面那樣，從頭到尾且長度逐漸減少。之是以這樣是因為第一步就把最大的排到了最後，第二步就把第二大的排到了倒數第二個，是以内部索引重新整理的長度就沒必要去刷已排序完成的部分了。
如果外部索引的重新整理順序是從尾到頭，那麼内部索引就相反。
- lua語言是從1開始索引的，但是差別不大！
print('hello lua developer\n冒泡排序')
local function showArray(arr) --局部函數
for i=1,#arr do
io.write(arr[i])
--等距輸出
if arr[i]>9 then
io.write(' ')
else
io.write(' ')
end
end
print()
end
arr={1,8,9,10,3,2,6,7,4,5}
showArray(arr)
for i=1,#arr do
for j=1,#arr-i do
if arr[j]>arr[j+1] then
temp=arr[j]
arr[j]=arr[j+1]
arr[j+1]=temp
end
end
end
showArray(arr)
輸出為
hello lua developer
冒泡排序
1 8 9 10 3 2 6 7 4 5
1 2 3 4 5 6 7 8 9 10
[Finished in 0.3s]
冒泡排序改進1，提前結束
内部索引第一輪是從開頭重新整理到末尾，最後一輪是重新整理第一個到第二個，但是如果到最後一輪前，前面兩個就已經是排序好的了，那麼最後一輪就是浪費！
是以說，需要提前結束排序——在一輪内部重新整理沒有交換元素的情況下（已經排序完成）
for i=1,#arr do
isSorted=true
for j=1,#arr-i do
if arr[j]>arr[j+1] then
temp=arr[j]
arr[j]=arr[j+1]
arr[j+1]=temp
isSorted=false --有元素交換，沒有排序完
end
end
if isSorted then --上一輪沒有元素交換，已經排序完成
break
end
end
冒泡排序改進2，設定有序邊界
之前是提前結束，算是設定了左邊界，現在我們來設定右邊界。
每次開始的階段都是從頭到尾，這也不xing哎！我們可以設定從頭到sortBorder——比如本來是重新整理到7，現在設定了右邊界後重新整理到4，當然是在5，6,7都排序好時，這樣效率就更高了點。
lastExchangeIndex=1
sortBorder=#arr-1
for i=1,#arr do
isSorted=true
for j=1,sortBorder do
if arr[j]>arr[j+1] then
temp=arr[j]
arr[j]=arr[j+1]
arr[j+1]=temp
isSorted=false --有元素交換，沒有排序完
lastExchangeIndex=j --更新為最後一次交換元素的位置
end
end
sortBorder=lastExchangeIndex --更新邊界
if isSorted then --上一輪沒有元素交換，已經排序完成
break
end
end
雞尾酒排序
左右都在冒泡，左邊冒一會兒泡，右邊冒一會兒泡，就像搖雞尾酒一樣（大概吧）
雞尾酒排序就是冒泡排序·改，可以在大部分元素已經有序的情況下，發揮其優勢！
for i=1,#arr/2 do
isSorted=true
--從左到右
for j=i,#arr-i do
if arr[j]>arr[j+1] then
temp=arr[j]
arr[j]=arr[j+1]
arr[j+1]=temp
isSorted=false
end
end
if isSorted then
break
end
--從右到左
for j=#arr-i+1,i+1,-1 do
if arr[j-1]>arr[j] then
temp=arr[j]
arr[j]=arr[j-1]
arr[j-1]=temp
isSorted=false
end
end
if isSorted then
break
end
end
雞尾酒排序改進1，設定有序邊界
leftBorder=2
leftLastExchangeIndex=#arr
rightBorder=#arr-1
rightLastExchangeIndex=1
for i=1,#arr/2 do
isSorted=true
--從左到右
for j=leftBorder,rightBorder do
if arr[j]>arr[j+1] then
temp=arr[j]
arr[j]=arr[j+1]
arr[j+1]=temp
isSorted=false
rightLastExchangeIndex=j
end
end
rightBorder=rightLastExchangeIndex
if isSorted then
break
end
--從右到左
for j=rightBorder,leftBorder,-1 do
if arr[j-1]>arr[j] then
temp=arr[j]
arr[j]=arr[j-1]
arr[j-1]=temp
isSorted=false
leftLastExchangeIndex=j
end
end
leftBorder=leftLastExchangeIndex
if isSorted then
break
end
end
快速排序
快速排序有好幾種實作的方法，總的來說，利用了分治的思想的排序就是快速排序！
分治類似于二分法，一分二，二分四，四份八
雙邊循環的快速排序
先從一組資料中取一個做基準元素，一般取第一個或者是随機取一個。
然後設定兩個指針，一個從頭重新整理到尾，一個從尾重新整理到頭，左邊的指針找到大于基準元素的，右邊找到小于基準元素的，然後交換一下——這樣就可以實作把小于基準元素的都放一邊，然後遞歸下去，就可以把整個資料都排序好！
local function partition(arr,startIndex,endIndex)
--[[
取第一個位置的元素做基準元素
當然，如果第一個元素是最大的或最小的，時間複雜度就很高了
]]
pivot=arr[startIndex]
leftPointer=startIndex --左指針，負責在左邊找大于基準元素的
rightPointer=endIndex --右指針，負責在右邊找小于基準元素的
while leftPointer~=rightPointer do --lua不等于為~=
while leftPointer<rightPointer and arr[rightPointer]>pivot do
rightPointer=rightPointer-1
end
while leftPointer<rightPointer and arr[leftPointer]<=pivot do
leftPointer=leftPointer+1
end
--找到了,把小的元素放到左邊，大的元素放到右邊
if leftPointer<rightPointer then
temp=arr[leftPointer]
arr[leftPointer]=arr[rightPointer]
arr[rightPointer]=temp
end
end
--從循環裡出來時，leftPointer和rightPointer重合了，是以把基準元素（第一個元素）交換到中間去
arr[startIndex]=arr[leftPointer]
arr[leftPointer]=pivot
--傳回中間元素
return leftPointer
end
local function quicksort(arr,startIndex,endIndex)
if startIndex>=endIndex then --遞歸結束條件，一般都放前面
return
end
--取得基準元素，并排序
pivotIndex=partition(arr,startIndex,endIndex)
--根據基準元素，分成兩個部分進行遞歸
quicksort(arr,startIndex,pivotIndex-1)
quicksort(arr,pivotIndex+1,endIndex)
end
arr={1,8,9,10,3,2,6,7,4,5}
showArray(arr)
quicksort(arr,1,#arr)
showArray(arr)
輸出
hello lua developer
快速排序
1 8 9 10 3 2 6 7 4 5
1 2 3 4 5 6 7 8 9 10
[Finished in 0.1s]
單邊循環的快速排序
相似的道理，沒必要設定兩個指針，一個指針也可以。在左邊設定一個指針，從左重新整理到右，遇到比基準大的就繼續右移，遇到小于基準的就交換到此指針左邊去！
local function partition(arr,startIndex,endIndex)
pivot=arr[startIndex]
mark=startIndex
--從第二個元素開始往右刷
for i=startIndex+1,endIndex do
if arr[i]<pivot then --每次遇到一個小于基準的，就把它交換到mark左邊
mark=mark+1
temp=arr[mark]
arr[mark]=arr[i]
arr[i]=temp
end
end
--mark指針停住了，意思是已經把小的放在了左邊，大的放在了右邊
--是以，此時把基準元素交換到mark位置來
arr[startIndex]=arr[mark]
arr[mark]=pivot
return mark
end
非遞歸的快速排序
遞歸與棧可以互相代替，是以不用函數遞歸就用棧的抛出和壓進！
先用lua子產品編寫的方法做一個stack的資料結構，不止可以壓入資料，還能壓入對象！
這處的難點在于如何拷貝table！
- 我隻做了一個簡單的儲存資料的棧，沒有實作儲存表的功能┭┮﹏┭┮
--[[
用lua做的資料結構棧module.lua
lua中的基本類型、函數都是值傳遞，隻有表是引用傳遞
直接用stack=require "stack"來接收子產品，可以得到預設的一個空棧
想要拷貝的話就用a=copy(stack)
lua中的#table隻算其中的數字和字元串的數量
]]
local module={}
module.info='[email protected]'
module.top=0 --記的是棧中的一級總數，如果某個元素是表，那麼下面的元素不計
function push(self,data)
--print('push')
if type(data)~='number' then
print('error:data isn\'t number')
return -1
end
self.top=self.top+1
self[self.top]=data
end
function pop(self)
--print('pop')
if self.top==0 then
print('error:top is zero, can\'t pop data')
return -1
end
data=self[self.top]
table.remove(self) --預設删除最後一個元素
self.top=self.top-1
return data
end
function isEmpty(self)
--print('isEmpty')
return self.top==0
end
function getNum(self)
return self.top
end
function showArray(self)
io.write('showArray>')
for i=1,#self do
io.write(self[i])
--等距輸出
if self[i]>9 then
io.write(' ')
else
io.write(' ')
end
end
print()
end
--拷貝一個表
function copy(self)
local function table_copy(src, dst)
for k,v in pairs(src) do
if type(v) == "table" then
dst[k] = {}
table_copy(v, dst[k])
else
dst[k] = v
end
end
end
local dst = {}
table_copy(self, dst)
return dst
end
return module
如何使用子產品 ⇓ \Downarrow ⇓
stack=require "stack"
print(stack.info)
push(stack,3)
push(stack,4)
push(stack,5)
push(stack,6)
showArray(stack)
print(pop(stack))
輸出為
[email protected]
showArray>3 4 5 6
6
[Finished in 0.3s]
非遞歸的快速排序，其中的partition可以是雙邊循環、單邊循環
stack=require "stack"
local function quicksort(arr,startIndex,endIndex)
local quicksort_stack=copy(stack)
--棧頂元素入棧
push(quicksort_stack,startIndex)
push(quicksort_stack,endIndex)
while isEmpty(quicksort_stack)==false do
--出棧得到起止下标
p2=pop(quicksort_stack)
p1=pop(quicksort_stack)
--得到基準元素位置
pivot=partition(arr,p1,p2)
--根據基準元素分成兩部分
if p1<pivot-1 then
push(quicksort_stack,p1)
push(quicksort_stack,pivot-1)
end
if pivot+1<p2 then
push(quicksort_stack,pivot+1)
push(quicksort_stack,p2)
end
end
end
堆排序
--[[
lua做的資料結構堆heap.lua
]]
local module={}
module.info='[email protected]'
--節點下沉
function downAdjust(self,parentIndex,len)
temp=self[parentIndex]
--以1作為開始的話，左孩子就是下面這樣
childIndex=2*parentIndex
while childIndex<=len do
--如果有右孩子，且右孩子大于左孩子，就定位到右孩子
if childIndex+1 <= len and self[childIndex+1]>self[childIndex] then
childIndex=childIndex+1
end
--如果父節點大于任何一個孩子的值，就跳出
if temp >= self[childIndex] then
break
end
--無需真正交換，指派即可
self[parentIndex]=self[childIndex]
parentIndex=childIndex
childIndex=2*parentIndex
end
self[parentIndex]=temp
end
function showArray(self)
io.write('showArray>')
for i=1,#self do
io.write(self[i])
--等距輸出
if self[i]>9 then
io.write(' ')
else
io.write(' ')
end
end
print()
end
--堆排序
function heapSort(self)
--1，把無序數組變成最大堆
for i=(#self)/2,1,-1 do
downAdjust(self,i,#self)
end
showArray(self)
--2，循環删除堆頂元素，移動到尾部，調整堆産生新的堆頂
for i=#self,1,-1 do
temp=self[i]
self[i]=self[1]
self[1]=temp
downAdjust(self,1,i-1) --堆的長度在減少，意思是末尾的被排序好了的就不算在堆内了
end
end
return module
使用
require "heap"
print('hello lua developer\n堆排序')
arr={1,8,9,10,3,2,6,7,4,5}
showArray(arr)
heapSort(arr)
showArray(arr)
輸出為
hello lua developer
堆排序
showArray>1 8 9 10 3 2 6 7 4 5
showArray>10 8 9 7 5 2 6 1 4 3
showArray>1 2 3 4 5 6 7 8 9 10
[Finished in 0.2s]
參考：《漫畫算法》