Lunatic's Space

排序算法

发表于
本文字数： 1.9k 阅读时长 ≈ 4 分钟

算法（2）排序算法

1、插入排序

1.1 直接插入排序：

直接插入排序的基本思想：

1）将整个数组分为“已排序”和“未排序”的两部分，设已排序m，总长度n

2）从未排序部分选取第一个元素

3）遍历已排序的数组，查找需要插入的位置下标i

4）保护待排序数据，将下标大于i，小于m的所有元素右移一位

5）插入，进入下一轮循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertSort(type* arr, int num)
{
	for (int m = 1; m < num; m++)//外层for循环，用于记录已经排序好的长度m
	{
		type tmp = arr[m];
		int i = m - 1;
		for ( i = m - 1; i >= 0&&arr[i]>tmp; i--)//内层for循环，用于遍历已排序的数组
		{
			arr[i + 1] = arr[i];
		}
		arr[i+1] = tmp;
	}
}

算法的性能分析：

时间复杂度：O（n^2）

（平均情况下向长度为m的序列中插入一个数据的平均移动速度是m/2，m从1累加到n-1）

空间复杂度：O（1）

稳定性：稳定

2、交换排序

2.1 快速排序

1）递归调用自身

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
#include <algorithm> // 用于 std::swap

int Partition(int* arr, int num, int nLower, int nUpper) {
	int pivot = arr[nLower]; // 选取第一个元素作为主元进行切割
	int nLeft = nLower + 1;
	int nRight = nUpper; // 确定本次分割的范围

	while (true) {
		while (nLeft <= nRight && arr[nLeft] <= pivot) nLeft++; // 查找左侧第一个大于 pivot 的元素对应的下标
		while (nRight >= nLeft && arr[nRight] >= pivot) nRight--; // 查找右侧第一个小于 pivot 的元素对应的下标
		if (nLeft > nRight) break; // 循环退出条件
		if (nLeft < nRight) { // 如果左标小于右标，交换找到的两个下标对应的数的位置
			std::swap(arr[nLeft], arr[nRight]);
		}
	}
	std::swap(arr[nLower], arr[nRight]); // 将主元放到正确的位置
	return nRight; // 返回主元的最终位置
}

void QuickSort(int* arr, int num, int nLower = 0, int nUpper = -1) {
	if (nUpper == -1) nUpper = num - 1; // 缺省参数的情况，nUpper 应该是 num - 1
	if (nLower < nUpper) {
		int nSplit = Partition(arr, num, nLower, nUpper); // 划分数组
		QuickSort(arr, num, nLower, nSplit - 1); // 递归排序左侧子数组
		QuickSort(arr, num, nSplit + 1, nUpper); // 递归排序右侧子数组
	}
}

算法性能分析：

快速排序在n较大时时间复杂度O（nlogn）

在n较小时或主元选择不合理时，时间复杂度为O（n^2）

空间复杂度O（logn）

快速排序是不稳定的

3、选择排序

3.1直接选择排序

1）数组被分为已排序与未排序两组

2）每次遍历未排序组找到最小的元素插入已排序组的最后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename type>
void selectSort(type* items, int len)
{
	for (int i = 1; i < len; i++)
	{
		int imin = i - 1;
		for (int j = i; j < len; j++)//j从i开始，在i后寻找最小的排到已经排序的前序列后一个
		{
			if (items[j] < items[imin]) {
				imin = j;
			}
		}
		if (imin != i - 1)//如果找到了，将最小值放置到i-1处
		{
			type t = items[i - 1];
			items[i - 1] = items[imin];
			items[imin] = t;
		}
	}
}