排序算法

cpp 评论

冒泡排序

稳定性

冒泡排序是一种稳定的排序算法

选择排序效率：O（n2)

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <stdio.h>
#include <stdlib.h>

/********************* 排序规则 *********************

冒泡排序算法的运作如下：（从后往前）
	1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
	2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
	3. 针对所有的元素重复以上的步骤，除了最后一个。
	4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

稳定性:冒泡排序是一种稳定排序算法

***************************************************/

//冒泡排序(升序)
void bubbleSort(int *array, int len)	//O(n²)
{
#if 0
	// 外层
	for (int i= 0; i < len; ++i)
	{
		for (int j = 1; j < len - i; j++)
		{
			// 交换
			if (array[j] < array[j - 1])
			{
				int tmp = array[j];
				array[j] = array[j - 1];
				array[j - 1] = tmp;
			}
		}
	}
#endif
	// 0: 没有排好, 1: 已经排好
	int flag = 0;
	for (int i = len - 1; i > 0 && flag==0; --i)
	{
		flag = 1;	// 默认已经排好
		for (int j = 0; j < i; ++j)
		{
			if (array[j] > array[j + 1])
			{
				int tmp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = tmp;
				flag = 0;	// 没有排好
			}
		}
	}
}

#if 0
void main()
{
	int i;
	//定义整型数组
	int array[] = { 11, 8, 7, 6, 3 };
	//计算数组长度
	int len = sizeof(array) / sizeof(int);
	//遍历数组
	printf("待排序数组序列: ");
	for (i = 0; i < len; ++i)
	{
		printf("%d\t", array[i]);
	}
	printf("\n");

	//排序
	bubbleSort(array, len);

	//遍历
	printf("冒泡排序之后的序列:	");
	for (i = 0; i < len; ++i)
	{
		printf("%d\t", array[i]);
	}
	printf("\n");
	system("pause");
}
#endif

选择排序

稳定性

选择排序是不稳定的排序方法

选择排序效率：O（n2)

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
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>

/*-------------------- 排序规则 --------------------

		它的工作原理是每一次从待排序的数据元素中选出
		最小（或最大）的一个元素，存放在序列的起始位
		置，直到全部待排序的数据元素排完。

		稳定性:选择排序是不稳定的排序方法 如:[5,5,3]

-------------------------------------------------*/

//选择排序(升序排列)
void selectionSort(int *array, int len)
{
	int min = 0;	// 指向最小的元素的位置
	// 外层循环
	for (int i = 0; i < len - 1; ++i)
	{
		min = i;
		// 内存循环
		for (int j = i + 1; j < len; ++j)
		{
			// 判断
			if (array[min] > array[j])
			{
				// 保存最小的元素的位置
				min = j;
			}
		}
		// 判断是否需要交换
		if (min != i)
		{
			// 找到了新的最小值
			// 交换
			int tmp = array[min];
			array[min] = array[i];
			array[i] = tmp;
		}
	}
}

#if 0
void main()
{
	int i;
	//定义整型数组
	int array[] = { 12, 5, 33, 6, 10 };
	//计算数组长度
	int len = sizeof(array) / sizeof(int);
	//遍历数组
	printf("待排序数组序列: ");
	for (i = 0; i < len; ++i)
	{
		printf("%d\t", array[i]);
	}
	printf("\n");

	//排序
	selectionSort(array, len);

	//遍历
	printf("选择排序之后的序列:	");
	for (i = 0; i < len; ++i)
	{
		printf("%d\t", array[i]);
	}
	printf("\n");
	system("pause");
}
#endif

插入排序

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
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>

/******************* 排序规则 *******************

	每次处理就是将无序数列的第一个元素与有序数列
	的元素从后往前逐个进行比较，找出插入位置，将
	该元素插入到有序数列的合适位置中。

	稳定性:插入排序是稳定的

***********************************************/

