潍坊市论坛

注册

 

发新话题 回复该主题

数据结构第十章排序 [复制链接]

1#
排序

目录

第10章排序

了解排序的基本概念(数据序列、关键字、稳定性、排序分类)。

熟练掌握各种内排序算法(直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、归并排序)的思想及其实现。

10.2插入排序

直接插入排序

希尔排序

10.3交换排序

起泡排序

快速排序

10.4选择排序

选择排序

归并排序

掌握上述6种排序算法的时间复杂度、空间复杂度和稳定性,能够根据实际情况选择适当的排序算法解决问题。

第10章排序了解排序的基本概念(数据序列、关键字、稳定性、排序分类)。

数据序列:

主关键字(key):某个数据项可以唯一地确定一个数据元素

注:当按照数据序列的主关键字进行排序时,排序结果是唯一的,否则排序结果不唯一。

排序方法的稳定性/p>

任意两个相等的数据,排序前后相对位置仍然一样

依排序策略的不同(以下加粗的的6种排序必须掌握)

插入排序(直接插入、折半插入、2-路插入、表插入、希尔)

交换排序(起泡排序、快速排序)

选择排序(简单选择排序、树形选择排序、堆排序)

归并排序

基数排序

排序算法的空间复杂度

若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间是O(1),则称之为就地排序。

反之则称为非就地排序。

熟练掌握各种内排序算法(直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、归并排序)的思想及其实现。10.2插入排序直接插入排序

先将拍好序的放到前面,再将没拍好的第一个依次和前面的进行对比,选出合适的位置放入,前面排好的在插入位置之后的依次往后移一位

注:

设待排序对象个数为n,则该算法的主程序执行n-1趟。

最好情况下,排序前对象已按排序码从小到大有序,每趟只需与前面有序对象序列的最后一个对象比较1次,移动0次对象,总的排序码比较次数为n-1。

希尔排序

改进的直接插入

若数据序列接近有序,则时间效率越高;

当n较小时,时间效率也较高。

10.3交换排序起泡排序

比较相邻记录,将关键字最大的记录交换到n-i+1的位置上

最坏:N*(N-1)/2

快速排序

思想:

具体操作:

递归法:

1.先以第一个元素为key(枢纽),设置两个变量i、j,排序开始的时候:i=0,j=N-1;

2.然后i++开始往后移动,j--开始往前移动,直到找到一个i,第i位的值大于key,再找到一个j,第j位的值小于key

3.则交换第i位和第j位的值

4.继续操作,重复2和3步骤,直到i=j;则将现在的i位置上的值和key交换。这个时候key前正好都是小于它的数,后面都是大于它的数,从而key正好到了排好序后正确的位置。

5,之后将第i位之前和i之后的数分别独立出,进行1,2,3,4操作,直到最后每个独立序列中支有一个元素,那么快排完成。

最好情况每次选择的主元都是在数组的正中间,将数组一份为二;

选主元:抽取几个数选择中位数(一般是头中尾三个)

10.4选择排序选择排序

每一趟(例如第i趟,i=1,2,…,n-1)在后面n-i+1个待排序记录中选出排序码最小的记录,作为有序序列中的第i个记录。待到第n-1趟作完,待排序记录只剩下1个,就不用再选了。

归并排序

将两个或两个以上的有序表合并成一个新的有序表。

if(i=m)for()TR[k..n]=SR[i..m];

//将剩余的SR[i..m]复制到TR

if(j=n)for()TR[k..n]=SR[j..n];

//将剩余的SR[j..n]复制到TR

掌握上述6种排序算法的时间复杂度、空间复杂度和稳定性,能够根据实际情况选择适当的排序算法解决问题。

简单快捷希尔不稳定

当待排记录序列按关键字顺序有序时

直接插入排序和起泡排序能达到O(n)的时间复杂度;

快速排序的时间性能蜕化为O(n2)

选择排序,归并排序?的时间性能不随记录序列中关键字的分布而改变。

1、总排序趟数与初始状态无关的有:(除了快速排序其他都是)2、算法复杂度与初始状态无关的有:归并排序、选择排序3、元素总比较次数与初始状态无关的有:选择排序4、元素总移动次数与初始状态无关的有:归并排序

这类排序法可能达到的最快的时间复杂度为O(nlogn)--快速排序

初始序列大量有序用:插入排序

预览时标签不可点收录于话题#个上一篇下一篇
分享 转发
TOP
发新话题 回复该主题