软考29-上午题-排序

一、排序的基本概念

1-1、稳定性

稳定性指的是相同的数据所在的位置经过排序后是否发生变化。若是排序后，次序不变，则是稳定的。

1-2、归位

每一趟排序能确定一个元素的最终位置。

1-3、内部排序

排序记录全部存放在内存中进行排序的过程。

1-4、外部排序

待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

1-5、排序小结（要背）

比较最好时间复杂度，会发现，当待排序的序列基本有序的话，适合采用：

• 直接插入排序
• 希尔排序
• 冒泡排序 

二、直接插入排序

稳定的 

不归位

三、希尔排序

直接插入排序的改进。

基本思想：现将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序；待整个序列中的记录基本有序的时候，再对全体记录进行一次直接插入排序。

示例：

不稳定

不归位 

四、真题1

真题1：

真题2：

 真题3：

真题4：

五、简单选择排序

算法思想：从待排数组中找到最小值，再将最小值与已排好序的数组后一位进行交换。

归位

不稳定 

六、堆排序（简单了解） 

示例：

此时，根元素80是最大的元素，将根元素80和队列最后一个元素10交换，并将80脱离当前序列（归位），此时，新的二叉树不满足大顶堆的规则，则继续调整。

每次调整完得到的根节点都是当前序列的最大元素！！！

归位

不稳定

七、真题2

真题1：

 

真题2：

八、冒泡排序

基本思想：相邻两个元素，俩俩交换。

稳定

归位 

 

九、快速排序

快速排序首先选择了一个基准值，然后分别选择两个指针在数组中一个找大，一个找小，然后进行交换。

通过一趟排序将待排序的记录以基准值为分界，分为独立的两个部分，称为前半区和后半区；前半区均小于基准值，后半区均大于基准值。

然后再分别对这两个部分在进行快速排序，从而使得整个序列有序。

分治：分而治之。

归位

不稳定！！！ 

纠错：空间时间复杂度是：O(log2n)； 

十、真题2

真题1：

真题2：

真题3：

真题4：

十一、归并排序

示例：

 

设计方法：分治法

不归并

稳定

11-1、真题

真题1：

真题2：

 真题3：

真题4：

真题5：

真题6：

十二、排序小结

12-1、简单排序

1、直接插入排序（稳定）

2、冒泡排序（稳定）

3、简单选择排序（不稳定）

时间复杂度都是：O(n^2)

空间复杂度：O(1)

12-2、希尔排序（不稳定）

时间复杂度：O(n^1.3)

空间复杂度：O(1)

12-3、快速排序（不稳定）

分治思想

时间复杂度：O(nlog2n)——性能最好

空间时间复杂度：O(log2n)

但是，当待排序列基本有序的时候，是最坏的情况，时间复杂度退化为：O(n^2)

12-4、堆排序（不稳定）

时间复杂度：O(nlog2n)

空间时间复杂度：O(1)

12-5、归并排序（稳定）

俩俩归并，n/2向上取整

整个归并排序，需要进行log2n趟（向上取整）

空间复杂度：O(n)

时间复杂度：O(nlogn)

12-6、小结-稳定的排序

• 直接插入排序；
• 冒泡排序
• 归并排序

12-7、真题

真题1：

真题2：

真题3：

直接插入排序：局部有序

冒泡：每一趟排序，都将最大的泡泡在最后的位置。