清风的技术小屋

不为所动, 做更专业的自己

0%

常用排序算法总结

在介绍排序算法之前,先约定数组表示为 \(A\),大小为 \(N\),数组下标从 \(0\) 开始,排序的数组是从小到大排列

插入排序

在数组是反序的情况下,时间复杂度为 \(O(N^2)\),在数组已排序的情况下,时间复杂度为 \(O(N)\)

1
2
3
4
5
6
7
8
9
10
11
void insertion_sort(int *nums, int n)
{
int p, tmp;
for (int i=1; i<n; i++)
{
tmp = nums[i];
for (p=i; p > 0 && nums[p-1] > tmp; p--)
nums[p] = nums[p-1];
nums[p] = tmp;
}
}

归并排序

时间复杂度为 \(O(NlogN)\)

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 merge(int *nums, int *tmp, int left_start, int right_start, int right_end)
{
int left_pos, right_pos, pos;

left_pos = left_start;
right_pos = right_start;
pos = left_start;
while (left_pos < right_start && right_pos <= right_end) {
if (nums[left_pos] <= nums[right_pos])
tmp[pos++] = nums[left_pos++];
else
tmp[pos++] = nums[right_pos++];
}

while (left_pos < right_start) {
tmp[pos++] = nums[left_pos++];
}
while (right_pos <= right_end) {
tmp[pos++] = nums[right_pos++];
}

// copy array tmp back to array nums
for (int i=left_start; i<=right_end; i++)
nums[i] = tmp[i];
}

void msort(int *nums, int *tmp, int left, int right)
{
if (left < right)
{
int center = (left + right) / 2;
msort(nums, tmp, left, center);
msort(nums, tmp, center+1, right);
merge(nums, tmp, left, center+1, right);
}
}

void merge_sort(int *nums, int n)
{
int *tmp = new int[n];
msort(nums, tmp, 0, n-1);
delete[] tmp;
}

快速排序

平均时间复杂度为 \(O(NlogN)\),最坏的情形下,时间复杂度为 \(O(N^2)\)

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
int partition(int *nums, int left, int right)
{
int i = left - 1;
int tmp;
int pivot = nums[right];

for (int j=left; j<=right-1; j++) {
if (nums[j] <= pivot) {
i = i + 1;

tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}

i = i + 1;
tmp = nums[i];
nums[i] = pivot;
nums[right] = tmp;

return i;
}

void qsort(int *nums, int left, int right)
{
if (left < right) {
int p = partition(nums, left, right);
qsort(nums, left, p-1);
qsort(nums, p+1, right);
}
}

void quick_sort(int *nums, int n)
{
qsort(nums, 0, n-1);
}