09期 | 一本书学会数据结构(二)

2018-08-19 本文已影响8人程序员星星_

你好，很高兴遇见你.jpg

编者按：8.20-8.25

先放一张总图吧~

八大排序算法比较.png

八大排序思路& 算法

[1]选择排序：
1到N-1中找到最小元素，与第一个元素互换位置，依次执行下去。

[2]简单排序：冒泡排序&插入排序
冒泡排序和插入排序区别：
共同点：

[3]希尔排序：
思路：D=N/2，D/=2，不断执行插入排序。
Hibbard 增量序列：Dk =2^k –1 相邻元素互质 & Sedgewick增量序列

[4]堆排序：建立最大堆，第一个元素与最后一个元素互换位置，剩下结点继续调整成最大堆。

[5]归并排序：
递归算法：左右两边分别递归排序，最后再合并在一起。
非递归算法：n个有序子序列，相邻两个元素进行归并，每个子序列包含两个元素，依次两两合并，最后得到有序序列。

[6]快速排序：
思路：找一个主元，如果左边<主元，不断向右；如果右边>主元，不断向左，如果两个都不满足，跳出while循环，交换直到i>j，最后i位置的元素值和主元进行交换。再左右两半分别递归进行快排。
算法：数据规模充分小，用插入排序；大于某个值用快速排序—递归(占用空间，不断进栈出栈速度慢)

[7]表排序：定义一个table为指针数组，不移动元素，只移动指针，和插入排序思路同

[8]基数排序：应用—整数的排序+多关键字的排序

复杂度最好：堆排序和归并排序，都是NlogN，快速排序最好也是NlogN
稳定：选择排序+插入排序+冒泡排序归并排序+基数排序
不稳定：希尔排序+堆排序+快速排序
额外空间：归并排序数据量大需要；快速排序递归需要O(logN)；O(1)代表不需要

[1]冒泡排序和插入排序的区别：同上

[2]希尔排序：建立在插入排序

[3]快速排序和插入排序的区别：
快速排序：数据规模大，每一次选定一个主元，子集划分完成以后，一次性放到最终位置，再也不会移动
插入排序：数据规模小，每次做了元素交换，元素所在的位置是临时的，一张牌移动了很多次

[4]插入排序和表排序的区别：
插入排序：移动元素
表排序：移动元素指针

散列表定义：符号表—名字Name+属性Attribute
散列函数: h(key) = key mod TableSize (求余)
装填因子:α= n / m，n为元素个数，m为散列表空间大小

散列表基本思想:
(1)以关键字key为自变量，通过一个确定的函数 h(散列函数)，计算出对应的函数值h(key)，作为数据对象的存储地址。
(2)可能不同的关键字会映射到同一个散列地址上，即h(keyi) = h(keyj)(当keyi ≠keyj)，称为冲突。

散列函数构造：数字关键词&字符关键词
冲突处理办法：开放地址法&链地址法
散列表的性能分析：线性探测法&平方探测法和双散列探测法&分离链接法：公式