发表更新shuo-liu1622 分钟读完 (大约3345个字)

数据结构：常见排序算法解析

因为我经常忘记各种排序算法的思路，所以我写了这篇文章。文章中使用了结构体数组来完成排序，已经完成了快排、希尔等多种排序方法。其中，我采用了 arr[0] = {} 这样的方式来置空数组，并将其作为哨兵来使用。

排序算法

（1）直接插入排序；
（2）折半插入排序；
（3）冒泡排序；
（4）简单选择排序。
（5）希尔排序；
（6）快速排序。

首先我先定义一下排序需要用到的…ababab

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
struct Student {
    string name;
    int score;
};

//打印排序后的数组
void printStudents(const Student students[], int size) {
    for(int i = 1; i < size; i++) {
        cout << "姓名：" << students[i].name << "  成绩：" << students[i].score << endl;
    }
    cout << endl;
}


int main() {
    Student students[] = {
    {},
    {"aaa", 87},
    {"bbb", 76},
    {"ccc", 92},
    {"ddd", 64},
    {"eee", 55},
    {"fff", 78},
    {"ggg", 100},
    {"hhh", 43},
    };
 
    int size = sizeof(students) / sizeof(students[1]);
    printStudents(students, size);
 
// insert(students, size);
// binary(students, size);
// bubble(students, size);
// selection(students, size);
 
 
 
// quickSort(students, 1, size);
// cout << "快速排序：" << endl;
// printStudents(students, size);

    shell(students, size, size); 
 
    return 0;
}

直接插入排序

算法步骤

首先取第一个元素假设这个范围内有序（升序），
接着扩大这个范围，由1到n,
始终保持范围内有序，最终完成排序。

动画演示链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void insert(Student students[], int size) {

    //这里假设前i-1个元素有序
    for(int i = 2; i < size; i++) {
    //中转变量，存储即将进入有序区域的数据

        Student tmp = students[i];
        int j = i-1;

        //这里 j = 0 时，students[j].score > tmp.score 必定为false
        while(j >= 0 && students[j].score > tmp.score) {
            students[j + 1] = students[j];
            j--;
        }

        students[j + 1] = tmp;
    }
   cout << "直接插入排序：" << endl;
    printStudents(students, size);
}

算法分析

a.算法性能

时间复杂度：平均（O(n^2)）
空间复杂度：额外空间复杂度是 ( O(1) )

b.稳定性(稳定性是指排序过程中相同元素的相对位置不变)

直接插入排序是稳定的排序算法，因此如果原始数组中存在相同值的元素，在排序后它们的相对顺序不会改变。

c.适用性

相比较于其他 ( O(n^2) ) 的排序算法（如冒泡排序和选择排序），直接插入排序在一般情况下效率更高，特别是在数据部分有序的情况下。
然而，对于大规模数据或需要快速排序的情况，更高效的排序算法（如快速排序、归并排序等 ( O(n \log n) ) 的算法）更为合适。

d.总结

