算法参考：

上面这篇文章对快排讲解得不错。快排概念详述请点上面链接。

记录一下，用lua实现的快排，以及一些注意的地方。

 

交换函数：

function Swap(tab, i, j)    local temp = tab[i];    tab[i] = tab[j];    tab[j] = temp;end

一、左右指针法：

-- 左右指针法-- 最后一个数为枢轴function PartSort(tab, left, right)    local key = right;    while left < right do         -- 必须先由左向右遍历        while left < right and tab[left] <= tab[key] do             left = left + 1;        end        -- 然后由右向左遍历        while left < right and tab[right] >= tab[key] do             right = right - 1;        end        if left < right then             Swap(tab, left, right);        else            Swap(tab, left, key);        end    end    return left;end

以最后一个值为key的话，必须从左边开始遍历。为什么必须从左边开始遍历？因为是以最右的元素做枢轴。回答这个问题之前，首先要知道为什么内层的while的循环还要 left < right 判断，这是因为不加的话，left就有可能和key重合了（如果key是当前片段最大的数），然后left再加1就越界了。 好，然后当while循环有了这个判断之后，外层循环的最后，必然会走到left == right。而如果不考虑特殊情况，一遍排序的最后，就是key跳到片段中间把片段分成小于key和大于key的两个子片段，而从左边开始，left和right最终停留的地方就是大于key的结点，交换left和key的位置，刚好把大于key的这个值调到了后面的片段。而如果从右开始，则停留在了比key小的地方，交换后就把一个比key小的值调到了片段后面。（这个地方我也只是意会，不晓得怎么用通俗语言描述出来，望指教）。同理，如果以最左的元素作为枢轴，那就是要从右边开始遍历。

 

二、挖坑法：

-- 挖坑法function PartSort(tab, left, right)    local sign = tab[left];    while left < right do         while left < right and tab[right] >= sign do             right = right - 1;        end        tab[left] = tab[right];        while left < right and tab[left] <= sign do             left = left + 1;        end        tab[right] = tab[left];    end    tab[left] = sign;    return left;end

挖坑法，其实叫成“填坑法”更好理解？把该数据结构想象成一排箱子，先空出第一个箱子（把里面的值放旁边做参考），然后从右边开始查找，有小于参考的就填到空箱中。此时，右边就多了一个空箱（此空箱的右边，如果有，都是大于参考的值），再从左边开始查找，如果有大于参考的值就填到右边的空箱中，如此反复。到最后，左边查找的指针和左边查找的指针相遇了，就把最先提出来的值填到最后的空箱中。

 

三、前后指针法：

-- 前后指针-- 以最右元素为keyfunction PartSort(tab, left, right)    if left < right then         local cur = left;        local pre = left - 1;        while cur < right do             -- 如果cur比最右的元素大，就不会进入这个if语句，pre就停滞了（停滞在第一个比right大的元素的前一个位置）            if tab[cur] < tab[right] then                -- pre + 1 有两种结果                -- 1. pre+1 = cur，说明pre 一直跟在cur后面，没有停滞过，即pre和cur之间，全是小于right的元素                -- 2. pre+1 < cur, 说明pre 停滞过，没有跟上cur，也就是说pre和cur之间有大于right的元素，由于是当cur遇到大于right的值pre就停滞了                --    所以，pre指向的还是小于right的元素，停滞的后一个元素（pre+1）才是大于right的元素。                --    把cur指向的小于right的元素和pre+1大于right的元素对调。此时的pre=pre+1指向的元素又成了小于right的元素了                pre = pre + 1;                if pre ~= cur then                     Swap(tab, pre, cur);                end            end            cur = cur + 1;        end        -- 由上可知，pre+1是指向大于right的元素，把它和right交换位置        -- 即把right放到了pre=pre+1的位置，就得到了以right元素为分界的 左边小于right, 右边大于right的两个部分        pre = pre + 1;        Swap(tab, pre, right);        return pre;    end    return -1;end

这种方法比较有趣了。注释比较多，就不啰嗦了。

 

快排算法有点忘了，复习一下，感谢开头提到的文章的博主。整理的不错。

 

测试代码：

--local nums = {8, 1, 7, 6, 5, 13, 1, 3, 6, 25, 87, 9, 3, 6, 8, 17, 22, 102, 7, 31, 6};local nums = {
   8, 1, 7, 6, 5, 13};function QuickSort(tab, left, right)    if left >= right then         return;    end    local index = PartSort(tab, left, right);   -- print(index);    QuickSort(tab, left, index - 1);    QuickSort(tab, index + 1, right);endQuickSort(nums, 1, #nums); for _, v in ipairs(nums) do     print(v);end