你好，很高兴遇见你.jpg
编者按：8.20-8.25
先放一张总图吧~
八大排序算法比较.png
八大排序思路& 算法
[1]选择排序：
1到N-1中找到最小元素，与第一个元素互换位置，依次执行下去。
[2]简单排序：冒泡排序&插入排序
冒泡排序和插入排序区别：
共同点：
- 都是比较相邻位置
- 稳定：相等元素都不做交换
- 最好情况复杂度：T=O(N)
- 最坏情况复杂度：T=O(N^2)
不同点： - 冒泡排序：不断比较相邻位置，把最大元素放到最后
- 插入排序：第一个元素已排好序，新元素小于已排序元素，位置全部向后挪，最后新元素赋值给i（扑克牌）
[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)，称为冲突。
散列函数构造：数字关键词&字符关键词
冲突处理办法：开放地址法&链地址法
散列表的性能分析：线性探测法&平方探测法和双散列探测法&分离链接法：公式
小贴士
本文总结自数据结构视频教程第9讲~第11讲：
http://mooc.study.163.com/learn/1000033001?tid=2001531009#/learn/content
网友评论