直接插入排序虽然简单，但其性能上不如快速排序等 ( O(n \log 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
void binary(Student students[], int size) {
    for(int i = 2; i < size; i++) {
        Student tmp = students[i];
        int left = 1;
        int right = i-1;

        while(left <= right) {
         //这样可以防止溢出，虽然这里用不到吧
            int mid = left + (right - left) / 2;
            if(students[mid].score > tmp.score) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
  //虽然这样查找的比较快，但是还是要遍历
        for(int j = i; j > left; j--) {  
            students[j] = students[j-1]; 
        }
        students[left] = tmp;
    }
    cout << "折半插入排序：" << endl;
    printStudents(students, size);
}

算法分析

a. 算法性能

时间复杂度：平均情况下 ( O(n^2) )，虽然查找插入位置的过程利用了二分查找，但插入操作仍然是 ( O(n) )。
空间复杂度：额外空间复杂度为 ( O(1) )

b. 稳定性

折半插入排序同样是稳定的排序算法，相同元素的相对位置不会改变。

c. 适用性

折半插入排序适用于需要稳定排序且对空间复杂度有要求的场景，特别是当直接插入排序在查找插入位置上效率较低时，折半插入排序可以提供更好的性能。

d. 总结

折半插入排序相比直接插入排序，在查找插入位置时能够更快地定位，但整体的时间复杂度仍然是 ( O(n^2) )，因此对于大规模数据或需要更高效排序算法的情况，应考虑使用 ( O(n \log n) ) 级别的排序算法，如快速排序或归并排序。

冒泡排序算法

算法步骤

从第一个元素开始，依次比较相邻的两个元素，如果顺序不对则交换它们。
继续对每一对相邻元素进行同样的操作，直到最后一个元素。
重复以上步骤，每次都将未排序部分中最大的元素”浮”到最后，直到整个序列有序。

动画演示链接

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubble(Student students[], int size) {
	for(int i = 1; i < size; i++) {
		for(int j = 1; j < size - i; j++) {
			if(students[j].score > students[j+1].score) {
				swap(students[j], students[j+1]);
			}
		}
//		printStudents(students, size);
	}
	cout << "冒泡排序：" << endl;
	printStudents(students, size);
}

算法分析

a. 算法性能

时间复杂度：O(n^2)
空间复杂度：额外空间复杂度为 ( O(1) )

b. 稳定性

冒泡排序是稳定的排序算法。在比较相邻元素时，如果他们的值相等，则不进行交换，因此相等的元素在排序后的相对位置保持不变。

c. 总结

由于其实现简单且易于理解，在一些教学场景中仍然被广泛使用。实际并不常用。

简单选择排序

算法步骤

首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置
然后，再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾
以此类推，直到所有元素均排序完毕

动画演示链接

1
2
3
4
5
6
7
8
9
10
11
12
13
void selection(Student students[], int size) {
	for(int i = 1; i < size - 1; i++) {
		int min_score = i;
		for(int j = i+1; j < size; j++) {
			if(students[min_score].score > students[j].score) {
				min_score = j;
			}
		}
		swap(students[i], students[min_score]);	
	}
	cout << "简单选择排序：" << endl;
	printStudents(students, size);
}

算法分析

a. 算法性能

时间复杂度：O(n^2)
空间复杂度：额外空间复杂度为 ( O(1) )

b. 稳定性

简单选择排序是不稳定的排序算法。在寻找最小（或最大）元素的过程中，如果有多个相等的元素，那么可能会破坏它们之间的相对顺序。

c. 总结

由于其实现简单且易于理解，在一些教学场景中仍然被广泛使用。实际并不常用。

希尔排序

算法步骤

选择增量序列：希尔排序的关键在于选择合适的增量序列（也称为间隔序列），初始时，选择一个增量h（通常选择数组长度的一半，即 h = n / 2，n为数组长度），然后逐步减小增量。

分组排序：对于当前的增量h，将待排序的数组分成h个长度为n/h的子数组（如果n不能被h整除，则最后一个子数组的长度会小于n/h）。
对每个子数组进行直接插入排序。此时，由于每个子数组中的元素间隔为h，因此只需要考虑每隔h个元素的比较和移动。

逐步减小增量：在完成一轮分组排序后，减小增量h的值（如 h = h / 2），并重复步骤2，直到h变为1。

最后排序：当h变为1时，整个数组被分为n个长度为1的子数组（即每个元素自成一组）。此时，再对整个数组进行一次直接插入排序，即可得到完全有序的数组。

动画演示链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void shell(Student students[], int size, int n) {
	// 逐步缩小间隔直到间隔为1
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 使用间隔进行插入排序
        for (int i = gap; i < n; i++) {
            Student tmp = students[i];
            int j;
            // 在当前间隔内进行插入排序·
            for (j = i; j >= gap && students[j - gap].score > tmp.score; j -= gap) {
                students[j] = students[j - gap];
            }
            students[j] = tmp;
        }
    }
    cout << "希尔排序：" << endl;
	printStudents(students, size);
}

算法分析

a. 算法性能

时间复杂度：希尔排序的时间复杂度很难准确计算，因为它与数据序列的初始状态以及增量序列的选择都有关。
空间复杂度：额外空间复杂度为 ( O(1) )

b. 稳定性

希尔排序是不稳定的排序算法。在增量大于1的排序过程中，相同元素的相对位置可能会发生变化

c. 总结

希尔排序在实际应用中并不常见，因为它通常不如快速排序、归并排序等算法高效。希尔排序的优点是代码实现简单，且在某些特定情况下（如数据基本有序时）效率较高。

快速排序

算法步骤

选择基准（Pivot）：从待排序的序列中选取一个元素作为基准（pivot），通常选择序列的第一个或最后一个元素，或者随机选择。

分割过程（Partition）：将待排序的序列重新排列，所有比基准值小的元素放在基准的前面，所有比基准值大的元素放在基准的后面。在这个分割过程之后，基准元素处于序列的中间位置（左侧的所有元素都比它小，右侧的所有元素都比它大）。这个过程称为一次划分（Partition）。

递归处理：递归地对基准元素左右两侧的子序列进行快速排序，直到每个子序列的长度为1（即已经有序），递归结束。

动画演示链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int quick(Student students[], int left, int right) {
	Student tmp = students[left];
	while(left < right) {
		while(left < right && students[right].score >= tmp.score)
			right--;
		students[left] = students[right];
		
		while(left < right && students[left].score <= tmp.score)
			left++;
		students[right] = students[left];
	}
	students[left] = tmp;
	return left;
}

void quickSort(Student students[], int left, int right) {
	if(left < right) {
		int pi = quick(students, left, right);
		quickSort(students, left, pi - 1);
		quickSort(students, pi + 1, right);
	}
}

算法分析

a. 算法性能

时间复杂度：O(n log n)
空间复杂度：额外空间复杂度为 O(log n)。

b. 稳定性

快速排序是不稳定的排序算法，即相等的元素在排序后可能会改变它们的相对顺序。

c. 总结

快速排序算法由于其高效性和广泛的适用性，在多个领域都有着广泛的应用。

代码全貌

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>

using namespace std;

struct Student {
	string name;
	int score;
};

void printStudents(const Student students[], int size) {
	for(int i = 1; i < size; i++) {
		cout << "姓名：" << students[i].name << "  成绩：" << students[i].score << endl;
	}
	cout << endl;
}

void insert(Student students[], int size) {
	for(int i = 2; i < size; i++) {
		Student tmp = students[i];
		int j = i-1;
		while(j >= 0 && students[j].score > tmp.score) {
			students[j + 1] = students[j];
			j--;
		}
		students[j + 1] = tmp;
	}
	cout << "直接插入排序：" << endl;
	printStudents(students, size);
}

void binary(Student students[], int size) {
    for(int i = 2; i < size; i++) {
        Student tmp = students[i];
        int left = 1;
        int right = i-1;

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(students[mid].score > tmp.score) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for(int j = i; j > left; j--) {  
            students[j] = students[j-1]; 
        }
        students[left] = tmp;
    }
    cout << "折半插入排序：" << endl;
    printStudents(students, size);
}

void bubble(Student students[], int size) {
	for(int i = 1; i < size; i++) {
		for(int j = 1; j < size - i; j++) {
			if(students[j].score > students[j+1].score) {
				swap(students[j], students[j+1]);
			}
		}
//		printStudents(students, size);
	}
	cout << "冒泡排序：" << endl;
	printStudents(students, size);
}

void selection(Student students[], int size) {
	for(int i = 1; i < size - 1; i++) {
		int min_score = i;
		for(int j = i+1; j < size; j++) {
			if(students[min_score].score > students[j].score) {
				min_score = j;
			}
		}
		swap(students[i], students[min_score]);	
	}
	cout << "简单选择排序：" << endl;
	printStudents(students, size);
}

void shell(Student students[], int size, int n) {
	// 逐步缩小间隔直到间隔为1
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 使用间隔进行插入排序
        for (int i = gap; i < n; i++) {
            Student tmp = students[i];
            int j;
            // 在当前间隔内进行插入排序
            for (j = i; j >= gap && students[j - gap].score > tmp.score; j -= gap) {
                students[j] = students[j - gap];
            }
            students[j] = tmp;
        }
    }
    cout << "希尔排序：" << endl;
	printStudents(students, size);
}

int quick(Student students[], int left, int right) {
	Student tmp = students[left];
	while(left < right) {
		while(left < right && students[right].score >= tmp.score)
			right--;
		students[left] = students[right];
		
		while(left < right && students[left].score <= tmp.score)
			left++;
		students[right] = students[left];
	}
	students[left] = tmp;
	return left;
}

void quickSort(Student students[], int left, int right) {
	if(left < right) {
		int pi = quick(students, left, right);
		quickSort(students, left, pi - 1);
		quickSort(students, pi + 1, right);
	}
}

int main() {
	Student students[] = {
	{},
	{"aaa", 87},
	{"bbb", 76},
	{"ccc", 92},
	{"ddd", 64},
	{"eee", 55},
	{"fff", 78},
	{"ggg", 100},
	{"hhh", 43},
	};
	
	int size = sizeof(students) / sizeof(students[1]);
	printStudents(students, size);
	
//	insert(students, size);
//	binary(students, size);
//	bubble(students, size);
//	selection(students, size);
	
	
	
//	quickSort(students, 1, size);
//	cout << "快速排序：" << endl;
//	printStudents(students, size);

	shell(students, size, size);	
	
	return 0;
}

数据结构：常见排序算法解析

http://voidgame.space/articles/shuo-liu16/数据结构：常见排序算法解析/

作者

VoidGameSpace

发布于

2024-06-15

更新于

2024-10-18

许可协议

#

评论

关注我

归档

标签

Balatro1
Big-Oh1
C++4
Computer Graphics1
EasyX3
Git2
Hexo1
Lighting1
Linux1
Math1
PCG1
SDL3
STL1
VoidGameSpace1
c++3
c++语法2
hexo1
hszSoft2
pbr1
suang2
勘误1
发表文章1
塔防课程1
塔防课程，c++1
学习2
学习心得1
小丑牌1
排序算法1
教程3
数据结构3
植物明星大乱斗1
测试2
测试测试测试测试测试1
游戏开发6
游戏心得1
游戏设计1
游戏评测1
算法3
编码1
网络编程1
自我介绍4
设计模式1
闲聊1

分类

链接

最新文章

×