//插入排序算法(升序排列)
void insertionSort(int *array, int len)
{
	int tmp = 0;	// 存储基准数
	int index = 0;	// 坑的位置
	// 遍历无序序列
	for (int i = 1; i < len; ++i)
	{
		index = i;
		tmp = array[i];
		// 遍历有序序列(从后往前)
		for (int j = i - 1; j >= 0; --j)
		{
			// 基准数根有序序列中的元素比较
			if (tmp < array[j])
			{
				// 有序序列元素后移
				array[j + 1] = array[j];
				// 坑的位置
				index = j;
			}
			else
			{
				break;
			}
		}
		// 填坑
		array[index] = tmp;
	}
}

#if 0
void main()
{
	int i;
	//定义整型数组
	int array[] = { 12, 5, 33, 6, 10 };
	//计算数组长度
	int len = sizeof(array) / sizeof(int);
	//遍历数组
	printf("待排序数组序列: ");
	for (int i = 0; i < len; ++i)
	{
		printf("%d\t", array[i]);
	}
	printf("\n");

	//排序
	insertionSort(array, len);

	//遍历
	printf("插入排序之后的序列:	");
	for (i = 0; i < len; ++i)
	{
		printf("%d\t", array[i]);
	}
	printf("\n");
	system("pause");
}
#endif

稳定性

插入排序是稳定的排序算法

插入排序效率：O(n2)

希尔排序

稳定性

希尔排序是不稳定的排序算法。

希尔排序的效率：O（n*logn）≈ O（1.3*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
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>

/**************************** 排序规则 ****************************

	希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
	随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰
	被分成一组，算法便终止。

	稳定性: 希尔排序是非稳定排序算法。

*****************************************************************/
//希尔排序
void shellSort(int *array, int len)
{
	// 步长
	int gap = len;
	while (gap > 1)
	{
		// 步长递减公式
		gap = gap / 3 + 1;
		// 分组, 对每一组, 进行插入排序
		for (int i = 0; i < gap; ++i)
		{
			int tmp;	// 基准数
			int index;	// 坑的位置
			// 插入排序
			// 无序序列
			for (int j = i + gap; j < len; j += gap)
			{
				tmp = array[j];
				index = j;
				// 有序序列(从后往前遍历)
				for (int k = j - gap; k >= 0; k -= gap)
				{
					if (tmp < array[k])
					{
						// 后移
						array[k + gap] = array[k];
						// 位置
						index = k;
					}
					else
					{
						break;
					}
				}
				// 填坑
				array[index] = tmp;
			}
		}
	}
}

#if 1
void main()
{
	int i;
	//定义整型数组
	int array[] = { 12, 5, 33, 6, 10 };
	//计算数组长度
	int len = sizeof(array) / sizeof(int);
	//遍历数组
	printf("待排序数组序列: ");
	for (int i = 0; i < len; ++i)
	{
		printf("%d\t", array[i]);
	}
	printf("\n");

	//排序
	shellSort(array, len);

	//遍历
	printf("希尔排序之后的序列:	");
	for (i = 0; i < len; ++i)
	{
		printf("%d\t", array[i]);
	}
	printf("\n");
	system("pause");
}
#endif

归并排序

稳定性

归并排序是一种稳定的排序算法。

