xingxinmanong的博客

同样先上这张图最后我们总结一下这八种排序算法：

还是先看一下这张图：下面分析一下基数排序：

归并排序把数组划分成几个小数组，然后小数组成划分，直到每个数组都只有一个元素，然后将相邻的两个数组进行合并，再将合并后的数组继续合并，直到合并成一个数组。总体的思想是先拆分再合并。

先看一下下面这张图下面分析选交换排序之快速排序：快速排序的思想是先选择一个基准元素（一般取第一个元素），然后对剩下的元素作两端遍历，左边找到比基准元素大的元素，右边找到比基准元素小的元素，两者交换，重复下去直到low>high，再把基准元素跟high交换。这样一遍下来，基准元素左边的元素都比基准元素小，基准元素右边的元素都比基准元素大。然后对基准元素左边和右边分

同样的先上这张图下面分析交换排序之冒泡排序：冒泡排序和选择排序很相似，都是遍历一趟把最大的元素放到最后面，但选择排序属于选择排序，而冒泡排序属于交换排序，原因在于冒泡排序在找最大元素的时间，两两比较之后会作交换，这样使得一趟排序下来不仅把最大元素放到了后面，同时让前面的元素也更加有序。原版的冒泡排序较之选择排序效率上不仅没有提高，反而会更差。因为冒泡排序同样也需

同样的先上这张图下面分析希尔插入排序：希尔排序将序列根据增量d分成几个子序列，对每个子序列作插入排序。然后把增量d变为d/2，重复这个过程直到d=1，这时的希尔排序其实就是插入排序。希尔排序的算法效率与增量因子有关，目前还没有确定的最好因子，其时间复杂度可认为是O(nlogn)。希尔排序不需要额外的辅助空间，其空间复杂度为O(1)。希尔排序在对每

同样的先上这张图下面分析插入排序：插入排序每次取一个元素插入到已排好序的序列中。由于前面的序列已经排好序，我们只需要从这个序列的后面开始查找，找到第一个大于待插入元素的位置，将该位置后面的元素全部往后移一个位置，并把待排元素插入到该位置之后。插入排序外层循环选择待排元素，时间复杂度为O(n)，内层循环找插入位置，最好情况是直接插入到最后，时间复杂度为O(1），最坏情况可能是

同样的先上这张图下面看一种较为复杂的选择排序 ——堆排序：首先来看一下什么是堆，堆用一个一维的数组模拟二叉树的结构，即堆数组的第一个元素为第二、第三个元素的父结点，即第i(i从0开始)个元素是第2i+1和第2i+2个元素的父结点，由此我们可以计算最后一个结点的父结点，设为j。由j=2n+1（n为偶数）和j=2n+2（n为奇数）得j=floor(n/2)。知道了堆的定义之后我们用

选择排序第一次从头遍历n个元素，找到最大（最小）的元素并放到最后。第二次从头遍历n-1个元素，同样找到最大的元素，放到n-2（即第n-1个元素）的位置。以此下去，直到只剩下第一个元素，排序结束。选择排序简单粗暴，实现起来比较容易，外层循环控制已经排好序的个数，内层循环遍历前n个元素找到最大元素放到n-1位置。也正是因为它的简单粗暴