排序+查找.ppt.ppt

说出你所知道的所有排序方法： 稳定的-一个序列中的相同的元素在排序完毕之后，他们顺序仍然不会改变 　　冒泡排序（bubble sort） — O(n^2） 　　鸡尾酒排序(Cocktail sort，双向的冒泡排序) — O(n^2） 　　 插入排序（insertion sort）— O(n^2) 　　桶排序（bucket sort）— O(n); 需要 O(k) 额外空间 　　计数排序(counting sort) — O(n+k); 需要 O(n+k) 额外空间 　　归并排序（merge sort）— O(nlog?n); 需要 O(n) 额外空间 　　原地合并排序— O(n^2) 　　二叉排序树排序 （Binary tree sort） — O(nlog?n)期望时间； O(n^2)最坏时间； 需要 O(n) 额外空间 　　鸽巢排序(Pigeonhole sort) — O(n+k); 需要 O(k) 额外空间 　　基数排序（radix sort）— O(n·k); 需要 O(n) 额外空间 　　Gnome 排序— O(n^2) 图书馆排序— O(nlog?n) with high probability，需要 （1+ε)n额外空间 不稳定的 　　选择排序（selection sort）— O(n^2) 　　希尔排序（shell sort）— O(nlog?n) 如果使用最佳的现在版本 　　组合排序— O(nlog?n) 　　堆排序（heapsort）— O(nlog?n) 　　平滑排序— O(nlog?n) 　　快速排序（quicksort）— O(nlog?n) 期望时间，O(n^2) 最坏情况； 对于大的、乱数列表一般相信是最快的已知排序 Introsort— O(nlog?n) 　　Patience sorting— O(nlog?n+?k) 最坏情况时间，需要 额外的 O(n+?k) 空间，也需要找到最长的递增子串行（longest increasing subsequence） 　　 不实用的排序算法 　Bogo排序— O(n×?n!) 期望时间，无穷的最坏情况。 　　Stupid sort— O(n^3); 递归版本需要 O(n^2) 额外存储器 　　珠排序（Bead sort） — O(n) or O（√n)，但需要特别的硬件 　　Pancake sorting— O(n)，但需要特别的硬件 　　stooge sort——O（n^2.7）很漂亮但是很耗时 简单的排序： 冒泡排序：依次比较相邻的两个数，将小数放在前面，大数放在后面 选择排序：在每趟排序中选出最小关键字的记录 插入排序：每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。 快速排序 归并排序 两种排序方式的比较 （有兴趣的同学可以自己研究一下堆排序，计数排序和基数排序） Sort函数和Qsort函数 二分查找 (有兴趣的同学可以自己研究一下三分查找) Trie-字典树 数据结构网站： /barcode/sort.html -排序的演示网站 /sjjg/datastructure/ds/web/main.htm-数据结构网站 * * *