哪些网站是做外贸生意的,信阳网站开发公司电话,上海品划做网站,免费行情软件app网站直播下载基本概念 排序是对数据进行处理的常见操作#xff0c;即将数据按某字段规律排列。字段是数据节点的一个属性#xff0c;比如学生信息中的学号、分数等#xff0c;可针对这些字段进行排序。同时#xff0c;排序算法有稳定性之分#xff0c;若两个待排序字段一致的数据在排序…基本概念 排序是对数据进行处理的常见操作即将数据按某字段规律排列。字段是数据节点的一个属性比如学生信息中的学号、分数等可针对这些字段进行排序。同时排序算法有稳定性之分若两个待排序字段一致的数据在排序前后相对位置不变则该排序算法是稳定的否则不稳定。此外根据数据量与内存的关系还分为内排序数据量小可全部装入内存处理和外排序数据量大需暂存外存分批次读入内存处理。
一、冒泡排序
一核心思想 冒泡排序基于相邻元素比较的思路。从头到尾让每两个相邻元素进行比较若顺序符合排序要求则保持位置不变若为逆序则交换位置。经过一轮比较序列中具有 “极值”最大值或最小值取决于排序顺序的数据会被挪至序列末端。 例如对于数组[5, 3, 8, 6, 2]进行升序排序从第一个元素开始5 和 3 比较因为 5 3所以交换位置数组变为[3, 5, 8, 6, 2]接着 5 和 8 比较顺序不变8 和 6 比较交换位置数组变为[3, 5, 6, 8, 2]8 和 2 比较交换位置第一轮比较结束后数组变为[3, 5, 6, 2, 8]。可以看到最大的数 8 被移到了数组末尾。若序列中有n个数据在最极端情况下经过n - 1轮比较一定能将所有数据排序完毕。
二代码实现
// 冒泡排序data为数组len为数组长度
void bubbleSort(int* data, int len) {int i, j;for (i 0; i len - 1; i) {int flag 1; // 用于标记某一趟是否有元素交换若没有则说明已排序完成for (j 0; j len - 1 - i; j) {if (data[j] data[j 1]) { // 升序排序若要降序改为data[j] data[j 1]int tmp;tmp data[j];data[j] data[j 1];data[j 1] tmp;flag 0; // 有元素交换标记为0}}if (flag) { // 若某一趟没有元素交换提前结束排序break;}}
}
三性能分析 冒泡排序的时间复杂度为 O(n^2)其中n是待排序数据的数量。这是因为在最坏情况下需要进行n - 1轮比较每轮比较的次数从n - 1逐渐减少到 1。空间复杂度为 O(1)因为它只需要几个临时变量来进行元素交换不需要额外的大量空间。冒泡排序是一种稳定的排序算法因为相同元素的相对顺序在排序过程中不会改变。
四示例图示 冒泡排序 以数组[5, 3, 8, 6, 2]的升序排序为例
第一轮
比较 5 和 3交换数组变为[3, 5, 8, 6, 2]比较 5 和 8顺序不变比较 8 和 6交换数组变为[3, 5, 6, 8, 2]比较 8 和 2交换数组变为[3, 5, 6, 2, 8]
第二轮
比较 3 和 5顺序不变比较 5 和 6顺序不变比较 6 和 2交换数组变为[3, 5, 2, 6, 8]
第三轮
比较 3 和 5顺序不变比较 5 和 2交换数组变为[3, 2, 5, 6, 8]
第四轮
比较 3 和 2交换数组变为[2, 3, 5, 6, 8]排序完成。
二、选择排序
一核心思想 选择排序的思路是每一轮从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。 例如对于数组[5, 3, 8, 6, 2]进行升序排序第一轮从数组中找到最小的数 2与第一个数 5 交换位置数组变为[2, 3, 8, 6, 5]第二轮从剩下的[3, 8, 6, 5]中找到最小的数 3由于它已经在正确位置无需交换第三轮从[8, 6, 5]中找到最小的数 5与 8 交换位置数组变为[2, 3, 5, 6, 8]第四轮从[6, 8]中找到最小的数 6由于它已经在正确位置无需交换此时数组已排序完成。
二代码实现
// 选择排序data为数组len为数组长度
void selectionSort(int* data, int len) {int i, j, minIndex;for (i 0; i len - 1; i) {minIndex i;for (j i 1; j len; j) {if (data[j] data[minIndex]) { // 升序排序若要降序改为data[j] data[minIndex]minIndex j;}}if (minIndex ! i) {int tmp data[i];data[i] data[minIndex];data[minIndex] tmp;}}
}
三性能分析 选择排序的时间复杂度同样为 O(n^2)因为无论数据初始状态如何都需要进行n - 1轮选择和交换操作。空间复杂度为 O(1)只需要几个临时变量。选择排序是一种不稳定的排序算法例如数组[5, 5, 3]进行升序排序时两个 5 的相对顺序可能会改变。
四示例图示 选择排序 以数组[5, 3, 8, 6, 2]的升序排序为例
第一轮
找到最小的 2与 5 交换数组变为[2, 3, 8, 6, 5]
第二轮
在剩下的[3, 8, 6, 5]中找到最小的 3位置不变
第三轮
在[8, 6, 5]中找到最小的 5与 8 交换数组变为[2, 3, 5, 6, 8]
第四轮
在[6, 8]中找到最小的 6位置不变排序完成。
三、插入排序
一核心思想 插入排序假设前面已经有i个节点是有序的那么从第i 1个节点开始插入到前面i个节点的合适位置中。由于第一个元素自身总是有序的因此从第 2 个元素开始不断插入前面的有序序列直到全部排列完毕。 例如对于数组[5, 3, 8, 6, 2]进行升序排序初始时认为第一个元素 5 是有序的。然后取第二个元素 3将其与 5 比较因为 3 5所以将 5 后移一位把 3 插入到 5 原来的位置数组变为[3, 5, 8, 6, 2]接着取第三个元素 8由于 8 5所以 8 的位置不变数组仍为[3, 5, 8, 6, 2]再取第四个元素 6将其依次与 8、5 比较找到合适位置插入数组变为[3, 5, 6, 8, 2]最后取第五个元素 2将其依次与 8、6、5、3 比较找到合适位置插入数组变为[2, 3, 5, 6, 8]。
二代码实现
// 插入排序data为数组len为数组长度
void insertionSort(int* data, int len) {int i, j, tmp;for (i 1; i len; i) {tmp data[i];j i - 1;while (j 0 data[j] tmp) { // 升序排序若要降序改为data[j] tmpdata[j 1] data[j];j--;}data[j 1] tmp;}
}
三性能分析 插入排序在最好情况下数据已经有序的时间复杂度为 O(n)因为只需要进行n - 1次比较无需移动元素。在最坏情况下数据逆序的时间复杂度为 O(n^2)平均时间复杂度也为O(n^2)。空间复杂度为 O(1)只需要几个临时变量。插入排序是一种稳定的排序算法因为在插入过程中相同元素的相对顺序不会改变。
四示例图示 插入排序 以数组[5, 3, 8, 6, 2]的升序排序为例
第一轮
3 插入到 5 前面数组变为[3, 5, 8, 6, 2]
第二轮
8 位置不变数组仍为[3, 5, 8, 6, 2]
第三轮
6 插入到 8 前面数组变为[3, 5, 6, 8, 2]
第四轮
2 插入到最前面数组变为[2, 3, 5, 6, 8]排序完成。 总结
冒泡排序、选择排序和插入排序都是简单的排序算法它们的时间复杂度在最坏情况下都O(n^2)空间复杂度为O(1)适用于数据样本较小的场合。其中冒泡排序和插入排序是稳定的排序算法选择排序是不稳定的排序算法。在实际应用中可根据数据特点和需求选择合适的排序算法。
