数据结构之排序

@TOC

先单趟在再整体

插入排序

直接插入排序（InsertSort）

思想

  • 举例——>摸牌

    在有序的数组中摸一张牌插入到前面合适的位置中去
    插入排序的逻辑，摸到一张牌后和最后的比较大小，大则插入在后面，使得总体有序。

实现

  • 单趟

    先排单趟，比较到要插入数据与前一个数据(end)比较大小，比该数大则插入到该数后面，直到比较到第一个数据为止插入到首元素位置（循环条件为end>=0）。
    先将要插入元素保存到tmp中，该位置为end+1，等到合适位置后插入到end+1中去。
    为处理end比较完没找到的(tmp最小)的情况，当tmp>=end时，跳出while，在循环外交换。
    每次比较完后end--向前比较
    单趟如下![[Pasted image 20230925213125.png]]

  • 总体

    共有n个数据，至少比较n次，故在用for循环，由于end+1的存在，i<=n-2/i<n-1;
    拿到一个乱序数组，从第一个数据向后排序，故end=i,

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void InsertSort(int*a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];	//往后挪动
			}
			else
			{
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
int main()
{
	int arr[] = { 1,3,5,7,4,1,0,2,6 };
	InsertSort(arr,sizeof(arr)/sizeof(arr[0]));
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	return 0; 
}

复杂度分析

  • 时间复杂度
    最优：
  • 有序：O(n)
    最劣：
  • 完全逆序：O(n^2)
  • 空间复杂度
    O(1)

希尔排序

  • 引入

    ①在插入排序中从第一个数开始向后遍历，②每到一个数(x)就与之前的m个数从后往前进行(比较–交换)，若完全逆序，则每个数的要与前n个数交换，时间复杂度提升至O(n^2)，完全有序则为O(n)。直到遍历完全后有序。
    而希尔在此基础上思考，遍历是少不了的，那能否通过减少从后往前比较时的交换次数进行(蓝色内容)来提高时间效率呢？。
    于是希尔排序的核心为先进行分组预排序，再进行直接插入排序来优化。
    ![[Pasted image 20230927113722.png]]

  • 以下是从0到1的希尔排序的过程

1.预排序

单元素

该元素往前比较，如果小于前面数，则交换，并将下标前移。直到n<0时退出循环，完成一个数的位置排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//单个数据单趟
gap = 3;
int end = 0;
int tmp = a[end + 1];
while (end >= n)
{
	if (a[end] > tmp)
	{
		a[end + gap] = a[end];
		end -= gap;
	}
	else
		break;
}
a[end + gap] = tmp;

单趟元素

对组内单元素的排序，每隔gap个数据进行比较，直到单趟元素排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int  gap = 3;
for (int i = 0; i < n - gap; i += gap)
{
	int end = i;
	int tmp = a[end + gap];
	//单个数据单趟
	while (end >= n)
	{
		if (a[end] > tmp)
		{
			a[end + gap] = a[end];
			end -= gap;
		}
		else
			break;
	}
	a[end + gap] = tmp;
}

多组

为使每组元素动起来，在最外层套一层循环，每组元素有gap个，故循环gap次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void InsertSort(int*a, int n)
{
	int  gap = 3;
		for (int j = 0; j < gap; j++)
		{
			for (int i = j ; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				//单个数据单趟
				while (end >= n)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
						break;
				}
				a[end + gap] = tmp;
			}
		}
}

多组并排

最后一步多组可以按如上分次进行，也可以按如下多组并行排序，效果相同，但代码更加整洁。
对与gap的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void InsertSort(int*a, int n)
{
	int  gap = 3;
	for (int i = 0; i < n - gap; ++i)
	{
		int end = i;
		int tmp = a[end + gap];
		//单个数据单趟
		while (end >= n)
		{
			if (a[end] > tmp)
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
				break;
		}
		a[end + gap] = tmp;
	}
}

分析

多组并排

意义：让大的数更快地到后面去，小的数更快的到前面去
gap越大，跳的越快，越不接近有序。
gap越小，跳的越慢，越解决有序，gap=1，直接有序

2.直接插入排序

  • 以上逻辑对比直接插入排序我们可得，当gap=1时，该排序为直接插入排序。
  • 当数据过多gap=3时预排过多，优化不明显，所以gap随n的变化而变化（gap=gap/2或gap=gap/3+1(效率更高，为保证最后1次为1，故+1)）。
  • 所以这样定义gap：第一趟gap=n每组分1个元素，之后分2、4、8……n个元素(gap=n/2、n/4……1)，到1时相当于预排序后的直接插入排序，实现有序。
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
void ShellSort(int* a, int n)
{
	//多组并排
	int  gap = n;
	while (gap > 1)
	{
		gap = gap / 2;
		//gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			//单个数据单趟
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}
}

复杂度计算

  • 时间复杂度

    gap=3，每组n/3个数据，每趟比较3次（1+2），一共比较(n/3)*3=n次
    gap=9，每组n/9个数据，每趟比较36(1+2+3+…+9)次，一共比较（n/9）*36=4n次
    ………………(组数x每组的次数)上一次排序对这次有所增益
    目前在严蔚敏教材中时间复杂度约为O(n^1.3)<O(n^log2N)；该准确数据仍在研究暂未有定论；

  • 空间复杂度为1
  • 不稳定

选择排序

直接选择排序

