排序算法

慢排: 时间复杂度为Ο(n log n), 外部遍历

1.冒泡: 相邻元素两两比较， 较大的元素下沉, 交换位置

基本思想：
假设待排序的表长为n， 从后向前或从前向后两两比较相邻元素的值，若为逆序，则交换之，直到序列比较完。
这样一回就称为一趟冒泡。这样值较大的元素往下“沉”，而值较小的元素入上“浮”。

2.选择排序

基本思想：
假设排序表为L[1...n],第i趟排序从表中选择关键字最小的元素与Li交换，第一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表有序。

选择排序(Selection sort)的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最大元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

选择排序，标记最小值，循环比较，替换最小值

3.插入

（1）直接插入排序算法
算法思想：将等排序列划分为有序与无序两部分，然后再依次将无序部分插入到已经有序的部分，最后就可以形成有序序列。

插入排序，逐个元素拿出来，与其左边元素逐个对比，碰到比该元素小的元素，则插入在对比元素后

操作步骤如下：
1）查找出元素L（i）在表中的插入位置K；
2）将表中的第K个元素之前的元素依次后移一个位置；
3）将L（i）复制到L（K）。

快排: 时间复杂度为Ο(n log )

1.快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

1.从数列中挑出一个元素，称为 “基准”（pivot），
2.与基准元素比较, 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.递归地（recursive）把小于基准元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

2.归并(合并)排序

归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤：
1.申请空间，使其大小为两个需要排序序列之和，该空间用来存放合并后的序列.
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针达到序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾

3.堆栈排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤：
1.创建一个堆H[0..n-1]
2.把堆首（最大值）和堆尾互换
3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4.重复步骤2，直到堆的尺寸为1

堆的定义如下：n个关键字序列号L[1..n]称为堆，仅当该序列满足：
1）L(i) <= L(2i)且L(i) <= L(2i+1) 或 2)L(i) >= L(2i)且L(i) >= L(2i+1)
满足第一种情况的堆，称为小根堆（小顶堆）；
满足第二种情况的堆，称为大根堆（大顶堆）。

4.希尔(Shell)排序

基本思想：
先将待排序的表分割成若干个形若L[i, i+d, i+2d, ..., i+kd]的“特殊”子表，分别进行直接插入排序，
当整个表已呈“基本有序”时，再对全体记录进行一次直接插入排序。
算法过程：
1）先取一个小于n的步长d1,把表中全部记录分成d1个组，所有距离为d1的倍数的记录放在同一组中，在各
组中进行直接插入排序；
2）然后取第二个步长d2 < d1, 重复步骤1
3）直到dk = 1，再进行最后一次直接插入排序

5.折半插入排序

使用于排序表为顺序存储的线性表
在查找插入位置时，采用折半查找
算法思想是：
1）设置折半查找范围；
2）折半查找
3）移动元素
4）插入元素
5）继续操作1）、2）、3）、4）步，直到表成有序。