排序算法

昵称70747151 2020-07-03

展开全文

一插入排序（Insertion sort)
该算法比较直接，类比扑克牌排序，具体如下：
1 桌面上的扑克牌始终是乱序的，手上的扑克牌始终是有序的；
2 当从桌面上拿到一张扑克牌后，比较该张扑克牌与手中扑克牌的大小，并在合理的位置插入扑克牌；
3 当桌面上所有扑克牌均在手上时，排序完成。

 1 void InsertionSort(std::vector<int>& unsorted, std::vector<int>& sorted)
 2 {
 3     int sz = unsorted.size();
 4     if (sz <= 0)
 5         return;
 6 
 7     for (int i = 1; i < sz; ++i)
 8     {
 9         for (int j = 0; j < i; ++j)
10         {
11             if (unsorted[i] < unsorted[j])
12             {
13                 int temp = unsorted[i];
14                 for (int k = i; k > j; --k)
15                     unsorted[k] = unsorted[k - 1];
16                 unsorted[j] = temp;
17             }
18         }
19     }
20 
21     sorted = unsorted;
22 }

该算法复杂度为N*N，运行效率很低。

二归并排序(Merge sort)
针对单个元素数组，该数组是有序的；然后一次合并相邻的两个单元素数组，形成两个有序元素的数组；继续以上过程，直到合并为整个大数组。
假设待排序数组为array[N]，其算法如下：
1 对数组进行第一次扫描，使array[0...1]有序，...，使array[N-2...N-1]有序；
2 对1形成的新数组进行第二次扫描，使array[0...3]有序，...，使array[N-4...N-1]有序；
3 对2形成的新数组进行第三次扫描，使array[0...7]有序，...，使array[N-8...N-1]有序；
4 重复以上过程，直到整个数组有序。

 1 void MergeSort(std::vector<int>& unsorted, std::vector<int>& sorted)
 2 {
 3     int sz = unsorted.size();
 4     if (sz <= 0)
 5         return;
 6 
 7     int merge_sz = 1;
 8     int src_idx = 0;
 9     std::vector<int> temp[2];
10     temp[0] = unsorted;
11     while (merge_sz < sz)
12     {
13         int dst_idx = 1 - src_idx;
14         temp[dst_idx].clear();
15         for (int i = 0; i < sz; i += merge_sz * 2)
16         {
17             int start1 = i;
18             int end1 = start1 + merge_sz < sz ? start1 + merge_sz : sz;
19             int start2 = end1;
20             int end2 = start2 + merge_sz < sz ? start2 + merge_sz : sz;
21             while (start1 < end1 || start2 < end2)
22             {
23                 if (start1 < end1 && start2 < end2)
24                 {
25                     if (temp[src_idx][start1] < temp[src_idx][start2])
26                     {
27                         temp[dst_idx].push_back(temp[src_idx][start1]);
28                         ++start1;
29                     }
30                     else
31                     {
32                         temp[dst_idx].push_back(temp[src_idx][start2]);
33                         ++start2;
34                     }
35                 }
36                 else
37                 {
38                     if (start1 < end1)
39                     {
40                         for (int j = start1; j < end1; ++j)
41                             temp[dst_idx].push_back(temp[src_idx][j]);
42                         start1 = end1;
43                     }
44 
45                     if (start2 < end2)
46                     {
47                         for (int j = start2; j < end2; ++j)
48                             temp[dst_idx].push_back(temp[src_idx][j]);
49                         start2 = end2;
50                     }
51                 }
52             }
53         }
54 
55         src_idx = 1 - src_idx;
56         merge_sz *= 2;
57     }
58 
59     sorted = temp[src_idx];
60 }

该算法时间复杂度为N*logN，运行效率较高。

三堆排序(heap sort)

完全二叉树可以使用线性列表实现，最大堆（或最小堆）可以通过完全二叉树实现，这样就实现了对元素的线性访问。

堆排序主要有以下内容：

1 将乱序数组形成堆结构；

2 成堆的线性数组的第一个元素即为最值元素；

3 使用最后一个元素替换第一个元素，并抛弃最后一个元素；

4 对3形成的新数组，不再满足堆条件（single violation)，校正堆违例；

5 进入2，直到堆中只有一个元素使退出。

 1 void HeapSort(std::vector<int>& unsorted, std::vector<int>& sorted)
 2 {
 3     int sz = unsorted.size();
 4     if (sz <= 0)
 5         return;
 6 
 7     // 构造max-heap
 8     for (int i = (sz - 1) / 2; i >= 0; --i)
 9     {
10         // 子树构造max-heap
11         int p = i;
12         int l = p * 2 + 1;
13         int r = l + 1;
14         while (l < sz)
15         {
16             int max_idx = l;
17             if (r < sz && unsorted[r] > unsorted[l])
18                 max_idx = r;
19             if (unsorted[max_idx] > unsorted[p])
20             {
21                 int temp = unsorted[p];
22                 unsorted[p] = unsorted[max_idx];
23                 unsorted[max_idx] = temp;
24 
25                 p = max_idx;
26                 l = p * 2 + 1;
27                 r = l + 1;
28             }
29             else
30                 break;
31         }
32     }
33 
34     // 循环提取最大元素
35     int heap_sz = sz;
36     while (heap_sz > 1)
37     {
38         // 提取0位元素（最大数），并将末位元素填充到0位
39         --heap_sz;
40         int temp = unsorted[0];
41         unsorted[0] = unsorted[heap_sz];
42         unsorted[heap_sz] = temp;
43 
44         // 校正堆结构单违例(correct single violation)
45         int p = 0;
46         int l = p * 2 + 1;
47         int r = l + 1;
48         while (l < heap_sz)
49         {
50             int max_idx = l;
51             if (r < heap_sz && unsorted[r] > unsorted[l])
52                 max_idx = r;
53             if (unsorted[max_idx] > unsorted[p])
54             {
55                 int temp = unsorted[p];
56                 unsorted[p] = unsorted[max_idx];
57                 unsorted[max_idx] = temp;
58 
59                 p = max_idx;
60                 l = p * 2 + 1;
61                 r = l + 1;
62             }
63             else
64                 break;
65         }
66     }
67 
68     sorted = unsorted;
69 }