排序算法

1 冒泡排序

如果是对n个数升序排序，冒泡排序每趟排序把一个最大值浮到最后。

第一趟，针对n个数，比较第1个数和第2个数，如果1数比2数大，交换两数位置，然后比较第2个位置的数和第3个位置的数，大数放后边，一直比较到第n-1个数和第n个数，完成一趟排序，这趟排序，将n个数中的max移动到了第n个位置；

第二趟，针对前n-1个数，挪动这n-1个数中的max到第n-1个位置；

第i趟，针对前n-i+1个数，挪动max到第n-i+1个位置；

n个数最多需要n-1趟，完成排序。

两层for循环可以搞定。

但是这样的方法不是最优，如果某一趟排序过程中，已经没有数发生交换，就是说其实这n个数已经有序了，他还会继续进行剩下的扫描，其实剩下的扫描都是浪费，对于这种情况的一个改进办法就是设置一个flag标志，开始的时候置0，如果排序过程中发生了数据交换，flag置1，每趟结束如果发现flag为0，就可以结束整个排序过程，提高效率。

2 快速排序

如果是对n个数升序排序，快速排序通过选择一个基准，每趟排序把小于基准的放基准左边，大于基准的放基准右边，基准值放中间。

可以选择最后一个元素（最右）作为基准，右指针左移找小于基准的数，找到后与左指针当前指向的数进行交换（相当于挪到左边），右指针停住；左指针开始右移，找大数，与右指针当前指向的数进行交换，左指针停住；重复直到左右指针相遇，将基准值赋给左指针（或者右指针，两人相遇，指向的位置都是相同的）。完成一趟排序。

递归调用快速排序，对基准左边的区间和基准右边的区间分别进行排序。

基准的选择直接影响排序算法的性能，如果每趟排序都将大部分的元素划分到基准一侧，那么快排退化成冒泡，递归调用栈的深度也特别深，为了避免这种情况，可以采用三者取中的办法，从首元素，尾元素，中间元素中取中值作为本趟排序的基准元素。每趟排序前将选取的基准元素与序列中的最右元素交换位置，即可按照上面的算法进行排序。

3 堆排序

对n个元素进行升序排序：

将n个元素构成一个大顶堆；

交换堆的第一个元素和堆的最后一个元素的位置；

将移走最大值元素后的剩下的这些元素构成的序列重新转换成一个堆；

重复这个过程n-1次就可以实现n个元素的升序排列。

调整为大顶堆的步骤：从堆顶元素、左节点、右节点中选择最大值作为堆顶元素，递归实现对所有子树的调整。

建堆的步骤：从数组的一半位置开始，调用调整大顶堆的函数，不断往上建堆。

4 希尔排序

缩小增量排序，将整个待排序的序列划分成若干子序列，分别对子序列进行排序，然后逐步缩小划分子序列的间隔，重复上述操作，直到划分间隔变为1。

排序算法的时间主要消耗在排序时元素的移动上，采用希尔排序，最初间隔的取值较大，因此排序时，元素移动的跨度大，当间隔等于1的时候，序列已经基本有序了，所以不需要特别多的移动就可以完成排序。

间隔的选取方法，序列总长度的一半，后续间隔为前一趟间隔的一半。

5 简单选择排序

从未排序的里面选一个最小值放未排序的最开头，未排序的序列长度减一。

每一趟的选择排序都是从序列里面未排好顺序的元素中选择一个最小元素，如果最小元素不位于未排序子序列的第一个位置，将该元素与第一个元素交换位置。

6 直接插入排序

从无序序列里面拿出一个值，插入到前面已经有序的序列中，让有序序列仍然有序。

有序序列长度变大，无序序列长度缩小。

7 归并排序

分解：计算分裂点，将当前序列一分为二

求解：递归地对两个子区间归并排序，当区间里只有一个元素的时候返回

组合：将已排序的两个子区间归并为一个有序区间

8 性能比较

名称	稳定性	时间复杂度	空间复杂度
冒泡排序	稳定	O(n2)	O(1)
选择排序	不稳定	O(n2)	O(1)
插入排序	稳定	O(n2)	O(1)
快速排序	不稳定	O(nlogn) badO(n2)	O(logn)
堆排序	不稳定	O(nlogn)	O(1)
归并排序	稳定	O(nlogn)	有争议
希尔排序	不稳定	O(nlogn*logn) badO(n2)	O(1)
计数排序	稳定	O(n+m)	O(n+m)
桶排序	稳定	O(n)	O(m)
基数排序	稳定	O(k*n) badO(n2)	-

归并排序适合子序列有序的序列排序；快速排序不适合基本有序的序列排序。