备考记录
软考中级软件设计师备考笔记
插入排序
直接插入排序
元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
c语言版：
#include <stdio.h>
#include <assert.h>
void InsertSort(int arr[], int n)
{
assert(arr); // 检查 arr 是否为 NULL
int i = 0;
for(i = 0; i < n - 1; i++)
{
int end = i;
int x = arr[end + 1];//这里定义了一个变量x，用来存储当前要插入的元素
while(end >= 0)
{
if(arr[end] > x)
{
arr[end + 1] = arr[end]; // 将 arr[end] 向后移动一位
--end;//end向前移动一位
}
else
{
break;
}
}
arr[end + 1] = x; // 将 x 插入到正确的位置
}
}
int main() {
int arr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
InsertSort(arr, n);
for(int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
希尔排序
希尔排序又称缩小增量法
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样整体而言，可以达到优化的效果。
时间复杂度O(N^1.5)
空间复杂度O(1)
稳定性：不稳定。
#include <stdio.h>
#include <assert.h>
void ShellSort(int* a, int n)
{
assert(a); // 检查 a 是否为 NULL
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1; // 计算增量
for (int i = 0; i < n - gap; i++)
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
int main() {
int arr[] = {5, 2, 9, 1, 5, 6}; // 示例数组
int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
ShellSort(arr, n); // 调用希尔排序函数
// 输出排序后的数组
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
选择排序
直接选择排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
#include <stdio.h>
#include <assert.h>
// 交换两个元素的函数
void Swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 选择排序
void SelectSort(int* a, int n) {
assert(a); // 检查 a 是否为 NULL
int begin = 0; // 保存数组的起始位置
int end = n - 1; // 保存数组的末尾位置
while (begin < end) {
int maxi = begin; // 保存最大元素下标
int mini = begin; // 保存最小元素下标
// 遍历数组寻找最小和最大元素
for (int i = begin; i <= end; i++) {
if (a[i] < a[mini]) {
mini = i;
}
if (a[i] > a[maxi]) {
maxi = i;
}
}
// 将最小元素交换到起始位置
Swap(a + begin, a + mini);
// 判断最大值的位置是否在起始位置
if (maxi == begin) {
maxi = mini;
}
// 将最大元素交换到末尾位置
Swap(a + end, a + maxi);
// 移动数组起始和末尾位置
begin++;
end--;
}
}
int main() {
int arr[] = {5, 2, 9, 1, 5, 6}; // 示例数组
int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
SelectSort(arr, n); // 调用选择排序函数
// 输出排序后的数组
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
堆排序
堆可以用数组实现，对于数组中的任意索引i：
父节点索引为 (i-1)/2
左子节点索引为 2i + 1
右子节点索引为 2i + 2
这些公式来源于完全二叉树的性质。下面通过图例来说明为什么这些公式成立。
考虑一个从0开始索引的数组，它代表了一棵完全二叉树。假设有一个根节点位于索引 0 的位置。
0
/ \
1 2
/ \ / \
3 4 5 6
/ \
7 8
在这个例子中：
节点 0 是根节点。
节点 1 和 2 是节点 0 的左子节点和右子节点。
节点 3 和 4 是节点 1 的左子节点和右子节点。
节点 5 和 6 是节点 2 的左子节点和右子节点。
节点 7 和 8 是节点 3 的左子节点和右子节点。
现在我们来看一下上述公式的应用：
父节点索引：对于节点 4，它的父节点是节点 1。根据公式 (i - 1) / 2，将 i = 4 代入得到 (4 - 1) / 2 = 1.5，向下取整后得到 1，这正是节点 4 的父节点索引。
左子节点索引：对于节点 2，它的左子节点是节点 5。根据公式 2 * i + 1，将 i = 2 代入得到 2 * 2 + 1 = 5，这正是节点 2 的左子节点索引。
右子节点索引：同样对于节点 2，它的右子节点是节点 6。根据公式 2 * i + 2，将 i = 2 代入得到 2 * 2 + 2 = 6，这正是节点 2 的右子节点索引。
// 堆排序完整代码
#include <stdio.h>
#include <assert.h>
void Swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 向下调整
void AdjustDown(int* a, int n, int root) {
assert(a);
int parent = root;
int child = parent * 2 + 1;
while (child < n) {
if (child + 1 < n && a[child + 1] > a[child]) {
child++;
}
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
void HeapSort(int* a, int n) {
assert(a);
// 建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(a, n, i);
}
// 交换
for (int i = n - 1; i > 0; i--) {
Swap(&a[i], &a[0]);
AdjustDown(a, i, 0);
}
}
// 测试堆排序
int main() {
int arr[] = {3, 5, 1, 10, 2};
int n = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
交换排序
冒泡排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置。共进行n-1趟这样的交换将可以把所有的元素排好。
// 冒泡排序完整代码
#include <stdio.h>
#include <assert.h>
void Swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 冒泡排序
void BubbleSort(int* a, int n) {
assert(a);
int i = 0;
int flag = 0;
// n-1趟排序
for (i = 0; i < n - 1; i++) {
int j = 0;
// 一趟冒泡排序
for (j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
Swap(&a[j], &a[j + 1]);
flag = 1;
}
}
// 若某一趟排序中没有元素交换则说明所有元素已经有序，不需要再排序
if (flag == 0) {
break;
}
}
}
// 测试冒泡排序
int main() {
int arr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
BubbleSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
快速排序
时间复杂度：O(NlogN)
空间复杂度：O(logN)
稳定性：不稳定
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序的方法有很多，但其核心思想是相同的，这里使用hoare版本举例
// 快速排序完整代码
#include <stdio.h>
#include <assert.h>
void Swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
//交换a与b的值
// 分区函数
int PartSort1(int* a, int left, int right) {
int key = right; // 选定基准值
while (left < right) {
// 选右边为基准值，左指针先走
while (left < right && a[left] <= a[key]) {
left++;
}
// 右指针再走
while (left < right && a[right] >= a[key]) {
right--;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
return left;
}
// 快速排序
void QuickSort(int* a, int left, int right) {
assert(a);
if (left >= right) {
return;
}
int keyi = PartSort1(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
// 测试快速排序
int main() {
int arr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
QuickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
归并排序
时间复杂度：O(NlogN)
空间复杂度：O(N)
稳定性：稳定
首先应在数组中找出有序的序列，但数组是否有序编译器可不知道。
所以可以将数组划分，一分二，二分四……直到每个序列中只有一个数字。
归并排序有递归实现与非递归实现
递归实现
// 归并排序完整代码
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
void _MergeSort(int* a, int left, int right, int* tmp) {
// 区间中没有元素时不再合并
if (left >= right) {
return;
}
// 划分数组，每次一分为二
int mid = (left + right) / 2;
_MergeSort(a, left, mid, tmp); // 划分左区间
_MergeSort(a, mid + 1, right, tmp); // 划分右区间
// 合并有序序列
int begin1 = left, end1 = mid; // 有序序列1
int begin2 = mid + 1, end2 = right; // 有序序列2
int i = left;
while (begin1 <= end1 && begin2 <= end2) { // 注意结束条件为一个序列为空时就停止
if (a[begin1] < a[begin2]) {
tmp[i++] = a[begin1++];
} else {
tmp[i++] = a[begin2++];
}
}
// 两序列不可能同时为空，将剩余元素合并
while (begin1 <= end1) {
tmp[i++] = a[begin1++];
}
while (begin2 <= end2) {
tmp[i++] = a[begin2++];
}
// 将合并后的序列拷贝到原数组中
// 在这里拷贝的原因是保证返回到上一层递归后两个子序列中的元素是有序的
for (int j = left; j <= right; j++) {
a[j] = tmp[j];
}
}
// 归并排序递归实现
void MergeSort(int* a, int n) {
assert(a);
// 因为需要将两个有序序列合并，需借助额外数组
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL) {
perror("malloc");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}
// 测试归并排序
int main() {
int arr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
MergeSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
非递归实现
// 归并排序非递归实现完整代码
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
void MergeSortNonR(int* a, int n) {
assert(a);
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL) {
perror("malloc");
exit(-1);
}
// 初始化每组的元素个数为1
int gap = 1;
while (gap < n) { // gap为n时就只有一个序列了，所以gap<n
// 归并每两组归并一次
int index = 0; // 记录tmp数组中的元素下标
for (int i = 0; i < n; i += 2 * gap) { // 两组中的元素个数为2*gap
// 控制两组边界
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 当原数组中元素个数不是2^n时，最后两组组会出现元素不匹配的情况
// 情况1：end1>=n或begin2>=n,即最后两组中只有一组有元素，则不需归并
if (end1 >= n || begin2 >= n) {
break;
}
// 情况2：end2>=n，即最后两组中，第二组元素个数小于第一组，则需要调整第二组边界
if (end2 >= n) {
end2 = n - 1;
}
// 归并
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++];
}
}
// 一趟排完后，将归并后的有序序列拷贝到原数组中
for (int j = 0; j < index; j++) {
a[j] = tmp[j];
}
// 每次循环每组元素个数增大2倍
gap *= 2;
}
free(tmp);
tmp = NULL;
}
// 测试归并排序非递归实现
int main() {
int arr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
MergeSortNonR(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
基数排序
时间复杂度：O(r+n)
空间复杂度：O(r+n)
稳定性：稳定
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤
统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中
比较容易理解，这里不多做说明
基数排序不适合同时正数和负数
存在负数时可以使用unsigned int// 计数排序完整代码 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> // 计数排序 void CountSort(int* a, int n) { assert(a); // 创建计数数组，数组大小为原数组中最大值-最小值+1 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, range * sizeof(int)); // 统计次数 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; } } free(count); count = NULL; } // 测试计数排序 int main() { int arr[] = {5, 2, 9, 1, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); CountSort(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
