以下说法正确的是__。

各排序算法的时间复杂度、空间复杂度、稳定性：

（排序算法的稳定性：排序前后相等元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的）

冒泡排序：

冒泡排序算法需要多次遍历数组（N-1次），在每次遍历中，比较连续相邻的元素。如果一对元素是降序，则互换它们的值；否则保持不变。这样每一次遍历较大的值都沉到了后面：第一次遍历区间为0~N-1，第一次遍历后，最后一个元素成为数组中最大的数；第二次遍历区间为0~N-2，第二次遍历后，倒数第二个元素成为第二大的数……

• 稳定性：稳定。冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。如果两个元素相等，不会把他们俩交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
• 时间复杂度：O(n^2)。需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n^2)，最坏的也是O(n^2)。
• 空间复杂度：O(1)。需要一个临时变量来交换元素位置，所以空间复杂度O(1)。

选择排序：

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择最小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。

• 稳定性：不稳定。在一趟选择中，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比如序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
• 时间复杂度：O(n^2)。需要两个for循环，平均时间复杂度为O(n^2)，最坏的也是O(n^2)。
• 空间复杂度：O(1)。需要一个临时变量来交换元素位置，所以空间复杂度O(1)。

插入排序：

插入排序是重复的将新的元素插入一个排好序的子线性表中，直到整个线性表排好序。插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置......

• 稳定性：稳定。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变。
• 时间复杂度：O(n^2)。需要两个for循环，平均时间复杂度为O(n^2)。最坏时间O(n^2)，最好时间O(n)，就是不用交换。
• 空间复杂度：O(1)。需要一个临时变量来交换元素位置，所以空间复杂度O(1)。

归并排序：

归并排序是使用分而治之法对数组排序。将数组分为两半，对每部分递归地应用归并排序。在两部分都排好序后，对它们进行归并。先什么都不管，把数组分为两个子数组，一直递归把数组划分为两个子数组，直到数组里只有一个元素，这时候才开始排序，让两个数组间排好序，依次按照递归的返回来把两个数组进行排好序，到最后就可以把整个数组排好序。

做法：分成两个函数：1）划分数组；2）归并两个有序数组。划分时创建两个临时数组，将数组前半部分与后半部分复制到临时数组中。归并时将它们先排序再归并到原始数组中。

• 稳定性：稳定。在短序列只有1个或2个元素时，1个元素不会交换，2个元素如果大小相等也不交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。
• 时间复杂度：O(nlogn)。归并排序将数组划分为两个子数组，使用同样的算法对子数组进行递归排序，然后将子数组进行归并，因此T(n)=T(n/2)+T(n/2)+归并用时。第一项是对数组的前半部分排序所需的时间，第二项是对数组的后半部分排序所需的时间。要归并两个数组，最多需要n-1次比较来比较两个子数组中的元素，以及n次移动将元素移到临时数组中，因此归并总时间为2n-1。因此T(n)=T(n/2)+T(n/2)+2n-1=O(nlogn)。
• 空间复杂度：O(n)。归并排序每次递归需要用到一个辅助表，长度与待排序的表相等，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，这样每一个时刻需要O(n)个空间即可，因而空间复杂度还是O(n)。

快速排序：

 　　在数组中选择一个基准元素（pivot），将数组分为两部分，使得第一部分中的所有元素都小于等于pivot，第二部分的所有元素都大于pivot。对第一部分递归的应用快速排序算法，然后对第二部分递归的应用快速排序算法。

• 稳定性：不稳定。快速排序有两个方向，右边的j下标一直往左走，当a[j] > pivot，左边的i下标一直往右走，当a[i] <= pivot。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j，交换a[j]和pivot，完成一趟快速排序。在基准元素pivot和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在基准元素5和3交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在基准元素和a[j]交换的时刻。
• 时间复杂度：O(nlogn)。
  • 最差情况下，划分由n个元素构成的数组需要进行n次比较和n次移动，划分所需时间为O(n)，在最差情况下，基准元素每次会将数组划分为一个大的子数组和另外一个空数组，这个大的子数组的大小是在划分前的子数组的大小上减1，该算法需要()+()+...+2+1=O(n^2)时间。
  • 最佳情况下，基准元素每次将数组划分为规模大致相等的两部分，则T(n)=T(n/2)+T(n/2)+划分用时，其中前两项表示在两个子数组上进行递归的快速排序用时，划分用时为O(n)，则T(n)=T(n/2)+T(n/2)+n=O(nlogn)。
• 空间复杂度：O(logn)。快速排序每次递归都会返回一个中间值的位置。最优的情况下空间复杂度为O(logn) ，即每一次都平分数组的情况；最差的情况下空间复杂度为O(n) ，即退化为冒泡排序的情况。

堆排序：

堆排序使用一个二叉堆，它首先将所有的元素添加到一个堆上，然后不断移除最大的元素以获得一个排好序的线性表。

该二叉堆是一个完全二叉树，该二叉树具有如下属性：首先它是一个完全二叉树（二叉树的每层都是满的，或者最后一层没填满并且最后一层的叶子都是靠最左放置的），其次每个结点大于或等于它的任意一个孩子。

• 稳定性：不稳定。
• 时间复杂度：O(nlogn)。

设h表示n个元素的堆的高度。由于堆是一颗完全二叉树，所以第一层有1（2^0）个结点，第二层有2（2^1）个结点，....，第h层有2^(h-1)个结点，最后第h+1层最少有1个最多有2^h个结点。因此1+2+...+2^(h-1)<n<=1+2+...+2^(h-1)+2^h，即2^h < n+1 <= 2^(h+1)，所以h < log(n+1) <= h+1。所以堆的高度为O(logn)。

• • 由于add方***最追踪从叶子结点到根节点的路径，因此向堆中添加一个新元素最多需要h步，所以建立一个包含n个元素的数组的初始堆需要O(nlogn)时间。
  • 因为remove方法要追踪从根节点到叶子结点的路径，因此从堆中删除根节点后重建堆最多需要n步。由于要调用n次remove方法，所以由堆产生一个有序数组需要时间为O(nlogn)。
• 空间复杂度：O(1)。只是需要一个临时变量来交换元素位置，所以空间复杂度O(1)。