鹤山网站建设易搜互联酒店网站建设一般考虑哪些因素

鹤山网站建设易搜互联,酒店网站建设一般考虑哪些因素,罗源城乡建设网站,网站建设投标文件范本作为刚学数据结构的大学生#xff0c;排序算法曾是我的 “噩梦”—— 背完原理写不出代码#xff0c;跑通代码又搞不清过程。直到把选择、冒泡、插入、归并、桶、计数这六大基础排序算法挨个实现并调试#xff0c;才摸清它们的 “脾气”。这篇文章带你从代码到运行过程…作为刚学数据结构的大学生排序算法曾是我的 “噩梦”—— 背完原理写不出代码跑通代码又搞不清过程。直到把选择、冒泡、插入、归并、桶、计数这六大基础排序算法挨个实现并调试才摸清它们的 “脾气”。这篇文章带你从代码到运行过程彻底搞懂这些排序算法排序算法概述定义与重要性排序算法在计算机科学中的基础地位及应用场景分类标准基于比较的排序选择、冒泡、插入、归并与非比较排序桶、计数性能指标时间复杂度、空间复杂度、稳定性分析选择排序Selection Sort核心思想每次遍历选择未排序部分的最小或最大元素与当前位置交换实现步骤嵌套循环结构外层控制边界内层查找极值复杂度分析时间复杂度$O(n^2)$最坏、平均、最好情况相同空间复杂度$O(1)$原地排序优缺点实现简单但效率低不适合大规模数据冒泡排序Bubble Sort核心思想重复比较相邻元素若逆序则交换直至无交换发生优化策略引入标志位提前终止已排序序列的无效遍历复杂度分析时间复杂度$O(n^2)$最坏、平均$O(n)$最好已排序时空间复杂度$O(1)$优缺点代码简单但效率低适合教学或小规模数据插入排序Insertion Sort核心思想将未排序元素逐个插入到已排序部分的正确位置实现细节从后向前扫描已排序序列边比较边移动元素复杂度分析时间复杂度$O(n^2)$最坏、平均$O(n)$最好空间复杂度$O(1)$优缺点对小规模或部分有序数据高效常作为高级算法的子过程归并排序Merge Sort核心思想分治法策略递归分解数组至单元素后合并有序子序列关键操作merge函数合并两个有序数组需额外空间复杂度分析时间复杂度$O(n \log n)$所有情况空间复杂度$O(n)$非原地排序优缺点稳定且高效但空间开销大适合链表排序或外部排序桶排序Bucket Sort核心思想将数据分到有限数量的桶中各桶单独排序后合并适用条件数据均匀分布桶数量与数据范围合理相关复杂度分析时间复杂度$O(n k)$$k$为桶数理想情况下空间复杂度$O(n k)$优缺点线性时间效率依赖数据分布需额外内存计数排序Counting Sort核心思想统计每个元素的出现次数按计数重建有序序列限制条件数据为整数且范围较小如0到100复杂度分析时间复杂度$O(n k)$$k$为数据范围空间复杂度$O(n k)$优缺点非比较排序速度快但仅适合特定场景算法对比与选型建议性能对比表横向对比六大算法的时间、空间复杂度及稳定性场景适配小规模数据插入、选择排序大规模数据归并排序特定分布数据桶排序、计数排序扩展思考如何结合算法优势如TimSort的插入归并策略一、选择排序“挑最小的往前放”核心思路大学生白话版就像整理书桌每次从一堆乱书里挑出最薄的一本放到最前面再从剩下的书里挑最薄的放到已整理好的书后面重复直到所有书排好序。代码与运行过程def SelectionSort(a): n len(a) for i in range(n-1): # 已排序区间0~i-1待排序区间i~n-1 min_i i # 假设当前i是最小值下标 for j in range(i1, n): if a[j] a[min_i]: min_i j # 更新最小值下标 a[i], a[min_i] a[min_i], a[i] # 交换到已排序区间末尾 print(a) # 打印每轮排序结果 a [3,4,5,2,3,6,1] SelectionSort(a)从运行结果能看到每一轮都把当前待排序区间的最小值 “挑” 到前面[1, 4, 5, 2, 3, 6, 3] # 第1轮找到最小值1放到开头 [1, 2, 5, 4, 3, 6, 3] # 第2轮找到最小值2放到第2位 [1, 2, 3, 4, 5, 6, 3] # 第3轮找到最小值3放到第3位 ...最终得到有序数组特点时间复杂度O(n2)最好 / 最坏 / 平均空间复杂度O(1)原地排序不稳定排序相同元素可能交换位置二、冒泡排序“大的元素往后冒”核心思路大学生白话版想象水里的气泡大的气泡会先浮到水面。排序时让相邻元素两两比较大的元素就像气泡一样一步步 “冒” 到数组末尾每一轮冒一个最大的直到所有元素有序。代码与运行过程def BubbleSort(a): n len(a) for i in range(n-1, -1, -1): # 已排序区间i1~n-1待排序区间0~i for j in range(0, i): if a[j] a[j1]: a[j], a[j1] a[j1], a[j] # 逆序则交换 print(a) a [5,4,6,7,3,53,5,2,1,6] BubbleSort(a)每一轮都把最大的元素 “推” 到末尾后面的元素逐渐有序[4, 5, 6, 3, 7, 5, 2, 1, 6, 53] # 第1轮53冒到最后 [4, 5, 3, 6, 5, 2, 1, 6, 7, 53] # 第2轮7冒到倒数第2位 ...最终得到有序数组特点时间复杂度O(n2)最坏 / 平均O(n)最好已近有序时加标志位优化空间复杂度O(1)原地排序稳定排序三、插入排序“把元素插到合适位置”核心思路大学生白话版类比打牌时整理手牌手里已经有一叠排好序的牌新摸一张牌就从后往前比找到它该放的位置插进去。排序时把数组分成 “已排序” 和 “待排序” 两部分每次插一个待排序元素到已排序区间。代码与运行过程def InsertionSort(a): n len(a) for i in range(1, n): # 已排序区间0~i-1待排序元素a[i] x a[i] j i - 1 while j 0: if x a[j]: a[j1] a[j] # 元素后移 j - 1 else: break a[j1] x # 插入到合适位置 print(a) a [23,43,5,12,6,6,55,343] InsertionSort(a)每一轮把新元素 “插” 到前面的有序区间里[23, 43, 5, 12, 6, 6, 55, 343] # 初始已排序区间只有23 [5, 23, 43, 12, 6, 6, 55, 343] # 第1轮5插入到23前面 [5, 12, 23, 43, 6, 6, 55, 343] # 第2轮12插入到5和23之间 ...最终得到有序数组特点时间复杂度O(n2)最坏 / 平均O(n)最好已近有序空间复杂度O(1)原地排序稳定排序适合小规模数据或已近有序的数据四、归并排序“分而治之先分后合”核心思路大学生白话版用 “分治” 思想把大问题拆成小问题解决。比如要排一个长数组先把它对半拆拆到每个子数组只有 1 个元素1 个元素天然有序再把这些有序的子数组两两合并合并成更大的有序数组直到合并回原来的长度。代码与运行过程def Merge(a, start, mid, end): tmp [] l, r start, mid 1 # 合并两个有序子数组a[start..mid]和a[mid1..end] while l mid and r end: if a[l] a[r]: tmp.append(a[l]) l 1 else: tmp.append(a[r]) r 1 # 把剩余元素加入tmp tmp.extend(a[l:mid1]) tmp.extend(a[r:end1]) # 把tmp赋值回原数组 for i in range(start, end1): a[i] tmp[i - start] print(start, end, tmp) def MergeSort(a, start, end): if start end: return mid (start end) // 2 MergeSort(a, start, mid) # 递归拆分左半部分 MergeSort(a, mid1, end) # 递归拆分右半部分 Merge(a, start, mid, end) # 合并 a [3,43,34,423,4,2,5,5,234] MergeSort(a, 0, len(a)-1)先拆分、后合并每一步都能看到子数组的合并过程0 1 [3, 43] # 合并子数组[3]和[43] 0 2 [3, 34, 43] # 合并[3,43]和[34] 3 4 [4, 423] # 合并[423]和[4] ...最终合并为完整有序数组特点时间复杂度O(nlogn)最好 / 最坏 / 平均空间复杂度O(n)需要额外数组存储临时结果稳定排序适合大规模数据但需要额外空间五、桶排序“分组排序再合并”核心思路大学生白话版像分批次洗衣服把一堆脏衣服按颜色分成 “白、黑、彩” 三个桶每个桶里的衣服单独洗干净最后把三个桶的衣服按顺序叠好。排序时把数据分到多个 “桶” 里每个桶单独排序最后合并所有桶的元素。代码与运行过程def SelectionSort(a): # 桶内用选择排序 n len(a) for i in range(n): min_i i for j in range(i1, n): if a[j] a[min_i]: min_i j a[i], a[min_i] a[min_i], a[i] def BucketSort(a): minV min(a) maxV max(a) bucketCount 3 # 桶的数量 bucket [[], [], []] # 初始化桶 # 计算每个桶的范围 perBucket (maxV - minV bucketCount) // bucketCount # 把元素分到对应桶中 for num in a: bucketIndex (num - minV) // perBucket bucket[bucketIndex].append(num) # 对每个桶排序 for i in range(bucketCount): SelectionSort(bucket[i]) # 合并所有桶的元素 idx 0 for i in range(bucketCount): for v in bucket[i]: a[idx] v idx 1 print(bucket) print(a) a [7,11,5,9,8,6,3,12,10,4,2] BucketSort(a)先分组、再排序、最后合并[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] # 每个桶排序后 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] # 合并后的结果特点时间复杂度O(nk)k是桶的数量数据分布均匀时空间复杂度O(nk)需要额外桶存储数据稳定排序取决于桶内排序算法适合数据分布均匀的场景六、计数排序“统计次数直接构造有序数组”核心思路大学生白话版类似统计班级同学的分数分布先数出考 59 分、60 分、61 分…… 的各有多少人再按分数从低到高把对应人数的分数依次列出来直接得到有序的分数表。代码与运行过程def CountSort(a): n len(a) cntLen max(a) 1 # 计数数组的长度覆盖最大元素 cnt [0] * cntLen # 统计每个元素出现的次数 for val in a: cnt[val] 1 print(cnt) # 根据计数数组构造有序数组 n 0 for val in range(0, cntLen): while cnt[val] 0: a[n] val cnt[val] - 1 n 1 a [2,3,1,3,2,1,4,2,4,6,2] CountSort(a) print(a)先统计次数再按次数输出元素[0, 2, 4, 2, 2, 0, 1] # 计数数组元素0出现0次1出现2次2出现4次... [1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 6] # 构造的有序数组特点时间复杂度O(nk)k是数据范围空间复杂度O(k)需要计数数组稳定排序适合数据范围小且为非负整数的场景如成绩、年龄七、6 大排序算法选型总结算法时间复杂度空间复杂度稳定性适用场景选择排序O(n2)O(1)不稳定小规模数据简单但低效冒泡排序O(n2)O(1)稳定小规模 / 已近有序数据教学用插入排序O(n2)O(1)稳定小规模 / 已近有序数据较高效归并排序O(nlogn)O(n)稳定大规模数据需额外空间桶排序O(nk)O(nk)稳定数据分布均匀的场景计数排序O(nk)O(k)稳定数据范围小的非负整数这些排序算法是数据结构的基础理解它们的原理和适用场景写代码时才能 “对症下药”。预告下一篇《排序算法实战篇二》将带来基数排序、快速排序、随机快速排序、希尔排序、堆排序这 5 种更进阶的排序算法带你玩转高效排序