学习笔记--数据结构与算法基础（青岛大学-王卓）--第八章排序

视频链接:

学习链接:数据结构与算法基础（青岛大学-王卓）--第八章排序

本章知识框架

@TOC

1.基本概念和排序方法概述

• 什么是排序?

• 排序方法的分类

内部排序和外部排序(按存储介质划分)
内部排序:在内存中进行排序
外部排序:将外部存储的数据传到内存中进行排序,排好后再交给外存

串行排序和并行排序(根据比较器来划分)

比较排序和基数排序(按操作来划分)

原地排序和非原地排序(按辅助空间来划分)

稳定排序和非稳定排序

例子:
稳定排序:

非稳定排序:

自然排序和非自然排序

• 按排序依据原则和按排序所需工作量(学习相关排序算法)

2.插入排序

• 基本思想

• 插入操作

插入的位置:

如何查找插入的位置:

• 直接插入排序

改进一下:

算法:

效率

• 二分插入排序

算法:

算法分析:

• 希尔排序

基本思想:

例子:


特点:

算法：


算法分析:

3.交换排序

• 基本思想

• 冒泡排序

基本思想:

规律:

算法:

算法改进:

算法分析:

• 快速排序

基本思想:



步骤:

算法:


算法分析：


快速排序不适于对原本有序或基本有序的记录序列进行排序。

4.选择排序

• 简单选择排序

基本思想:



算法:

算法分析:

• 堆排序

堆的定义:

例子:


堆排序：

实现堆排序需要解决的二个问题:

解决问题2:

例子:

输出堆顶元素

取堆中最后一个元素替代

比较其左右孩子值的大小，并与其中较小者交换

没有到达叶子,继续循环

再次输出堆顶元素,依次循环以上操作
解决问题1:
堆的建立


调整从第n/2个元素开始，将以该元素为根的二叉树调整为堆


将以序号为n/2 -1的结点为根的二叉树调整为堆


再将以序号为n/2-2的结点为根的二叉树调整为堆(无需调整38<49,38<76)

再将以序号为n/2-3的结点为根的二叉树调整为堆




实现:

进行堆排序

算法:

算法分析:

5.归并排序

• 基本思想

例子:

• 如何将二个有序序列合成一个有序序列

• 算法分析

6.基数排序

• 基本思想

例子:
按个位有序分配,按十位有序分配,按百位有序分配

• 算法分析

7.外排序

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

学习链接:外部排序算法总结

8.各种基本排序总结

• 各种基本排序算法的比较

• 时间性能上看各种排序算法

• 空间性能上看各种排序算法

• 各种排序算法的稳定性能

• 各个排序算法的时间复杂度的下限(最坏时间复杂度)