排序效率： O(N*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
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>

//将两个有序数列a[first...mid]和a[mid+1...last]合并。
void mergeArray(int a[], int first, int mid, int last, int temp[])
{
	int leftStart = first;	//左有序序列起点
	int leftEnd = mid;	//左有序序列终点
	int rightStart = mid + 1;	//右有序序列起点
	int rightEnd = last;	//右有序序列终点
	int length = 0;	//两个有序序列合并之后的有序序列长度
	int i = leftStart, j = rightStart;
	
	//将两个有序序列中的元素合并到第三个有序序列中(a的左半部分和右半部分合并到temp中)
	while (i <= leftEnd && j <= rightEnd)
	{
		//按照从小到大的顺序放入到temp中
		if (a[i] <= a[j])
		{
			temp[length++] = a[i++];
		}
		else
		{
			temp[length++] = a[j++];
		}
	}
	//如果左半部分还有元素, 直接放到temp中
	while (i <= leftEnd)
	{
		temp[length++] = a[i++];
	}
	//如果右半部分还有元素, 直接放到temp中
	while (j <= rightEnd)
	{
		temp[length++] = a[j++];
	}
	//将temp中排好的序列拷贝到a数组中
	for (i = 0; i < length; i++)
	{
		//只替换已排好序的那一部分
		a[leftStart + i] = temp[i];
	}
}

//归并排序
void mergeSort(int a[], int first, int last, int temp[])
{
	if (first < last)
	{
		//找到数组的中间位置
		int mid = (first + last) / 2;
		//左边有序
		mergeSort(a, first, mid, temp);  
		//右边有序
		mergeSort(a, mid + 1, last, temp); 
		//再将二个有序数列合并
		mergeArray(a, first, mid, last, temp); 
	}
}

#if 0
void main()
{
	int i;
	//定义整型数组
	int array[] = { 12, 5, 33, 6, 10 };
	//计算数组长度
	int len = sizeof(array) / sizeof(int);
	//遍历数组
	printf("待排序数组序列: ");
	for (i = 0; i < len; ++i)
	{
		printf("%d\t", array[i]);
	}
	printf("\n");

	//创建合适大小的临时数组
	int *p = (int*)malloc(sizeof(int) * len);
	if (p == NULL)
	{
		return;
	}
	mergeSort(array, 0, len - 1, p);
	free(p);

	//遍历
	printf("归并排序之后的序列:	");
	for (i = 0; i < len; ++i)
	{
		printf("%d\t", array[i]);
	}
	printf("\n");
	system("pause");
}
#endif

堆排序

将一个数组变成完全二插树

image-20220423155542270

将完全二插树变成大顶堆(每一个父节点数必须大于左右结点数)或小顶堆

最后一个非叶子结点的位置: 数组长度 / 2 - 1

image-20220423160008111

将第一个结点和最后一个结点交换

image-20220423160339867

再次进行一次大顶堆初始化

image-20220423160602459

将第一个结点和倒数第二个结点交换

image-20220423160654345

再次进行大顶堆初始化

image-20220423160827881

将第一个结点和倒数第三个结点交换

image-20220423160936804

然后进行大顶堆优化

image-20220423161648658

将第一个和倒数第四个交换

image-20220423161757724

再次进行大顶堆优化

image-20220423161914987

将第一个和倒数第五个交换

image-20220423162000297

再次进行大顶堆优化

image-20220423162102108

将第一个和倒数第六个交换

image-20220423162159693

进行大顶堆优化

image-20220423170513121

将第一个和倒数第七个交换

image-20220423170550850

进行大顶堆优化

image-20220423170628012

将第一个和倒数第八个交换

因为倒数第八个已经是可以交换的最后一个了,所以不需要大顶堆优化了,这是我们的序列已经排好序了

image-20220423170700601

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
65
66
67
68
69
70
71
72
#include<iostream>
#include<ctime>
using namespace std;
#define MAX 10

void PrintArr(int arr[], int len) {
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

void Swap(int arr[],int index,int max) {
	int temp = arr[index];
	arr[index] = arr[max];
	arr[max] = temp;

}
void HeapAdjust(int arr[],int index,int len) {
	int lchild = index * 2 + 1;
	int rchild = index * 2 + 2;

	int max = index;

	if (lchild < len && arr[lchild] > arr[max])
	{
		max = lchild;
	}
	if (rchild < len && arr[rchild] < arr[max])
	{
		max = rchild;
	}

	if (max != index) {
		Swap(arr,index,max);
		HeapAdjust(arr,max,len);
	}


}
void HeapSort(int arr[],int len) {

	for (int i = len / 2 - 1; i >= 0; i--)
	{
		HeapAdjust(arr,i,len);
	}

	for (int i = len - 1; i >= 0; i--)
	{
		Swap(arr,0,i);
		HeapAdjust(arr, 0, len);
	}

}

int arr[MAX];
int main() {
	int len = sizeof(arr) / sizeof(int);
	srand((unsigned int)time(NULL));
	for (int i = 0; i < MAX; i++)
	{
		arr[i] = rand() % 10;
	}
	unsigned int start = time(NULL);
	HeapSort(arr,len);
	PrintArr(arr,len);
	unsigned int end = time(NULL);

	cout << "time: " << end - start << endl;
	return 0;
}

排序总结

image-20220423121229212

YanChen

Personal profile