文章

常见排序算法的实现

发表于 更新于
作者 Klc 11 分钟阅读

排序

最近面试遇到手写排序的问题, 虽然记得原理但总有些细节不完善, 所以总结一下
只实现常见的几种排序: 冒泡, 快排, 堆排. 用C#,C++,lua多个语言实现

C#实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

internal class Program
{
    //冒泡排序
    static void Sort_Bubble<T>(T[] arr, Func<T, T, int>? cmp = null) where T : IComparable
    {
        if (cmp == null)
        {
            cmp = (a, b) => a.CompareTo(b);
        }

        int _length = arr.Length;
        for (int i = 0; i < _length - 1; ++i)
        {
            for (int j = i + 1; j < _length; ++j)
            {
                if (cmp(arr[i], arr[j]) > 0)
                {
                    (arr[i], arr[j]) = (arr[j], arr[i]);
                }
            }
        }
    }
    
    //快速排序
    static void SortQuick<T>(T[] arr, Func<T, T, int>? cmp = null) where T : IComparable
    {
        if (cmp == null)
        {
            cmp = (a, b) => a.CompareTo(b);
        }
        Random r = new Random();
        Action<int, int>? quickSort = null;
        quickSort = (int lIndex, int rIndex) =>
        {
            if (lIndex >= rIndex) return; //排序结束的情况

            int pivotIndex = r.Next(lIndex, rIndex + 1);
            (arr[pivotIndex], arr[lIndex]) = (arr[lIndex], arr[pivotIndex]);
            int originlIndex = lIndex;
            int originrIndex = rIndex;
            while (lIndex < rIndex)
            {
                while (lIndex < rIndex && cmp(arr[rIndex], arr[originlIndex]) >= 0) rIndex--;
                while (lIndex < rIndex && cmp(arr[lIndex], arr[originlIndex]) <= 0) lIndex++;
                if (lIndex != rIndex)
                {
                    (arr[lIndex], arr[rIndex]) = (arr[rIndex], arr[lIndex]);
                }
            }
            (arr[originlIndex], arr[rIndex]) = (arr[rIndex], arr[originlIndex]);
            quickSort(originlIndex, lIndex - 1);
            quickSort(lIndex + 1, originrIndex);
        };
        quickSort(0, arr.Length - 1);
    }

    //堆排序
    static void SortHeap<T>(T[] nums, Func<T, T, int>? cmp = null) where T : IComparable
    {
        if (cmp == null)
        {
            cmp = (a, b) => a.CompareTo(b);
        }

        int length = nums.Length;
        for (int i = length / 2; i >= 0; i--)
        {
            Sink(nums, i, length, cmp); //在倒数第二层结点一直往上， 从当前结点往下调整堆， 保证每一层都符合堆性质
        }
        for (int i = length - 1; i > 0; i--)
        {
            (nums[0], nums[i]) = (nums[i], nums[0]);
            Sink(nums, 0, i, cmp);
        }
    }

    static void Sink<T>(T[] nums, int currIndex, int length, Func<T, T, int> cmp) where T : IComparable //调整堆中当前位置的元素
    {
        T temp = nums[currIndex]; //保存当前结点
        for (int i = currIndex * 2 + 1; i < length; i = i * 2 + 1) //遍历两个子节点(currIndex*2+1和currIndex*2+2)
        {
            if (i + 1 < length && cmp(nums[i], nums[i + 1])<0) //如果有右孩子且右孩子的值大于左孩子， 那么就把右孩子和当前结点比较
            {
                i++;
            }
            if (cmp(nums[i], temp) <= 0) //如果右孩子比当前结点小，说明符合堆性质， 不作处理
            {
                break;
            }
            (nums[currIndex], nums[i]) = (nums[i], nums[currIndex]); //否则就把当前和右孩子交换， 一直到叶子结点
            currIndex = i;
        }
    }

    static void DisplayArr<T>(T[] arr)
    {
        Console.Write(string.Join(' ', arr));
        Console.WriteLine();
    }

