陈留阳
0%

十大排序

发表于 更新于 分类于

从大一学 C 语言开始就一直听说有个叫做十大排序算法的东西，要涉及一些有趣的思想和数据结构什么的，听起来很厉害的样子，觉得好难就没去看过，只是调用 qsort 和 sort 之类的函数。

最近学一些东西的时候恰巧和十大排序打了交道，理解起来并不难，拖延了好久才去看真的挺遗憾的。然后学完后打算把十大排序总结记录下来。

所谓十大排序是十种比较经典，综合了很多经典思路的排序算法。分别是冒泡排序，选择排序，插入排序，希尔排序，归并排序，快速排序，堆排序，计数排序，桶排序，基数排序。

本篇文章的动画演示录制自VisualGo,panthema与USF

部分算法的介绍来自维基百科

以 C/C++混合风格实现

冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

实现的基本思路就是两个循环嵌套起来，比较相邻元素，将大的元素逐渐后移，小的元素就逐渐浮到了前面。

1
2
3
4
5
6
7
8
9
10
11
12
void BubbleSort(int array[], int len)
{
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len - i - 1; j++)
        {
            if (array[j] > array[j + 1])
            {
                swap(array[j], array[j + 1]);
            }
        }    }
}

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

当然，也可以同时选出最大元素和最小元素，将它们分别放入两边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void SelectionSort(int array[], int len)
{
    for (int i = 0; i < len; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < len; j++)
        {
            if (array[j] < array[minIndex])
            {
                minIndex = j;
            }
        }
        swap(array[i], array[minIndex]);
    }
}

插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertionSort(int array[], int len)
{
    for (int i = 1; i < len; i++)
    {
        int temp = array[i];
        int j = i - 1;
        for (; (j >= 0) && (array[j] > temp); j--)
        {
            array[j + 1] = array[j];
        }
        array[j + 1] = temp;
    }
}

希尔排序

希尔排序(Shell Sort)实际上是插入排序的一种变形。插入排序在比较的时候总是和前一个进行比较然后交换，而插入排序是从一个比较大的间隔起，逐渐缩短到一。

经典的希尔排序在取间隔的时候设置为 n/2，n/4，n/8，在不断缩小间隔进行插入排序。

引用来自维基百科的说法：

假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为 5 开始进行排序，我们可以通过将这列表放在有 5 列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时 10 已经移至正确位置了，然后再以 3 为步长进行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以 1 步长进行排序（此时就是简单的插入排序了）。

值得一提的是虽然希尔排序的作者 Donald Shell 最初建议的间隔是(1, 2, 4, … n/2)，但是间隔的选取只要是从大到小，最后到达 1 即可。目前为止已知的效率最优秀的间隔是 Sedgewick 提出的(1, 5, 19, 41, 109,…)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void ShellSort(int array[], int len)
{
    for (int gap = len >> 1; gap > 0; gap >>= 1)
    {
        for (int i = gap; i < len; i++)
        {
            int temp = array[i];
            int j = i - gap;
            for (; (j >= 0) && (array[j] > temp); j -= gap)
            {
                array[j + gap] = array[j];
            }
            array[j + gap] = temp;
        }
    }
}

归并排序

归并排序(Merge Sort)是一种采取分治法进行排序的算法。在我看来可以这样理解归并排序：

  1. 将两个有序数组合成一条有序数组；
  2. 若数组中只有一个元素则自然有序。

归并排序有多种实现方式，比较经常见到的有递归法和迭代法。相比而言，递归法比较容易理解。

