Aloha～！又是我少女人妻 Uerica！今天终於可以进入到演算法的章节啦 (欢呼) ～ 之前因为从没碰过演算法，在整理和学习的时候发现大家都从资料结构开始提及，当时我就想那资料结构应该很重要吧～於是花了几天时间认真研究资料结构，直到前两天我跟老公说，怎麽办文章都写快一半了还没写到演算法...老公用不失礼貌的微笑看着我并对我说：难怪你在厨房想了 30 天都想不出来。Q_Q

好的今天要来提排序 sort 啦～

排序 sort

排序简单来说就是将资料由大到小，或由小到大顺序排列。平常上网购物时会看到可依照价钱由高至低排序商品的按钮，或依照上架日期由新至旧陈列商品等，或是生活上在学校老师依成绩高低排列，在亲戚家跟表堂兄弟们排列身高等（我永远都是最矮的那个，时间复杂度 O(1) QQ）。排序後的优点是资料或物件更容易阅读、统计分析、快速搜寻等。

排序演算法分类

内部与外部排序法

• 内部排序 Internal sort : 资料量少，在主记忆体(RAM)就可以完成，一般的演算法都是属於内部排序。
• 外部排序 External Sort : 资料量较大，需透过其它储存装置 (Disk, File) 辅助，外部排序通常会分次载入部份的资料到记忆体，用内部排序演算法排序後再回存或合并结果

稳定与不稳定排序法

• 稳定排序法 stable sorting : 相同的值排序前後顺序皆相同
• 不稳定排序法 unstable sorting : 相同的值排序前後顺序可能会对调

简单与高等排序法

• 简单排序法 : 排序演算法简单，但执行时间较长。
• 高等排序法 : 排序演算法复杂，执行时间较短。

常见的排序演算法

排序演算法的简要比较，来自维基百科

气泡排序 bubble sort

气泡排序法是利用反覆进行相邻的两个值两两比对，若顺序错误就进行交换。因移动时最小的数很像水中的气泡慢慢浮到数列顶端所以称为气泡排序，也称泡沫排序法。以下例图为从右到左比较，也有看到有人从左到右比较，不过概念都相同，只是程序写法会有些差异。

假设现在有一堆乱序数列要由小至大做排序

先比较 4 跟 2 ，因 4 的值较大所以维持不变

再往前比较 2 跟 1，2 的值较大所以也维持不变

再往前比较 1 跟 ３

喔这时发现 1 的值比 3 小！

所以将 1 跟 3 的位置做交换

交换完成後，再向前比较，这次是比较 1 跟 5

因为 1 的值比较小，所以跟 5 交换

这时第一轮的排序就结束了，可以发现数列中的最小值 1 已经排到数列的最前面了～

剩余的乱序数列再从头开始比较，跟刚刚一样先比较 4 跟 2，因为 4 比较大所以维持不变

再比较 2 跟 3，此时 2 比 3 小，所以跟 3 做交换

再比较 2 跟 5 ，因 2 比 5 小，所以与 5 做交换

这时 2 已经到数列的正确位置，排序第二轮就结束了

後面未排序的数列如同上述一样，再重新比对与交换，直到所有值符合由小到大排序，就算排序完成。

选择排序 selection Sort

选择排序法是找出数列中的最大或最小值，并与数列起始位置的值交换，反覆操作直到排序完成为止。

来用选择排序排跟刚刚一样的乱数

先找出数列中的最小值，这边找到是 1

让最小值 1 直接跟最前方的数值交换

如此一来，第一轮的排序就完成了。

再从为排序的值中找最小值，於是找到最小值是 2

让 2 与最前方的为排序的数值做交换

於是第二轮也结束了，1 跟 2 都排序好了～

跟刚刚一样，再从为排序的值找最小值，这边找到是 3

3 再跟最前方未排序的数值做交换

第三轮结束

再找未排序的最小值

做交换

然後将啷～排序就完成啦～选择排序法很简单吧！

插入排序 Insertion Sort

插入排序是依序将未排序的资料一一由後向前扫描，并将数插入至对应的位置。

跟刚刚一样的乱数～

第一个值先定位，第一轮就算完成了

再来由未排序的值 3 来往前比较

因 5 大於 3 ，所以两个位置需交换

换到左边没有大於自己的数值为止，第二轮结束

再来由未排序的 1 来做排序

因为 5 大於 1，所以交换

1 再往前比较，3 也大於 1，所以再交换

换到直到左边没有大於自己的数值为止，第三轮就结束了～

之後以此类推，直到所有直排序完成～

参考资料:
演算法笔记:Sort
[演算法] 排序演算法(Sort Algorithm)

好的～今天就先到这边啦！抱持一个凡事先求有再求好的心态，哈哈哈，我要先去遛狗了明天见掰掰～