    public static void Main()
    {
        int[] arr = { 33, 1, 111, 22, 55 };
        SortHeap(arr); //默认升序
        DisplayArr(arr);
        SortHeap(arr, (a, b) => -a.CompareTo(b)); //根据自定义方法降序
        DisplayArr(arr);
    }
}

lua实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

local arrx = { 33, 1, 111, 22, 55 }

--冒泡排序
local function Sort_Bubble(arr)
    local cmp = function(a, b)
        if a > b then
            return 1
        else
            return -1
        end
    end
    local _length = #arr;
    for i = 1, _length - 1, 1 do
        for j = 1, _length - i, 1 do
            if (cmp(arr[j], arr[j + 1]) > 0) then
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            end
        end
    end
    return arr
end

--快速排序
function Sort_Quick(arr, cmp)
    if (cmp == nil) then
        cmp = function(a, b)
            if a > b then
                return 1
            else
                return -1
            end
        end
    end

    _QuickSort = function(lIndex, rIndex)
        if lIndex >= rIndex then
            return
        end --排序结束的情况
        local _pivotIndex = math.random(lIndex, rIndex)
        arr[_pivotIndex], arr[lIndex] = arr[lIndex], arr[_pivotIndex]
        local _originlIndex = lIndex
        local _originrIndex = rIndex
        while lIndex < rIndex do
            while (lIndex < rIndex and cmp(arr[rIndex], arr[_originlIndex]) >= 0) do
                rIndex = rIndex - 1
            end

            while (lIndex < rIndex and cmp(arr[lIndex], arr[_originlIndex]) <= 0) do
                lIndex = lIndex + 1
            end

            if (lIndex ~= rIndex) then
                arr[lIndex], arr[rIndex] = arr[rIndex], arr[lIndex]
            end
        end
        arr[_originlIndex], arr[rIndex] = arr[rIndex], arr[_originlIndex]
        _QuickSort(_originlIndex, lIndex - 1)
        _QuickSort(lIndex + 1, _originrIndex)
    end

    _QuickSort(1, #arr)
    return arr
end

local function Sink(arr, currIndex, length, cmp)
    local _child = nil
    while currIndex * 2 <= length do
        _child = currIndex
        if (_child + 1 < length and cmp(arr[_child], arr[_child + 1]) < 0) then --如果有右孩子且右孩子的值大于左孩子， 那么就把右孩子和当前结点比较
            _child = _child + 1
        end

        if cmp(arr[_child], arr[currIndex]) <= 0 then --如果右孩子比当前结点小，说明符合堆性质， 不作处理
            break
        end
        arr[currIndex], arr[_child] = arr[_child], arr[currIndex] --否则就把当前和右孩子交换， 一直到叶子结点
        currIndex = _child
    end
end

--堆排序
function Sort_Heap(arr, cmp)
    if cmp == nil then
        cmp = function(a, b)
            if a > b then
                return 1
            else
                return -1
            end
        end
    end

    local _length = #arr
    for i = _length // 2, 1, -1 do
        Sink(arr, i, _length, cmp) --在倒数第二层结点一直往上， 从当前结点往下调整堆， 保证每一层都符合堆性质
    end
    for i = _length, 1, -1 do
        arr[1], arr[i] = arr[i], arr[1]
        Sink(arr, 1, i, cmp)
    end
end

arrx = Sort_Quick(arrx, function (a,b)
    return a<b and 1 or -1
end)
print(table.concat(arrx, ' '))

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

#include "algorithm"
#include "functional"
#include "iostream"
#include "random"

class Sort
{
public:
    template<typename T>
    static void Bubble(T arr[], int size, int (*cmp)(T, T) = NULL)
    {
        if (cmp == NULL)
        {
            cmp = [](T a, T b) -> int {return std::tie(a) < std::tie(b) ? -1 : 1; };// 默认递增
        }

        int _length = size;
        for (int i = 0; i < _length - 1; ++i)
        {
            for (int j = i + 1; j < _length; ++j)
            {
                if (cmp(arr[i], arr[j]) > 0)
                {
                    std::swap(arr[i], arr[j]);
                }
            }
        }
    };

    template<typename T>
    static void Quick(T arr[], int sz, int (*cmp)(T, T) = NULL)
    {
        if (cmp == NULL)
        {
            cmp = [](T a, T b) -> int {return std::tie(a) < std::tie(b) ? -1 : 1; };// 默认递增
        }

        int _length = sz;
        std::random_device seed;
        std::ranlux48 engine(seed());

        auto quickSort = [&, f = [&](auto&& self, int lIndex, int rIndex)
        {
            if (lIndex >= rIndex) return; //排序结束的情况

            std::uniform_int_distribution<int> distrib(lIndex, rIndex);
            int pivotIndex = distrib(engine);
            std::swap(arr[pivotIndex], arr[lIndex]);

            int originlIndex = lIndex;
            int originrIndex = rIndex;
            while (lIndex < rIndex)
            {
                while (lIndex < rIndex && cmp(arr[rIndex], arr[originlIndex]) >= 0) rIndex--;
                while (lIndex < rIndex && cmp(arr[lIndex], arr[originlIndex]) <= 0) lIndex++;
                if (lIndex != rIndex)
                {
                    std::swap(arr[lIndex], arr[rIndex]);
                }
            }
            std::swap(arr[originlIndex], arr[rIndex]);
            self(self, originlIndex, lIndex - 1);
            self(self, lIndex + 1, originrIndex);
        }](int _lIndex, int _rIndex)
        {
            f(f, _lIndex, _rIndex);
        };
        quickSort(0, _length - 1);
    };

    //堆排序
    template<typename T>
    static void SortHeap(T nums[], int sz, int (*cmp)(T, T) = NULL)
    {
        if (cmp == NULL)
        {
            cmp = [](T a, T b) -> int {return std::tie(a) < std::tie(b) ? -1 : 1; };// 默认递增
        }

        auto Sink = [&, f = [&](auto&& self, T nums[], int currIndex, int length, int (*cmp)(T, T))
        {
            T temp = nums[currIndex]; //保存当前结点
            for (int i = currIndex * 2 + 1; i < length; i = i * 2 + 1) //遍历两个子节点(currIndex*2+1和currIndex*2+2)
            {
                if (i + 1 < length && cmp(nums[i], nums[i + 1]) < 0) //如果有右孩子且右孩子的值大于左孩子， 那么就把右孩子和当前结点比较
                {
                    i++;
                }
                if (cmp(nums[i], temp) <= 0) //如果右孩子比当前结点小，说明符合堆性质， 不作处理
                {
                    break;
                }
                std::swap(nums[currIndex], nums[i]); //否则就把当前和右孩子交换， 一直到叶子结点
                currIndex = i;
            }
        }](T nums[], int currIndex, int length, int (*cmp)(T, T))
        {
            f(f, nums, currIndex, length, cmp);
        };

        int length = sz;
        for (int i = length / 2; i >= 0; i--)
        {
            Sink(nums, i, length, cmp); //在倒数第二层结点一直往上， 从当前结点往下调整堆， 保证每一层都符合堆性质
        }
        for (int i = length - 1; i > 0; i--)
        {
            std::swap(nums[0], nums[i]);
            Sink(nums, 0, i, cmp);
        }
    }

};

int main()
{
    int arr[] = { 33, 2, 111, 1, 33 };
    int size = sizeof(arr) / sizeof(arr[0]);
    auto cmp = [](int a, int b) {return std::tie(a) > std::tie(b) ? -1 : 1; };//递减排序

    //lambda与函数指针类型不同, 需要手动转化, 否则不能自动推导类型
    Sort::Quick(arr, size, (int(*)(int, int))cmp);

    //或者声明时给出具体类型
    int (*cmp2)(int, int) = cmp;
    Sort::Quick(arr, size, cmp2);

    //或者使用function, 需要把形参列表中类型也替换为std::function<T(T, T)>
    std::function<int(int, int)> func = cmp;
    //Sort::Quick(arr, size, func);

    int (*cmp3)(int, int) = [](int a, int b)->int { return std::tie(a) > std::tie(b) ? -1 : 1; };
    Sort::SortHeap(arr, size, cmp3);
    return 0;
}
Algorithm, Sort
CSharp algorithm Sort
本文由作者按照 CC BY 4.0 进行授权