各类排序方法_堆排序顺序表链表

1.直接插入排序与折半插入排序

实现思路：将当前元素前面的序列看作是一个有序表，通过不同的查找手段查找当前元素应该在前面的有序序列中的插入位置，然后进行元素移动并插入

适用性：适用于顺序存储和链式存储的线性表

直接插入排序

int main()//常规方法
{
	int a[10];
	int i, k, j;
	printf("输入10个数:\n");
	for (i = 0; i < 10; i++)
		scanf("%d", &a[i]);
	for (j = 1; j < 10; j++)
	{
		int temp = a[j];
		for ( k = j - 1; k >= 0 && a[k] > temp; k--)//这里没有用哨兵的方式，而下面的希尔排序是仿照用哨兵实现的直接插入排序而改写的，当采用哨兵时就省去了每次判断越界这一操作
			a[k + 1] = a[k];
		a[k + 1] = temp;
	}
	printf("结果:\n");
	for (int i = 0; i < 10; i++)
		printf("%d ", a[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

折半插入排序

int main()
{
	int a[10];
	int i, k, j, low, high, mid;
	printf("输入10个数:\n");
	for (i = 0; i < 10; i++)
		scanf("%d", &a[i]);
	for (k = 1; k < 10; k++)//当前元素前面的序列已有序，在当前元素的前面序列实施折半查找
	{
		low = 0;
		high = k - 1;
		int temp = a[k];//保存待插入元素
		while (low<=high)
		{
			mid = (low + high) / 2;
			if (a[mid] > temp)//写成大于等于就破坏了稳定性
				high = mid - 1;
			else
				low = mid + 1;//当a[mid]==temp时，还需要在low的右边继续查找，这里是与常规折半查找不一样的地方，常规折半查找是a[mid]==temp就返回了
		}
		for (j = k-1; j >=low; j--)//查找结束后low所在位置即为插入位置，需将low及后面元素全部后移腾出low位置插入
		{
			a[j + 1] = a[j];
		}
		a[low] = temp;
	}
	for (int i = 0; i < 10; i++)
		printf("%d ", a[i]);
}
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

直接插入排序时间效率分析

首先需要知道，插入排序的时间复杂度由比较和移动两部分组成

1.若通过顺序查找查找插入位置时，在最好情况下，元素本来就有序，那么元素无需移动，只需比较n-1次即可，所以时间复杂度为O(n)，在最坏情况下，原表为逆序，则需要进行n-1趟操作，每趟操作由i次(i代表第几趟)比较和i+1次移动构成，所以用最好情况和最坏情况的时间复杂度平均值作为最后的算法时间复杂度，即O(n方)

2.若通过折半查找查找插入位置，则会缩减比较次数，但不会减少移动次数，比较次数缩减约为O(nlog2n),因为每一趟需要比较log2n次，共进行n-1趟，所以是nlog2n，最后得出时间复杂度依旧是O(n方)

2.希尔排序及时间效率分析

实现思路：其实就是直接插入排序的变式，出现了一个增量的概念，通过每次变化增量(最终变为1)会出现对应增量下的子表，对每一个子表进行直接插入排序，然后继续变化增量直至增量为1，此时在进行依次直接插入排序即可，增量为1时表已经基本有序，所以这一次直接插入排序会很快，若一开始增量就为1,则它就是直接插入排序

代码

#include<stdio.h>
int main()
{
	int m = 4, i, j, k,n,p;
	int a[11];
	printf("输入10个数\n");
	for (i = 1; i < 11; i++)
		scanf("%d", &a[i]);
	for (n = 5; n >= 1; n /= 2)
	{
		for (j = n + 1; j <= 10; j++)
		{
			if (a[j] < a[j - n])
			{
				a[0] = a[j];
				for (k = j - n; k >= 1 && a[k] > a[0]; k -= n)//记住加防越界条件
					a[k + n] = a[k];
				a[k + n] = a[0];
			}
		}
	}	
	for (i = 1; i < 11; i++)
		printf("%d ", a[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

适用情况：由于每次需要根据增量访问每个对应子表的元素，所以需要存储结构具有随机访问特性，所以只适用于顺序存储，不适用于链式存储

由于种种原因，时间复杂度不是很好求，在这里选择记下来

当n在某个范围是，时间复杂度为O(n的1.3次方),最坏情况下还是O(n方)，所以只能说希尔排序要优于直接插入排序

稳定性：不稳定
注意：小于还是小于等于才进行交换直接影响了算法稳定性

3.冒泡排序及时间效率分析

代码

#include<stdio.h>
#include<stdlib.h>
int main()
{
	void swap(int&, int&);
	int *a = NULL, num, i, j, k;
	bool flag = false;//false证明此趟没有发生交换元素
	printf("输入元素个数:\n");
	scanf("%d", &num);
	a = (int *)malloc(sizeof(int)*num);
	printf("输入这%d个数\n", num);
	for ( i=0; i < num; i++)
		scanf("%d", a+i);
	for ( j = 0; j < num-1; j++)//num个元素要进行num-1趟冒泡
	{
		flag = false;
		for (int k =0; k < num-1-j; k++)//每一趟要进行将当前还未有序的序列的两两元素比较，num-j表示剩余未有序元素个数，在减一是因为防止下面if语句越界
		{
			if (a[k] > a[k + 1])
			{
				swap(a[k], a[k + 1]);
				flag = true;//出现交换将flag设置为true
			}
		}
		if (flag == false)//易错点：若一趟下来无元素交换证明此序列已经整体有序，无须比较余下趟数
			break;
	}
	for (i = 0; i < num; i++)
		printf("%d ", *(a+i));
	return 0;

}
void swap(int &a, int &b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
}
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

时间效率分析
空间复杂度： O(1)
最好时间复杂度： 即为元素本来就有序的情况，如123456，在比第一趟时进行了n-1次比较，随后由于未发生元素交换直接退出程序，所以最好时间复杂度为O(n)
最坏时间复杂度： 即为整体序列逆序，每进行一趟需要比较当前未有序元素序列个数-1次，每进行依次比较都要进行一次交换，总的时间复杂度为O(n方)
平均时间复杂度：O（n方）

注： 通过算法代码可发现每进行依次交换会调用一次swap函数，调用一次swap函数会进行三次的元素移动，所以在题中需留意他问你的是元素交换次数还是移动次数
在这里插入图片描述

4.快速排序

代码

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int *a = NULL, i,num;
	printf("输入个数:\n");
	scanf("%d", &num);
	a = (int *)malloc(sizeof(int)*num);
	for (i = 0; i < num; i++)
		scanf("%d", &a[i]);
	void dealwith(int[], int, int);
	dealwith(a, 0, num - 1);//首先处理0~num-1这个区间的子表
	for (i = 0; i < num; i++)
		printf("%d ", a[i]);
	return 0;
}
void dealwith(int a[], int low, int high)
{
	int SpeedSort(int, int, int[]);
	int keypoistion = 0;
	if (low < high)
	{
		keypoistion = SpeedSort(low,high,a);//执行一次speedsort将会确定一个元素的最终位置，这个元素会将剩下的表分为两部分，因此用keypoistion来接收这个元素的位置
		dealwith(a, low, keypoistion - 1);//处理左半边
		dealwith(a,keypoistion + 1, high);//处理右半边
	}
}
int SpeedSort(int low, int high, int a[])
{
	int key = a[low];//用这个序列的第一个元素作为“枢纽元素”
	while (low<high)//切记不要写成low！=high，否则造成系统栈溢出
	{
		while (low < high && a[high] >= key)//不要写成low<=high了
			high--;
		if (low < high)//切记每一步均由low<high这一步判断
			a[low] = a[high];
		while (low < high && a[low] <= key)
			low++;
		if (low < high)
			a[high] = a[low];
	}
	a[low] = key;//最后key的存放位置一定是low和high相等的位置
	return low;//返回这个已经被确定最终位置的元素的下标，用它将主函数剩下的表再分为两部分
}
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

快速排序的时间效率分析

空间复杂度:空间复杂度直接取决于递归调用次数，然鹅最好情况下也就是所选枢纽元素可以很好地平分剩余序列的元素，此时对应于最好的空间复杂*O(log以2为底n的对数)；但是假若序列一开始就是有序的，你要是选取第一个元素作为枢纽元素就会导致剩下的递归过程每次都会选择下一个作为枢纽元素，造成“树”只有一个孩子，类比于n个结点具有的树的最大高度为n的情况，所以最坏情况的空间复杂度为O(n)

时间复杂度
不难发现，上述speedsort中的代码实际上每次都将low~high区间内的元素都扫描了一遍，所以每调用一次speedsort函数所执行的基本操作次数不会超过n，所以与空间复杂度一样，时间复杂度也由递归调用的次数决定，所以最好情况下就是枢纽元素可平均分序列的情况下，即O(nlog以2为底n的对数)，最坏情况下为O(n^2)，平均时间复杂度也为O(nlog以2为底n的对数)

如何优化快速排序：
1.随机选择枢纽元素，避免出现由于原序列已有序而导致左右子树分配及其不均的情况

5.简单选择排序与时间效率分析

代码

#include<stdio.h>
int main()
{
	void swap(int &, int &);
	int a[10] = { 2,3,5,16,5,65,1,2,3,74 };
	int i, j, min;
	for (i = 0; i < 9; i++)
	{
		min =i;//本算法简单，但注意有些语句是对下标操作，有些则是对变量操作
		for (j = i + 1; j < 10; j++)
		{
			if (a[min] > a[j])
				min = j;
		}
		if (min != i)
			swap(a[i], a[min]);
	}
	for (i = 0; i < 10; i++)
		printf("%d ", a[i]);
	return 0;
}
void swap(int &a, int &b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
}
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

效率分析
简单选择排序时间复杂度与初始序列状态无关，每一趟都需要比较n-1次，其中n是当前序列中未被排序的元素的个数，所以时间复杂度为O(n方)，空间复杂度为O(1)

稳定性：不稳定

适用于顺序表和链表

6.堆排序

大根堆：是指以顺序存储方式存储的完全二叉树中每一个分支节点的值都大于它左右孩子结点的值的情况

小根堆：是指每一个分支节点的值都小于它左右孩子结点的值的情况

代码

#include<stdio.h>
#include<stdlib.h>
int main()
{
	void DuiSpot(int [],int );
	int *a = NULL;
	int i, j, k;
	printf("输入元素个数:\n");
	scanf("%d", &i);
	a = (int *)malloc(sizeof(int)*(i+1));//顺序存储方式存储树需保证下标可描述结点之间的逻辑关系
	printf("依次输入各数:\n");
	for (j = 1; j < i + 1; j++)
		scanf("%d", &a[j]);

		DuiSpot(a, i);//堆排序主函数
	for (j = 1; j < i + 1; j++)
		printf("%d ", a[j]);
	return 0;
}
void DuiSpot(int a[],int length)
{
	int m, n;
	void swap(int &, int &);
	void BuildDui(int a[], int length);//建堆函数
	void HeadAdjust(int a[], int k, int length);//后续处理函数
	BuildDui(a, length);//此语句执行一遍后，此时数组第一个元素为最大元素
	for (m = length; m > 1; m--)
	{
		swap(a[m], a[1]);//将第一个最大的元素与序列尾元素互换
		HeadAdjust(a, 1, m - 1);//对剩余元素进行调整
	}
}
void BuildDui(int a[], int length)
{
	void HeadAdjust(int[], int, int);//调整大根堆的函数，分别传入数组、需要调整的分支节点的下标、数组长度
	for (int i = length / 2; i > 0; i--)//n个结点
		HeadAdjust(a, i, length);

}
void HeadAdjust(int a[], int k, int length)
{
	int m, n;
	a[0] = a[k];
	for (m = 2 * k; m <= length; m *= 2)//2*k表示当前结点的左孩子
	{
		if (m<length&&a[m+1]>a[m])//语句1   选取当前结点左右孩子中更大的那个
			m++;
		if (a[0] >=a[m])//语句2
			break;
		else
		{
			a[k] = a[m];
			k = m;//将m赋予k的意思是，现在还不能确定能否将那个小的元素放到当前位置，因为有可能放进来之后造成下面不满足大根堆要求
		}
	}
	a[k] = a[0];
}
void swap(int &a, int &b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
}
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

实现思路
我们将一开始是一个大根堆的情况定为初始状况，同样等到下一次出现大根堆的情况视作上一次的操作结束，首先我们对n各元素进行建堆，就是确保树中的每个非叶节点的值大于它的左右孩子的值(如果非叶节点值小于左右孩子的值则为小根堆)，建堆过后，数组第一个元素一定是当前序列最大元素，将其与表尾元素互换，由于进行了互换会导致此时根节点有可能不满足大根堆的特性，因此需要“下沉根节点”(其余结点是不会被破坏的，只用调整根节点即可)，也就是HeadAdjust函数，经过这个函数后视作一次操作彻底结束，此时首元素又是一个最大元素，继续将其与尾元素交换，后续过程一次类推，可以发现BuildDui函数只执行了一次，也就是对初始序列建堆时调用了一次，后续只需要通过HeadAdjust函数进行大根堆调整即可

堆排序的时间效率分析

可以发现主要操作集中于HeadAdjust函数中的语句1和语句2，当结点有左右孩子时需进行两次比较，当只有一个孩子时仅需要一次比较，也就是说结点每下降一层最多比较2次，若树高为h，某结点在i层，则此结点下降时最多进行2(h-i)次比较，二叉树高h=下取整(log以2为底n的对数)+1，所以每一层有2的i-1次方个结点，由此可以推理出相应的时间复杂度，详细过程看王道数据结构视频*

结论
注：：图片中的排序时间复杂度是指每次进行首尾元素交换后需要再次调整大根堆，而调整大根堆的方法则是沉降根节点，最多沉降树高-1次，(因为最后一层是叶子结点不用管),总共需要进行n-1趟交换，再乘以n-1即可得出排序时间复杂度

往堆中插入和删除元素

插入：插入最低不断上升直到满足大根堆(小根堆要求)
删除：直接删除，用尾元素代替，不断沉降直到满足大根堆(要求)

注： 注意留心插入和删除需要比较的次数，删除时比较的次数要多

7.归并排序

#include<stdio.h>
#include<stdlib.h>
int n;
int main()
{
	void mergesort(int[], int, int);//一开始将表中各元素处理成每一个独立的表的过程
	printf("请输入元素个数:\n");
	scanf("%d", &n);
	int *p = (int *)malloc(sizeof(int)*n);
	printf("请输入这%d个数字:\n", n);
	for (int i = 0; i < n; i++)
		scanf("%d",&p[i]);
		//cin >> p[i];
	mergesort(p, 0, n - 1);
	printf("排序结果如下:\n");
	for (int i = 0; i < n; i++)
		printf("%d ", p[i]);
	return 0;
}
void merge(int[], int, int, int);//归并排序核心函数
void mergesort(int a[], int low, int high)
{
	int mid;
	if (low<high)//不要写成while了
	{
		mid = (low + high) / 2;//让数据表列不断对半分，直到分到每个表只有一个元素为止，代表的则是以一个元素作为一个表的意思
		mergesort(a, low, mid);
		mergesort(a, mid + 1, high);
		merge(a, low, high, mid);
	}
}
int *b = (int *)malloc(sizeof(int)*n);//b为归并排序需要的辅助数组
void merge(int a[], int low, int high, int mid)//low表示表1的首元素下标，mid表示表1的尾元素下标，high表示表2的尾元素下标
{
	int i, j, k;
	for (i = low; i <= high; i++)//先将要处理的表的元素放到b数组对应位置，这里需要注意i的初始取值是low，而不是0
		b[i] = a[i];
	for (i = low, j = mid + 1,k=i; i <= mid && j <= high;)//同样需要注意i和j的初始赋值，不是0！！！
	{
		if (b[i] <= b[j])
		{
			a[k++] = b[i];
			i++;
		}
		else
		{
			a[k++] = b[j];
			j++;
		}

	}
	//将剩下没处理的表直接接到a表后面，以下while语句只会执行一个
	while (i<=mid)
	{
		a[k++] = b[i++];
	}
	while (j<=high)
	{
		a[k++] = b[j++];
	}
}
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

归并排序时间效率分析

归并排序的主要时间耗费在元素的比较上，下图可知，n个元素的归并排序会形成一棵“归并树”，而这个树高-1=归并的趟数，而树高等于log2n，其次每进行一趟归并排序，假设第三趟归并排序，至多需要比较n-1次关键字即可完成(第一趟仅仅需要n/2次比较即可完成)，所以每一趟比较次数不会超过n-1，所以总的时间复杂度就为O(nlogn),空间复杂度为O(n)，主要耗费在辅助数组上，递归工作站所产生的的耗费不足以超过O(n),算法具有稳定性

8.基数排序

首先有3个量搞清楚——d、n、r，比如要给100个人的出生日期降序排序，d就是3，因为关键字的权重可分为3个等级，日最低，年最高，n为元素个数，也就是100，r为每个权重组对应的可能取值的个数，这个r在根据不同权重进行排序时是不一定的，比如对日排序r为31，对月排序则为12，对年则为12，算法的过程：不管是降序还是升序都应该从关键字权重最低的那一组开始进行，也就是日，将日对应的数值放进对应的队列中(队列走势最上面为队头，最下面为队尾)，这一步叫分配，分配结束后开始进行收集，这里的收集则需要你的需求进行选择，若升序则从小的队列那一边开始收集，降序则从大的那一边开始收集，收集结束后当前权重组就排序完成了，开始进行下一个权重组，直至3个权重组全部分配收集完毕。

基数排序的时间效率分析

总共进行d趟，每一趟由分配和收集组成，分配是要将n个元素依次按当前权重组进行分配，所以时间复杂度为O(n)，收集是要将r个队列进行收集，只需将各队列队头指针相连即可，所以时间复杂度为O(r ),所以总的时间复杂度为O(d(n+r)),空间复杂度为O(r )。

9.计数排序

实现思路：将序列中的最大值和最小值找出来，生成一个max-min+1的数组，然后将这些数出现的次数放进数组中，最后在遍历出来即可，详情看B站C中文网讲解的视频

#include<stdio.h>
#include<stdlib.h>
#define len 50 
#define Min -5000//序列中的任意数不会小于它
#define Max1 42200//序列中的任意数不会大于它
int main()
{
	int arr[10];
	for (int i = 0; i < 10; i++)
		scanf("%d", &arr[i]);
	void JiShuSort(int [], int);//计数排序核心算法
	JiShuSort(arr, 10);
	for (int s = 0; s < 10; s++)
		printf("%d ", arr[s]);
	return 0;
}
void JiShuSort(int arr[], int length)
{
	void FindMaxandMin(int [], int,int &,int &);//用来找序列中的最大值和最小值
	int min = 0, Max = 0;
	FindMaxandMin(arr, length,min,Max);
	int *arr1 = (int*)malloc(sizeof(int)*(Max-min+1));
	for (int k = 0; k < Max - min + 1; k++)//初始化临时数组
		arr1[k] = 0;
	for (int i = 0; i < length; arr1[arr[i] - min]++, i++);//将原数组计数情况填入临时数组,这里表达式3的前后有区别
	int s = 0;
	for (int m = 0; m < Max - min + 1; m++)
	{
		for (int n = 0; n < arr1[m]; n++)
			arr[s++] = m+min;
	}
}
void FindMaxandMin(int arr2[], int length,int &min,int &max)
{
	int Max = Min;
	int min1 = Max1;
	for (int i = 0; i < length; i++)
	{
		if (arr2[i] > Max)
			Max = arr2[i];
		if (arr2[i] < min1)
			min1 = arr2[i];
	}
	min = min1;
	max = Max;
}
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

计数排序时间效率分析

大总结