实验十二 排序算法

实验十二 排序算法

实验目的和要求

  1. 掌握六种排序算法
  2. 理解不同的数据对排序算法

实验环境

  1. Visual Studio 2017 Community
  2. Windows 10 Pro

实验内容

  1. 分析插入排序、选择排序、冒泡排序、希尔排序、快速排序、基数排序的性能

实验过程

插入排序

性能分析

时间复杂度 O(n ^ 2), 空间复杂度 O(1)

排序时间与输入有关:

  • 输入的元素个数
  • 元素已排序的程度

最佳情况,输入数组是已经排好序的数组,运行时间是 n 的线性函数;最坏情况,输入数组是逆序,运行时间是 n 的二次函数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insertSort(int *num, size_t length)
{
for (int i = 1; i < length; i++)
{
if (num[i - 1] > num[i])
{
int temp = num[i];
int j = i;
while (j > 0 && num[j - 1] > temp)
{
num[j] = num[j - 1];
j--;
}
num[j] = temp;
}
}
}

选择排序

性能分析

时间复杂度 O(n ^ 2), 空间复杂度 O(1)

排序时间与输入无关,最佳情况,最坏情况都是如此, 不稳定,如 {5, 5, 2}。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void selectionSort(int *num, size_t length)
{
int tmp;
int currentMinIndex;
for (int i = 0; i < length - 1; ++i)
{
currentMinIndex = i;
for (int j = i + 1; j < length; ++j)
if (num[currentMinIndex] > num[j])
currentMinIndex = j;
if (currentMinIndex != i)
{
tmp = num[currentMinIndex];
num[currentMinIndex] = num[i];
num[i] = tmp;
}
}
}

冒泡排序

性能分析

时间复杂度 O(n ^ 2), 空间复杂度 O(1)

排序时间与输入无关,最好、最差、平均都是 O(n ^ 2);稳定,因为是两两比较,不存在跳跃。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubbleSort(int *num, size_t length)
{
int tmp;
for (int i = 0; i < length - 1; ++i)
for (int j = 0; j < length - 1 - i; ++j)
{
if (num[j] > num[j + 1])
{
tmp = num[j];
num[j] = num[j + 1];
num[j + 1] = tmp;
}
}
}

下图中横轴为数据量,纵轴为时间(ms):

排序对比图 - 1

快速排序

性能分析

时间复杂度 O(nlogn),空间复杂度O(logn);不稳定

代码

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
void quickSort(int *num, int left, int right)
{
int i, j, t, temp;
if (left > right)
return;
temp = num[left];
i = left;
j = right;
while (i != j)
{
while (num[j] >= temp && i < j)
j--;
while (num[i] <= temp && i < j)
i++;
if (i < j)
{
t = num[i];
num[i] = num[j];
num[j] = t;
}
}
num[left] = num[i];
num[i] = temp;
quickSort(num, left, i - 1);
quickSort(num, i + 1, right);
}

希尔排序

性能分析

时间复杂度 O(n ^ 1.25)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void shellSort(int *num, size_t length)
{
for (int gap = length / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < length; i++)
{
int j = i;
int temp = num[j];
if (num[j] < num[j - gap])
{
while (j - gap >= 0 && temp < num[j - gap])
{
num[j] = num[j - gap];
j -= gap;
}
num[j] = temp;
}
}
}
}

基数排序

性能分析

时间复杂度 O (n)

代码

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
void radixSort(int *num, size_t length)
{
int* tmp = new int[length];
int* count = new int[length];
int d = maxbit(num, length);
int r = 1;
for (int i = 0; i < d; i++)
{
for (int i = 0; i < 10; i++)
count[i] = 0;
for (int i = 0; i < length; i++)
{
int k = num[i] / r;
int q = k % 10;
count[q]++;
}
for (int i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
for (int j = length - 1; j >= 0; j--)
{
int p = num[j] / r;
int s = p % 10;
tmp[count[s] - 1] = num[j];
count[s]--;
}
for (int i = 0; i < length; i++)
{
num[i] = tmp[i];
}
r = r * 10;
}
}

下图中横轴为数据量,纵轴为时间(ms):

排序对比图 - 2