排序算法

选择排序

基本思想

1) 将序列划分成有序区（左边）和无序区（右边）
2) 初始时，有序区为空，无序区为序列全部
3) 每一次选择出无序区中最小元素，与无序区中第1个元素交换，成为有序区的最后一个元素

如：对数据48,70,8,30,23,11,15进行选择排序，写出每趟的结果

时间复杂度：
O(n2)

冒泡排序

基本思想

1) 将序列划分成有序区（右边）和无序区（左边）
2) 初始时，有序区为空，无序区为序列全部
3) 每一次“起泡”相邻元素依次两两比较，将较大/小者交换到后面，成为有序区的第一个元素

如：对48，70，8，30，23，11，15进行冒泡排序

第二趟：
8,30,23,11,15,（48, 70）
第三趟：
8,23,11,15,（30,48, 70）
第四躺：
8,11,15,（23,30,48, 70）
第五躺：
8,11,（15,23,30,48, 70）
第六趟：
8,（11,15,23,30,48, 70）

时间复杂度：
最好O(n)；最坏O(n^2)；平均O(n^2)

归并排序

基本思想：
将序列划分成两个长度相等的子序列，分别进行排序，最后将两个有序序列合并

如：对数据48,70,8,30,23,11,15,28进行归并排序

时间复杂度：
O(nlog2n)

快速排序

基本思想：

1) 划分：选定一个数做为轴值，把序列分成比轴值小（左边）和比轴值大（右边）两个子序列
2) 求解子问题：分别对两个子序列进行轴值划分

划分步骤：

1) 选择区域内第一个元素为轴值；
2) 设立i，j分别指向区域第一和最后一个元素；
3) 重复以下步骤：

1. j往前走，寻找比轴值小的元素与轴值交换
2. i住后走，寻找比轴值大的元素与轴值交换

如：快速排序 34,20,71,26,23,9,44,35，求解思路为：

时间复杂度：
最好（子序列等长）O(nlog2n)、最坏（基本有序）O(n^2)、平均O(nlog2n)

快速排序的特点为：

1. 快速排序对已有序（不管是正序还是逆序）的序列，效率最差。
2. 每次划分实质上是找出轴值在排序后的位置，即每次划分是对轴值进行排序
3. 假如某次划分后，轴值所在位置为i，实质上表明该轴值在序列中是第i小的值（注意，这里说的序列是参与划分的序列），因此可借助快速排序的划分操作实现“求序列第i小数”

插入排序

基本思想：

1) 将序列划分为有序区和无序区。有序区为序列第一个元素，无序区为剩下的元素。
2) 每一次操作都将无序区的第一个元素ri与有序区里从第一个元素开始比较，直到找到一个元素rj比ri大；如果找不到元素比ri大，则ri要插入的位置为序列尾部
3) 将ri插到rj前面，调整有序区中其它元素位置

如：对数据34,20,71,26,23,9,44进行插入排序

时间复杂度：

最好（基本有序）：O(n)，最坏（逆序）：O(n^2)，一般情况O(n^2)

堆排序

基本思想：

1) 根据待排序序列，建立堆。升序排序采用大根堆；降底排序采用小根堆
2) 堆顶元素为最大值（大根堆）或最小值（小根堆），将该元素与最后一个元素交换并移入有序区
3) 调整无序区为一个堆结构
4) 重复（2）和（3）直到无序区剩一个元素

1. 构建初始堆
2. 调整为大根堆（升序）或小根堆（降序）
3. 将堆顶值与从尾部开始的值交换，每交换一次就需要调整一次堆

如：4，6，8，5，9