各种排序方法复杂度总结

各种排序方法复杂度总结各种排序方法复杂度总结 在 C 中 排序算法是最基本最常用的算法 不同的排序算法在不同的场景或应用中会有不同的表现 接下 来小编搜集了各种排序方法复杂度总结 欢迎查看 一 冒泡 排序 主要思路是 通过交换相邻的两个数变成小数在前大数在后 这样每次遍 历后 最大的数就 沉 到最后面了 重复 N 次即可以使数组 有序 代码实现 void bubble sort int arr int len for int i 0 i len 1 i for int j len 1 j i j if arr j arr j 1 int temp arr j arr j arr j 1 arr j 1 temp 冒泡排序改进1 在某次遍历中 如果没有数据交换 说明整个数组已经有序 因此通过设置标志位来记录此次遍历有无数据交换就可以判断 是否要继续循环 冒泡排序改进2 记录某次遍历时最后发生数据交换的位置 这个位置之后的 数据显然已经有序 因此设置标志位记录每次遍历中最后发生 数据交换的位置可以确定下次循环的范围 二 直接插入排序 主要思路是 每次将一个待排序的数组元素 插入到前面已排序的序列中 这个元素应该在的位置 直到全部数据插入完成 类似扑克牌 洗牌过程 代码实现 void sort int arr int len for int i 1 i len i int j i 1 int k arr i while j 1 k arr j arr j 1 arr j j arr j 1 k 三 直接选择排序 主要思路是 数组分成有序区和无序区 初始时整个数组都是无序区 每 次遍历都从无序区选择一个最小的元素直接放在有序区最后 直到排序完成 代码实现 void select sort int arr int len for int i 0 i len i int index i for int j i 1 j len j if arr j arr index index j if index i int temp arr i arr i arr index arr index temp 四 快速排序 主要思路是 挖坑填数 分治法 首先令 i L j R 将 a i 挖出形成打 一个坑 称 a i 为基准数 然后 j 从后向前找到一个比基准 数小的数 挖出来填到 a i 的坑中 这样 a j 就形成了一个新的 坑 再 i 从前向后找到一个比基准数大的数填到 a j 坑中 重 复进行这种挖坑填数 直到 i j 这时 a i 形成了一个新的坑 将基数填到 a i 坑中 这样 i 之前的数都比基准数小 i 之后的 数都比基准数大 因此将数组分成两部分再分别重复上述步骤 就完成了排序 代码实现 void quick sort int arr int left int right if left right int i left j right target arr left while i j while i j arr j target j if i j arr i arr j while i j arr i target i if i j arr j arr i arr i target qu