排序算法整理(C++版本)

发表于 | 分类于 | 本页总阅读量 次

排序算法说明

排序的定义

对某一序列对象根据某个关键字进行排序

排序中的术语

  • 稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
  • 不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
  • 内排序 ：所有排序操作都在内存中完成；
  • 外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
  • 时间复杂度 ： 一个算法执行所耗费的时间。
  • 空间复杂度 ：运行完一个程序所需内存的大小。

算法总结

排序算法总结

  • n是数据规模
  • k是桶的个数
  • In-Place是占用常数内存，无额外内存
  • Out-Place 占用额外内存

算法分类

排序算法分类

比较排序算法和非比较排序算法的区别

常见的快速排序、归并排序、堆排序、冒泡排序 等属于比较排序 。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置 。

在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。

比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

计数排序、基数排序、桶排序则属于非比较排序 。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置 。

非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。

非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

void printVector(vector<int> &numbers)
{
    for (int i = 0; i < numbers.size(); i++)
    {
        cout << numbers[i] << ' ';
    }
    cout << endl;
    return;
}
vector<int> bubbleSort(vector<int> &numbers)
{
    if (numbers.empty())
        return numbers;
    int temp;
    for (int i = 0; i < numbers.size(); i++)
    {
        for (int j = 0; j < numbers.size() - 1; j++)
        {
            if (numbers[j + 1] < numbers[j])
            {
                temp = numbers[j + 1];
                numbers[j + 1] = numbers[j];
                numbers[j] = temp;
            }
        }
    }
    return numbers;
}

vector<int> selectionSort(vector<int> &numbers)
{
    if (numbers.empty())
        return numbers;
    int temp;
    for (int i = 0; i < numbers.size(); i++)
    {
        for (int j = i; j < numbers.size(); j++)
        {
            if (numbers[i] > numbers[j])
            {
                temp = numbers[j];
                numbers[j] = numbers[i];
                numbers[i] = temp;
            }
        }
    }
    return numbers;
}

vector<int> InsertionSort(vector<int> &numbers)
{
    if (numbers.empty())
        return numbers;
    int current;
    for (int i = 1; i < numbers.size(); i++)
    {
        int j;
        current = numbers[i];
        for (j = i; j >= 1; j--)
        {
            if (current < numbers[j - 1])
            {
                numbers[j] = numbers[j - 1];
            }
            else
            {
                break;
            }
        }
        numbers[j] = current;
    }
    return numbers;
}

vector<int> ShellSort(vector<int> &numbers)
{
    if (numbers.empty())
        return numbers;
    int len = numbers.size();
    int gap = len / 2;
    int temp;
    while (gap > 0)
    {
        for (int i = gap; i < len; i++)
        {
            temp = numbers[i];
            int preindex = i - gap;
            while (preindex >= 0 && numbers[preindex] > temp)
            {
                numbers[preindex + gap] = numbers[preindex];
                preindex -= gap;
            }
            numbers[preindex + gap] = temp;
        }
        gap = gap / 2;
    }
    return numbers;
}

void MergeSort(vector<int> &numbers, size_t l, size_t r)
{
    if (numbers.empty() || l >= r)
        return;
    int mid = (l + r) >> 1;
    MergeSort(numbers, l, mid);
    MergeSort(numbers, mid + 1, r);
    int i = l, j = mid + 1;
    vector<int> temp;
    while (i <= mid && j <= r)
    {
        if (numbers[i] < numbers[j])
        {
            temp.push_back(numbers[i++]);
        }
        else
        {
            temp.push_back(numbers[j++]);
        }
    }
    while (i <= mid)
    {
        temp.push_back(numbers[i++]);
    }
    while (j <= r)
    {
        temp.push_back(numbers[j++]);
    }
    for (int i = l, j = 0; i <= r; i++, j++)
    {
        numbers[i] = temp[j];
    }
}

void QuickSort(vector<int> &numbers, size_t l, size_t r)
{
    if (numbers.empty() || l >= r)
        return;
    int i = l, j = r, mid = numbers[l + (r - l) / 2];
    while (i < j)
    {
        while (numbers[i] < mid)
        {
            i++;
        };
        while (numbers[j] > mid)
        {
            j--;
        };
        if (i < j)
        {
            swap(numbers[i], numbers[j]);
        }
    };

    QuickSort(numbers, l, j);
    QuickSort(numbers, j + 1, r);
}

class HeapSort
{
public:
    vector<int> numbers;
    HeapSort(vector<int> &v) : numbers(v){};
    void AdjustHeap(int node, int len)
    {
        int index = node;
        int child = 2 * index + 1;
        while (child < len)
        {
            if (child + 1 < len && numbers[child] < numbers[child + 1])
            {
                child++;
            }
            if (numbers[index] >= numbers[child])
                break;
            swap(numbers[index], numbers[child]);
            index = child;
            child = 2 * index + 1;
        }
    };
    void MakeHeap()
    {
        int len = numbers.size();
        for (int i = numbers.size() / 2; i >= 0; i--)
        {
            AdjustHeap(i, len);
        }
    };

    void Sort()
    {
        if (numbers.empty())
            return;
        MakeHeap();
        for (int i = numbers.size() - 1; i >= 0; i--)
        {
            swap(numbers[i], numbers[0]);
            AdjustHeap(0, i);
        }
        return;
    };
};

void CountingSort(vector<int> &numbers)
{
    if (numbers.empty())
        return;
    int Min = 0x7fffffff, Max = 0x80000000;
    for (auto i = numbers.begin(); i < numbers.end(); i++)
    {
        if (*i < Min)
            Min = *i;
        if (*i > Max)
            Max = *i;
    }
    int bias = 0 - Min;
    int length = Max - Min + 1;
    vector<int> countarray(length, 0);
    for (int i = 0; i < numbers.size(); i++)
    {
        countarray[numbers[i] + bias] += 1;
    }
    int index = 0;
    for (int i = 0; i < length; i++)
    {
        while (countarray[i] != 0)
        {
            numbers[index] = i - bias;
            countarray[i]--;
            index++;
        }
    }
    return;
}

vector<int> BucketSort(vector<int> &numbers)
{
    if (numbers.empty())
        return numbers;
    
    return numbers;
}

vector<int> RadixSort(vector<int> &numbers)
{
    if (numbers.empty())
        return numbers;

    return numbers;
}

int main()
{
    vector<int> numbers = {3, 5, 4, 1, 2};
    printVector(numbers);
    // QuickSort(numbers, 0, numbers.size() - 1);
    // HeapSort A = HeapSort(numbers);
    // A.Sort();
    CountingSort(numbers);
    printVector(numbers);
    return 0;
}