第六章：数据结构与算法-part3:数据结构算法提升

一、排序算法

排序是数据处理过程中经常使用的一种重要的运算，排序的方法有很多种，本节主要讨论内排序的各种算法，并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行讨论。

1、什么是排序？

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如:将下列关键字序列:49,38,65,97,76,13, 27,49,调整为13,27，38,49,49, 65, 76, 97

2、排序算法的稳定性

排序算法的稳定性: 如果在对象序列中有两个对象r[i]和r[j]，它们的关键字 k[i] == k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象rr 仍在对象rr;的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。(值相同的两个不同位置上的数，在排序后，如果前后位置发生变化就不稳定。)

3、排序算法分类

按排序过程中使用到的存储介质来分，可以将排序分成两大类序和外排序。内排序是指在排序过程中所有数据均放在内存中处理，不需要使用外存的排序方法。而对于数据量很大的文件，在内存不足的情况下，则还需要使用外存，这种排序方法称为外排序。
内部排序：

• 分类：插入排序，交换排序，选择排序，归并排序，基数排序
  
  

1.1 插入排序

基本思想：每一轮比较值在有序序列R中的位置

1、实现”一趟插入排序“可分三步进行：

1、直接插入排序

代码实现：

直接插入排序的时间复杂度：

2、折半插入排序

对于数据量不大时可以用直接插入排序，对于数据量较大时，选择折半插入排序。
折半插入排序基本思想是: 设在顺序表中有一 个对象序列 71],…, v[n-1]。其中，1],…, v[i-l] 是已经排好序的对象。在插入 i 时，利用折半搜索法寻找 vij的插入位置

3、希尔排序

基本思想:对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。
具体做法：


例：

1.2、交换排序法

交换排序是通过交换进行排序的方法，基本思想是两两比较待排序对象的关键字，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之，直到所有对象都排好序为止。

1、起泡排序

起泡排序的基本方法是:设待排序对象序列中的对象个数为n。最多作 n-1 趟排序。在第 i 趟中顺次两两比较r[j-1].Key和r[j].Key，j = i,i+1，…,n-i-1。如果发生逆序，则交换r[j-1]和r[j]。

起泡排序的过程：

• 起泡排序的结束条件为，最后一趟没有进行“交换记录
• 一般情况下，每经过一趟“起泡”，“i 减一”.(但并不是每趟都如此)
  

2、快速排序

一趟快速排序 (一次划分)。
目标：找一个记录R[i]，以它的关键字作为“枢轴”’，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后

例：



具体实现：


快速排序的效率：
当数据量较大时，效率较高，数据量较小时反而慢。

1.3 选择类排序

1、简单选择排序

效率分析：

二、业务逻辑算法设计

2.1 基本概念和术语

1、查找表：

2、关键字

3、查找


4、平均查找长度（Average Search Length):

2.2 静态查找表

使用线性表表示静态查找表。可用顺序或链式存储结构实现查找操作。
1、查找表的定义

2、基本操作

3、算法实现

4、算法“好”还是“坏”衡量？

• 讨论各种查找算法时，常以算法的效率和存储开销来衡量查找算法的优劣。然而，效率和存储开销常常是相互制约的，很难两者兼顾。
• 效率只是相对的，通常把对关键字的最多比较次数和平均比较次数作为两个基本的技术指标，前者叫做最大查找长度(MSLMaximum Search Length)，后者叫做平均查找长度(ASL，AverageSearch Length)
  

2.3、有序表的查找

• 上述顺序查找表中的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。
• 若以有序表表示静态查找表，则查找过程可以基于“折半”进行

1、折半查找

写在最后：
课看完了，只能说质量不高，全程PPT，没意思，就当记录笔记吧。。。。