遍历一遍直接选出 最大/最小 的值

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
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//直接选择排序
void SelectSort(int* a, int n)
{
	int begin = 0, end = n-1;
	while(end > begin)
	{
		int mini = begin, maxi = end;
		for (int i = begin+1; i <= end ; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		
		Swap(&a[mini], &a[begin]);
		
		if (maxi == begin)
		{
			maxi = mini;
		}
		
		Swap(&a[maxi], &a[end]);
		begin++;
		end--;
	}
}

堆排序

排升序建小堆，排降序建大堆

交换排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;
		for (int j = 1; j < n - i; j++)
		{
			if (a[j-1] > a[j])
			{
				int tmp = a[j-1];
				a[j-1] = a[j];
				a[j] = tmp;
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}

快速排序

Honre

将第一个数设为key，
找key，左边找比key小，右边找比key大，交换。
比key小的放到左边，比key大的换到右边，最终达到左边比key小、右边比key大的效果。
当左右相遇时，key与右边交换。
至此，key为它要到的最终位置。

单趟

Pasted image 20231004171541.png

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
int PartSort(int* a, int left , int right)
{
	//*防止局部变量交换无效
	int keyi = left;
	while(left < right)
	{
		//*等于号防止陷入死循环的情况
		//*left<right防止越界访问
		
		//找小_大就跳过
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//找大，小就跳过
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

单趟时间复杂度为O(n);

递归

Pasted image 20231004171711

1
2
3
4
5
6
7
8
9
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return ;
	int keyi = PartSort(a, begin, end);
	//[begin, keyi-1] keyi [key+1, end]
	QuickSort(a, begin, keyi-1);
	QuickSort(a, keyi + 1, end);
}
  • 为什么相遇位置比key小？

    右边先走做到的

    • 右边先走找小，找到比key小数
      • 左边找大
        • 找到
        • 交换——>右边走
          • 未找到
            • R=L，相遇位置是右边所找的比key小的数

三数取中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//三数取中
int GetMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[right])
	{
		if (a[left] > a[mid])
			return mid;
		else if (a[left] < a[mid])
			return left;
		else
			return left;
	}
	else   //right 大
	{
		if (a[right] > a[mid])	
			return mid;
		else if (a[right] < a[mid])	
			return right;
		else
			return right;
	}
}

挖坑法

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
//挖坑法
int PartSort2(int* a, int left, int right)
{
	int midi = GetMid(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;

		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

前后指针法

cur找比key小的数，++prev，交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int PartSort3(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	return keyi;
}

小区间优化

降低递归次数——>直接插入

递归太深可能会产生栈溢出，所以我们来学习非递归(当然快排不太可能会溢出，1000000000个数据30层，)

非递归——栈

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 QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	STInit(&st);
	STPush(&st, end);	//入栈先右后左
	STPush(&st, begin);

	while(!STEmpty(&st))
	{
		//出栈先左后右
		int left = STTop(&st);
		STPop(&st);

		int right = STTop(&st);
		STPop(&st);

		int keyi = PartSort1(a, left, right);
		// [left, keyi-1] keyi [keyi+1, right]
		
		//先入右再入左
		if (right > keyi + 1)	//有位置
		{
			STPush(&st, right);
			STPush(&st, keyi + 1);
		}
		
		if (left < keyi - 1)
		{
			STPush(&st, keyi-1);
			STPush(&st, left);
		}
	}
	STDestory(&st);
}

二叉树结构的排序
右边找比key小的，左边找比key大的。

归并排序

递归

开空间

  • 分左右区间(递进)
    直到递进空返回，直到1个元素
  • 归并
    将 左|右 进行大小比较，大的元素插入到tmp数组中。
    判断 左|右 是否已经空，有一个空即停止。
    后续将剩下的元素插入到tmp中去。
  • 拷贝
    将tmp中数组插入到原数组a中，顺序与tmp中相同
  • (回归)
    回归后继续 归并-拷贝- 回归

代码

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
void _MergeSort(int* a,int* tmp, int begin, int end)
{
	if (begin >= end)
		return;
	int mid = (begin + end) / 2;

	//递归
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid+1, end);

	//归并到tmp中，并拷贝到原数组
	//[begin1, end1][begin2, end2]
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin;
	while (begin1 <= end1 && begin2 <= end2)	//有一个递归结束就结束
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	//只进一个
	while(begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp==NULL)
	{
		perror("malloc error\n");
		return ;
	}
	_MergeSort(a, tmp, 0, n-1);
	free(tmp);
}

空间复杂度：O(n)
时间复杂度：O(n*log2n)

非递归

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
void MergeSortNonr(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp==NULL)
	{
		perror("malloc error\n");
		return ;
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[begin1, end1] [begin2, end2]
			int begin1 = i, end1 = gap + i - 1;
			int begin2 = i + gap, end2 = 2 * gap + i - 1;
			//printf("[%d,%d][%d,%d]", begin1, end1, begin2, end2);

			if (begin2 > n)
			{
				break;
			}
			if (end2 > n)
			{
				end2 = n - 1;
			}

			int index = i;
			while (begin1 <= end1 && begin2 <= end2)	//有一个结束就结束
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];

				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			//只进一个
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, (end2-i+1) * sizeof(int));
		}
		//printf("\n");
		gap *= 2;
	}
	free(tmp);
}

复杂度

空间复杂度：O(n)
时间复杂度：O(n*log2n)

内/外排序
磁盘不支持下标访问
顺序写顺序读

计数排序

统计每个数字出现的次数，每个值是多少就对对应位置++；
局限：数值得是相对集中
相对映射

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
void CountSort(int* a, int n)
{
	//找出最大的和最小的
	int max = a[0], min = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	//确定范围，开辟空间
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	//将空间内数据初始化为0
	memset(count, 0, sizeof(int) * range);
	//统计数据出现的次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	//排序(回写)
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

复杂度

时间复杂度：O(n+range)
空间复杂度：O(range)
适合范围集中的排序

各种常用排序算法

d