对于一个长度为 n 的序列，递归方式的归并排序可以描述成：

  1. 排序序列前 n/2 与后 n/2；
  2. 合并前后两个有序序列；
  3. 排序完成
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
void MergeRecursive(int array[], int help[], int start, int end)
{
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    MergeRecursive(array, help, start1, end1); //对数组前一半进行排序
    MergeRecursive(array, help, start2, end2); //对数组后一半进行排序

    //合并两个有序数组
    int index = start;
    int start11 = start1, end11 = end1, start22 = start2, end22 = end2;
    while ((start1 <= end1) && (start2 <= end2))
    {
        help[index++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
    }
    while (start1 <= end1)
    {
        help[index++] = array[start1++];
    }
    while (start2 <= end2)
    {
        help[index++] = array[start2++];
    }

    //将合并后的结果复制回原数组。
    for (int i = start; i <= end; i++)
    {
        array[i] = help[i];
    }
}

void MergeSort(int array[], int len)
{
    int *help = new int[len];
    MergeRecursive(array, help, 0, len - 1);
    delete[] help;
}

递归法可以看作是归并排序的自顶向下的实现方式，而迭代法更多的体现的是自底向上的实现方法。

对于一个长度为 n 的序列，迭代方式的归并排序可以描述成：

  1. len = 1；
  2. 合并两两相邻的长度长度为 len 的序列；
  3. len *= 2；
  4. 如果 len < n,回到 2；
  5. 排序完成。
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
void MergeSort(int array[], int len)
{
    int *arr = array;
    int *help = new int[len];
    for (int dis = 1; dis < len; dis *= 2)
    {
        for (int start = 0; start < len; start += 2 * dis)
        {
            int low = start, mid = min(start + dis, len), high = min(start + 2 * dis, len);
            int start1 = start, end1 = mid;
            int start2 = mid, end2 = high;
            int index = start;
            while ((start1 < end1) && (start2 < end2))
            {
                help[index++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            }
            while (start1 < end1)
            {
                help[index++] = arr[start1++];
            }
            while (start2 < end2)
            {
                help[index++] = arr[start2++];
            }
        }
        swap(arr, help);
    }
    if (arr != array)
    {
        for (int i = 0; i < len; i++)
        {
            array[i] = arr[i];
        }
        help = arr;
    }
    delete[] help;
}

我认为在迭代法中最巧妙的一步是swap(arr, help)，交换了原数组与辅助数组的指针，这样做让两个数组轮流做为辅助数组，省去了将辅助数组复制回原数组的开销，只在最后排完序后判断一下是否是原序列即可。相当巧妙！

快速排序

快速排序(Quicksort)也是一种分治的排序算法。与归并相比，快速排序更注重与划分子问题，而归并排序更注重于合并子问题，因此在具体的思路上会有较大的不同。

对于一个数组来讲，快速排序可以被描述成：

  1. 如果数组长度小于等于 1，则排序完成；
  2. 选取数组中的一个元素，将所有小于该元素的元素放在数组前部分，所有大于该元素的元素放在数组后部分，该元素放在正中间；
  3. 对数组前一部分和后一部分进行排序；
  4. 排序完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void QuickSort(int array[], int len)
{
    if (len <= 1)
        return;
    int low = 1, high = len - 1;
    while (low <= high)
    {
        if (array[low] < array[0])
        {
            low++;
        }
        else
        {
            swap(array[low], array[high--]);
        }
    }
    swap(array[0], array[high]);
    QuickSort(array, low - 1);
    QuickSort(array + low, len - low);
}

2019年7月15日更新，使用标准库实现了更优雅的写法

1
2
3
4
5
6
7
8
9
void quicksort(ForwardIt first, ForwardIt last)
{
    if(first == last) return;
    auto pivot = *std::next(first, std::distance(first,last)/2);
    ForwardIt middle1 = std::partition(first, last, [pivot](const auto& em){ return em < pivot; });
    ForwardIt middle2 = std::partition(middle1, last, [pivot](const auto& em){ return !(pivot < em); });
    quicksort(first, middle1);
    quicksort(middle2, last);
}

堆排序

堆排序(Heap Sort)是一种借助数据结构堆的性质进行排序的算法。

由于堆本身可以使用数组进行实现，因此可以将数组堆化成一个大顶堆或者小顶堆，不断 pop 出堆顶元素并存起来，就是排序结果(大顶堆对应升序，小顶堆对应降序)。

堆化：

不断 pop：

在实际实现过程中，数组的首元素下标为 0，所以需要对堆的实现稍微做些调整。

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
void BuildMaxHeap(int array[], int father, int len)
{
    if (father >= len)
        return;
    int leftSon = (father << 1) + 1, rightSon = (father << 1) + 2;
    if (rightSon < len)
    {
        if (array[father] < max(array[leftSon], array[rightSon]))
        {
            if (array[rightSon] > array[leftSon])
            {
                swap(array[father], array[rightSon]);
                BuildMaxHeap(array, rightSon, len);
            }
            else
            {
                swap(array[father], array[leftSon]);
                BuildMaxHeap(array, leftSon, len);
            }
        }
    }
    else if (leftSon < len)
    {
        if (array[leftSon] > array[father])
        {
            swap(array[father], array[leftSon]);
            BuildMaxHeap(array, leftSon, len);
        }
    }
}

void HeapSort(int array[], int len)
{
    for (int i = len - 1; i >= 0; i--)
    {
        BuildMaxHeap(array, i, len);
    }
    for (int i = len - 1; i >= 0; i--)
    {
        swap(array[0], array[i]);
        BuildMaxHeap(array, 0, i);
    }
}

计数排序

计数排序(Counting Sort)是一种比较暴力，但是在一定场合下，效率又非常高的排序算法。

就如名字中的计数一样，计数排序的本质是使用额外的辅助空间记录下一个数字出现的次数，然后按照顺序返还会原数组。计数排序特别适应于数据相对集中，重复率特别大的情况，此时计数排序的效率可以达到很高。

在实际情况下，可以用多种方式处理负数数据，本次实现采用的是偏移的方式，将原数组的跨度映射到自 0 始的一段相同跨度的数组(有个特别神奇的操作是利用 C\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
void CountingSort(int array[], int len)
{
    int maxValue = array[0], minValue = array[0];
    for (int i = 1; i < len; i++)
    {
        maxValue = max(array[i], maxValue);
        minValue = min(array[i], minValue);
    }
    int length = maxValue - minValue + 1;
    int *help = new int[length];
    memset(help, 0, (length) * sizeof(int));
    for (int i = 0; i < len; i++)
    {
        help[array[i] - minValue]++;
    }
    ShowArray(help, length);
    for (int i = 0, j = 0; i <= maxValue - minValue; i++)
    {
        while (help[i]--)
        {
            array[j++] = i + minValue;
        }
    }
    delete[] help;
}

桶排序

桶排序(Bucket Sort)就有些一言难尽。

桶排序的具体思路是将原数组的元素在某个大小区域内的所有元素放在一个“桶”中，最后将所有的桶内元素再复制回原数组。

因为桶内元素的具体数量并不能提前确定，因此需要使用可以灵活调整大小的数据结构来实现桶，实际实现的时候，采取了链表来实现桶。

桶排序的一个关键是要保证将桶内元素复制回原数组时需要保证桶内的元素一定是有序的，而实现这一点的方式有很多种，既可以在装桶的时候采取插入排序，也可以在装桶结束后使用 链表版本的归并排序或者其他排序手段。

本次实现采取的是装桶过程中使用插入排序，并配合排序原理封装了一个简单的链表。

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
class Node
{
  public:
    Node();
    Node(int data, Node *next = nullptr);
    int data;
    Node *next;
};

Node::Node()
{
    this->next = nullptr;
}

Node::Node(int data, Node *next)
{
    this->data = data;
    this->next = nullptr;
}

void InsertNode(Node *head, Node *node)
{
    Node *iterator = head;
    for (; iterator->next != nullptr; iterator = iterator->next)
    {
        if (iterator->next->data > node->data)
        {
            break;
        }
    }
    node->next = iterator->next;
    iterator->next = node;
}

void BucketSort(int array[], int len)
{
    int maxValue = array[0], minValue = array[0];
    for (int i = 0; i < len; i++)
    {
        maxValue = max(maxValue, array[i]);
        minValue = min(minValue, array[i]);
    }
    const int bucketCount = 10;
    Node *buckets = new Node[bucketCount];
    int distance = (maxValue - minValue) / (bucketCount) + 1;
    for (int i = 0; i < len; i++)
    {
        int index = (array[i] - minValue) / distance;
        InsertNode(buckets + index, new Node(array[i]));
    }
    for (int i = 0, j = 0; i < bucketCount; i++)
    {
        for (Node *iterator = buckets[i].next; iterator != nullptr; iterator = buckets[i].next)
        {
            array[j++] = iterator->data;
            buckets[i].next = iterator->next;
            delete iterator;
        }
    }
    delete[] buckets;
}

基数排序

基数排序(Radix Sort)就有些意思了，它在原理上和计数排序有点类似，但是区别在于计数排序需要能容纳该数组所有元素的很多桶，而基数排序只需要十个桶，然后把元素按照每一位进行装桶，复制回原数组，再在高位装桶直到超过最大元素的位数。

基数排序有点像是使用桶排序对每一位进行排序后的结果。

有一点需要注意的是，向桶内放数和从桶内取数的顺序是刚好相反的，不然会破环由低位排序而形成的相对大小关系。

因此，需要一种可以灵活调整大小的线性结构，可以通过一端放数而从另一端取数。

或许双向链表比较符合期望，但实际上使用队列会更加合适而且容易实现，因此本次实现按照排序原理封装了一个简单的队列(亦可使用 STL 中的队列)。

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
class node
{
  public:
    node(int data, node *prev = nullptr, node *next = nullptr);
    int data;
    node *prev, *next;
};

class queue
{
  public:
    queue();
    void push(int data);
    int pop();
    bool empty();

  private:
    node *head;
};

node::node(int data, node *prev, node *next)
{
    this->data = data;
    this->prev = prev;
    this->next = next;
}

queue::queue()
{
    this->head = new node(-1);
    this->head->prev = this->head->next = this->head;
}

void queue::push(int data)
{
    node *temp = new node(data, this->head, this->head->next);
    this->head->next->prev = temp;
    this->head->next = temp;
}

int queue::pop()
{
    node *temp = this->head->prev;
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    int data = temp->data;
    delete temp;
    return data;
}

bool queue::empty()
{
    return this->head->next == this->head;
}

void RadixSort(int array[], int len)
{
    const int bucketCount = 10;
    queue *buckets = new queue[bucketCount];
    int maxValue = array[0];
    for (int i = 1; i < len; i++)
    {
        maxValue = max(maxValue, array[i]);
    }
    int loopTime = log10(maxValue);
    for (int i = 0, power = 10; i <= loopTime; i++, power *= 10)
    {
        for (int j = 0; j < len; j++)
        {
            buckets[array[j] % power / (power / 10)].push(array[j]);
        }
        for (int j = 0, k = 0; j < bucketCount; j++)
        {
            while (!buckets[j].empty())
            {
                array[k++] = buckets[j].pop();
            }
        }
    }
    delete[] buckets;
}

检测排序情况

十大排序基本上就是以上的介绍了，在博主本人实际实现的过程中，为了检测排序结果是否正确，也为了调试上的方便，特地实现了一个小小的检测程序用来验证排序算法的准确性，也一并记录到最后。

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
int *CreateArray(int len)
{
    static int *ret = nullptr;
    if (ret != nullptr)
    {
        delete ret;
    }
    ret = new int[len];
    for (int i = 0; i < len; i++)
    {
        ret[i] = rand() % 10000;
    }
    return ret;
}

int *CopyArray(int *array, int len)
{
    int *ret = new int[len];
    for (int i = 0; i < len; i++)
    {
        ret[i] = array[i];
    }
    return ret;
}

bool CompArray(int array1[], int array2[], int len)
{
    for (int i = 0; i < len; i++)
    {
        if (array1[i] != array2[i])
        {
            return false;
        }
    }
    return true;
}

void ShowArray(int array[], int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << array[i] << ",";
    }
    cout << endl;
}

int main()
{
    int len;
    srand(time(NULL));
    // srand(1);
    int T = rand() % 100 + 100;
    // int T = 1;
    while (T--)
    {
        // len = 5;
        len = rand() % 10 + 1;
        int *array = CreateArray(len);

        // int array[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        // len = sizeof(array) / sizeof(array[0]);

        int *temp1 = CopyArray(array, len);
        int *temp2 = CopyArray(array, len);

        // BubbleSort(temp1, len);
        // SelectionSort(temp1, len);
        // InsertionSort(temp1, len);
        // ShellSort(temp1, len);
        // MergeSort(temp1, len);
        // QuickSort(temp1, len);
        // HeapSort(temp1, len);
        // CountingSort(temp1, len);
        // BucketSort(temp1, len);
        // RadixSort(temp1, len);

        sort(temp2, temp2 + len);
        if (!CompArray(temp1, temp2, len))
        // if (true)
        {
            ShowArray(array, len);
            ShowArray(temp1, len);
            ShowArray(temp2, len);
            cout << endl;
        }
        delete temp1;
        delete temp2;
    }
    return 0;
}

完结撒花！！
★,°:.☆(￣ ▽ ￣)/$:.°★