排序总结

一、插入排序

插入排序分为直接插入、二分插入和希尔排序；

直接插入排序

类似于扑克的排序，将待排序列分为有序序列和未排序序列两部分，从未排序序列中选取第一个数据，插入到有序序列中；时间复杂度为O(n2)；

示例：

分组插入排序（希尔排序）

希尔排序相当于把待排序列分为多个组，每组的数据之间间隔一个关键字key,对每一组执行直接插入排序，所有组完成排序之后，整个序列达到一个相对有序的状态；再次减小key，重新分组、直接插入排序，使得序列不断地向着相对有序的状态前进；最终key值减小到1之后的最后一次插入排序完成后，排序完成；

整体上希尔排序相当于在直接插入排序的基础上，让数据进入到排序的位置的过程中跳了几次，不需要每次都对大于该数据的数据进行进行比较，移位；

key的选取无规定，感觉每次key/=2比较好；

时间复杂度为O（nlgn）

示例：

二分插入排序

二、选择排序

选择排序从第一个位置开始排，选择后面未排序序列中的最小值，与已排序序列的最末尾的后一个数据进行交换位置，直到未排序序列大小变为零。

时间复杂度：O(n2)；对于随机序列，由于选择排序要对所有未排序数据进行比较，时间可以认为是直接插入排序的两倍；

示例：

二元选择排序：

是对选择排序的改善，每次选择时，分别在未排序序列中选择出最大数据和最小数据，并且分别与两个排序序列的待交换位置的数据进行交换。

三、堆排序

大根堆满足arr[i]>arr[2*i+1]&&arr[i]>arr[2*i+2] i从0开始；

小根堆满足arr[i]

利用大根堆、小根堆的最大值最小值在第一个位置的特性，进行堆排序；

1．首先对数组按照堆的特性创建一个大根堆或者小根堆；

Øn个节点的完全二叉树，第n个节点的父节点为n/2

Ø从第n/2节点开始向前，每个节点与两个子节点中较大(小)的一个进行比较，适时交换位置，使该子树成为堆；

Ø交换了位置的父节点和子节点，子节点需要继续与其子节点进行调整，父节点的调整交给for循环；

示例：

2．对创建出来的堆，将其最大值或者最小值与最后一个位置的数据进行交换位置，然后对前n-1个数组元素进行调整，继续成为堆，继续与倒数第二个位置的数据交换，直到全部交换完毕。所以进行升序排序，使用大根堆，进行降序排序，使用小根堆。

算法的核心部分在于堆的调整算法heap_adjust，堆的创建和交换数据之后的调整都需要使用该算法；

示例：

可以使用递归来实现该算法，也可以使用一个while语句来实现；

时间复杂度也为：O(nlgn )；

四、冒泡排序

冒泡排序为将数据与其后面的数据进行比较，升序排序的时候，则把较大的数据移动到靠后的位置，不断的比较，把大的数据挨个挤到后面去；

时间复杂度为O（n2）；

可以改为二元冒泡，向后置位冒大的，同时向前置位冒小的；

五、快速排序

快速排序的基本思路为：将一个无序序列分为两部分，怎么分？找一个数据，放在它有序的时候该在的位置，所有小于该数据的数据放置在它前面，所有大于该数据的放置在它后面，这个数据怎么选，通常选择无序序列的第一个数据。分为两部分之后，继续递归。

Ø如何使用一个数据将序列分为大于和小于的两个部分：将第一个数据取出来，则第一个位置空闲，从末端开始遍历，找到一个小于该数的数据移动到第一个位置，该数据位置空闲，再从首端开始遍历，找到一个大于该数的数据，移动至后端。两端轮流向中间遍历，直至碰头，找到该数据的合适位置。

Ø分为两部分之后，继续递归；

快速排序时间复杂度：O(nlogn)，不稳定

六、归并排序

归并排序采用分治的思想，将一个无序的序列不断的二分，分割为大小为一的时候，则序列是有序的，再不断的将两个有序序列合并，最终整个序列有序。用到递归。

在时间上，比较好的排序算法是希尔排序，堆排序，快速排序，归并排序；这几个应该是重点。

时间复杂度：O(nlogn)