c语言各种排序算法的实现

在学习算法的过程中 排序算法是很基础的 下面我用 C 语言实现了 5 中基础 的排序算法 插入排序 选择排序 冒泡排序 并归排序 快速排序 1 插入排序 插入排序很简单 在 算法导论 中的解释是这样的 插入排序的工作机理与 很多人打牌时 整理手上的牌的做法差不多 开始的时候我们的左手是空的 接着我们从桌面上一张一张的摸牌 并将它放到左手的一个正确的位置上 为 了找到这个正确的位置 要将它与左手的牌从右到左地进行比较 无论在什么 时候左手的牌都是排好序的 很简单吧 不过当初为了理解这个算法也花了一点 时间 下面是 C 语言对插入排序的一个简单实现 帮助 1 2 3 4 5 6 7 8 9 10 11 12 13 插入排序 int insert sort int a int size int i j temp for i 1 i 0 for i 0 i size i for j i 1 j a j 交换位置 temp a i a i a j a j temp return 0 end select sort 3 冒泡排序 冒泡排序是重复交换相邻的两个反序元素 它的工作工作机理我觉得跟选择排 序差不多 因为在第一个遍历整个数组交换反序元素之后 数组的第一个元素 就已经是整个数组中最小的元素了 下面是 C 语言实现的一个冒泡排序 帮助 1 2 3 4 5 6 7 8 9 10 11 12 冒泡排序 int bubble sort int data int size int i j temp for i 0 i i j if data j 并归排序 并归排序 你也可以叫它合并排序 它采用了递归的思想 将数据分成两个部 分 将这两个部分排好序之后再进行合并 一直重复这个过程 得出最后的结 果 可能说的比较抽象 大家看下面的代码 帮助 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 合并两个已经排好的结果 int merg result int data int start int middle int end int s1 s2 i i1 i2 s1 middle start 1 s2 end middle i1 i2 0 两个临时的数组 int temp1 s1 temp2 s2 复制数据前后两个段的数据进临时数组 for i 0 i s1 i temp1 i data start i for i 0 i s2 i temp2 i data middle 1 i 开始合并 for i start i s1 s2 start i if temp1 i1 s1 break 无法将两个临时数组的最后一个 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 元素设为无穷大 data i temp1 i1 else if i2 s2 break data i temp2 i2 添加两个循环 将最后的数据合并好 while i1 s1 data i temp1 i1 while i2 s2 data i temp2 i2 end merg result 并归排序 int merg sort int data int start int end int middle if start 快速排序 这是我觉得最神奇的一个 前面 3 个排序时间代价都是 O n2 虽然并归排序 的时间 O nlgn 但是由于合并过程中需要的临时数组 使得它占用的栈空间 相当大 在我的机子上 2G 内存 排序 50 万的整形数据程序就会崩溃 内存 不够了 而快速排序虽然也是递归的 但是它完全在本地工作 不需要申请额 外的空间 所以很方便 下面是我用 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 合并两个已经排好的结果 int partition int data int start int end int key i j temp 选取最后一个元素作为主元素 key data end i start for j start j end j if data j key 交换 data j 与 data i temp data i data i data j data j temp 将主元素换到 i 位置 temp data i 31 32 33 34 35 36 37 38 39 40 data i data end data end temp 返回主元素的位置 printf d i return i end partition 并归排序 int quick sort int data int start int end int middle if start end middle partition data start end quick sort data start middle 1 quick sort data middle 1 end return 0 end quick sort 这只是我理解的快速排序一个很简单的实现 更多有关快速排序的原理你可以 看这里 上面的代码都是我在理解算法之后写出来的 当然可能有一些 bug 如果你发 现 了请联系我 关于算法性能的分析 我实在不在行 在书上说的这几个算法性能上 前 3 个 是 O n2 后两个是 O nlgn 说实话我对这些的理解不是很够 于是我自己写 了一个测试程序在我的笔记本上跑了下 我的方式是随机生成数据 然后使用 不同的排序算法进行测试 当然几百个数据几乎一瞬间就可以解出 所以我在 测试的时候是对 1000 次 或者更多 排序的总时间进行统计 通过统计结果 我发现插入排序在对于小量的数据 效果很好 但是在数据太 大的时候就不能和并归排序和快速排序进行比较了 这个数据的间值在 200 左 右 而快速排序不管是大数据还是小数据的效果都非常好 有些时候比插入排 序还好 当然 这是我没有遇到传说中的坏数据 因为坏数据是有可能让快速 排序的时间达到 O n2 的 这个文件是我测试的结果 有一些我连续