寫在前面
- 推薦一個(gè)排序可視化網(wǎng)站：VisuAlgo
- 代碼里所有輸出都是通過下面這個(gè)輸出函數(shù)輸出的
function outNum( needOutNum )
for k,v in ipairs(needOutNum) do
print(v)
end
end
- lua里的#到這都成注釋了= =||||，所以就不貼代碼了私痹，直接貼圖
一、選擇排序
1. 原理
- 在未排序序列中找到最型彻巍（大）元素紊遵，存放到排序序列的起始位置
- 從剩余未排序元素中繼續(xù)尋找最小（大）元素侥蒙，然后放到已排序序列的末尾
2. 代碼實(shí)現(xiàn)
選擇排序
二暗膜、冒泡排序
1. 原理
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大鞭衩，就交換他們兩個(gè)
- 對每一對相鄰元素作同樣的工作学搜，從開始第一對到結(jié)尾的最后一對。這步做完后论衍，最后的元素會(huì)是最大的數(shù)瑞佩。
- 針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟坯台，直到?jīng)]有任何一對數(shù)字需要比較
2. 代碼實(shí)現(xiàn)
冒泡排序
3. 優(yōu)化代碼
- 記錄最后一次交換的位置炬丸，下一次交換就從這結(jié)束
-
記錄是否交換，如果沒有交換證明已經(jīng)有序了
冒泡排序優(yōu)化
三蜒蕾、插入排序
1. 原理
- 從第一個(gè)元素開始稠炬，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素滥搭，將該元素移到下一位置
- 重復(fù)步驟3酸纲，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟2~5
2. 代碼實(shí)現(xiàn)
插入排序
四、希爾排序
1. 原理
- 將整個(gè)待排元素序列分割成若干個(gè)子序列瑟匆，分別進(jìn)行插入排序
- 依次縮減增量再進(jìn)行排序
- 待整個(gè)序列中的元素基本有序（增量足夠忻銎隆）時(shí)，再對全體元素進(jìn)行一次直接插入排序
2. 代碼實(shí)現(xiàn)
希爾排序
五愁溜、歸并排序
1. 原理
- 遞歸將數(shù)組兩兩劃分
- 對劃分的數(shù)組分別進(jìn)行排序
- 合并排序好的數(shù)組
2. 代碼實(shí)現(xiàn)
- 遞歸版
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大于數(shù)組長度疾嗅，說明沒有right部分，不需要合并了
if (left<=#needSortTable and middle<=#needSortTable) then
mergeTable(left,middle,#needSortTable)
end
i = i + i
end
outNum(needSortTable)
end
六冕象、快速排序
1. 原理
- 挑選基準(zhǔn)值：從數(shù)列中挑出一個(gè)元素
- 分割：重新排序數(shù)列代承，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（與基準(zhǔn)值相等的數(shù)可以到任何一邊）渐扮。在這個(gè)分割結(jié)束之后论悴，對基準(zhǔn)值的排序就已經(jīng)完成
- 遞歸排序子序列：遞歸地將小于基準(zhǔn)值元素的子序列和大于基準(zhǔn)值元素的子序列排序
2. 代碼實(shí)現(xiàn)
快速排序
七掖棉、桶排序
1. 原理
- 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子
- 尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對應(yīng)的桶子去
- 對每個(gè)不是空的桶子進(jìn)行排序
- 從不是空的桶子里把項(xiàng)目再放回原來的序列中
2. 代碼實(shí)現(xiàn)
桶排序
八膀估、堆排序
1. 原理
- 最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整幔亥，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
- 創(chuàng)建最大堆（Build Max Heap）：將堆中的所有數(shù)據(jù)重新排序
- 堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算
2. 代碼實(shí)現(xiàn)
堆排序
九察纯、基數(shù)排序
1. 原理
- 求數(shù)據(jù)的最大位數(shù)
- 從個(gè)位數(shù)開始對每位數(shù)進(jìn)行排序帕棉，存放在桶中
- 從不是空的桶子里把值再放回原來的序列中
2. 代碼實(shí)現(xiàn)
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
