8大排序3大查找
每天都在叫嚣自己会什么技术，什么框架，可否意识到你每天都在被这些新名词、新技术所迷惑，.NET、 XML 等等技术固然诱人，可是如果自己的基础不扎实，就像是在云里雾里行走一样，只能看到眼前，不能看到更远的地方。这些新鲜的技术掩盖了许多底层的原理，要想真正的学习技术还是走下云端，扎扎实实的把基础知识学好，有了这些基础，要掌握那些新技术也就很容易了。
要编写出优秀的代码同样要扎实的基础，如果 排序和查找 算法学的不好，怎么对程序的性能进行优化 ？废话不多说，本文要介绍的这些排序算法就是基础中的基础，程序员必知！
1 、直接插入排序
（ 1 ）基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排
好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
也是排好顺序的。如此反复循环，直到全部排好顺序。
（ 2 ）实例
3 、简单选择排序
（ 1 ）基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
（ 2 ）实例：
4 、堆排序
（ 1 ）基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
（ 2 ）实例：
初始序列： 46,79,56,38,40,84
建堆：
交换，从堆中踢出最大数
剩余结点再建堆，再交换踢出最大数
依次类推：最后堆中剩余的最后两个结点交换，踢出一个，排序完成。
5 、冒泡排序
（ 1 ）基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
（ 2 ）实例：
6 、快速排序
（ 1 ）基本思想：选择一个基准元素 , 通常选择第一个元素或者最后一个元素 , 通过一趟扫描，将待排序列分成两部分 , 一部分比基准元素小 , 一部分大于等于基准元素 , 此时基准元素在其排好序后的正确位置 , 然后再用同样的方法递归地排序划分的两部分。
（ 2 ）实例：
上图中将待排序列分成两部分 , 一部分比基准元素小 , 一部分大于基准元素 , 然后对这两部分重复上图的求解过程。
（这只是快速排序的一种实现方式，个人认为比较容易理解）
7 、归并排序
（ 1 ）基本排序：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
（ 2 ）实例：
8 、基数排序
（ 1 ）基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
（ 2 ）实例：
稳定性说明： 排序前 ， 2 （或者更多） 个相等的数在序列的前后位置顺序和排序后它们 在序列中的 前后位置顺序 一样。
实例：
待排序数列： 5,4, 8 ,6,1, 8 ,7,9
排序结果： 1,4,5,6,7,8,8,9
稳定： 1,4,5,6,7, 8 , 8 ,9
不稳定： 1,4,5,6,7, 8 , 8 ,9
说明：对比红色的8和紫色的8，看他们排序前后的位置。排序前，红8在紫8前面，如果排序后红8仍然在紫8前面，则排序算法稳定，否则不稳定。
现在 我们 分析一下 8 种 排序算法的稳定性。
（ 请网友结合前面的排序基本思想来理解排序的稳定性（ 8 种排序的基本思想已经在前面说过，这里不再赘述） 不然可能有些模糊）
（ 1 ）直接 插入排序 ： 一般插入排序， 比较是从有序序列的 最后一个元素 开始，如果比它大则直接插入在其后面，否则一直 往前比 。如果 找到 一个和插入元素相等的，那么 就 插入 到这个 相等元素的后面。插入排序是稳定的。
（ 2 ） 希尔排序 ： 希尔排序是按照不同步长对元素进行插入排序，一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，稳定性 就会被破坏 ，所以 希尔 排序不稳定。
（ 3 ）简单 选择排序 ： 在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。 光说可能有点模糊，来看个小实例： 8 5 8 4 10 ， 第一遍扫描， 第 1 个元素 8 会和 4 交换，那么原序列中2个 8 的相对前后顺序 和原序列不一致了 ，所以选择排序 不 稳定。
（ 4 ） 堆排序 ： 堆排序的过程是从第 n/2 开始和其子节点共 3 个值选择最大 ( 大顶堆 ) 或者最小 ( 小顶堆 ), 这 3 个元素之间的选择当然不会破坏稳定性。但当为 n/2-1, n/2-2, ... 这些父节点选择元素时，有可能第 n/2 个父节点交换把后面一个元素交换过去了，而第 n/2-1 个父节点把后面一个相同的元素没有交换，所以堆排序并不稳定。
（ 5 ） 冒泡排序 ：由前面的内容可知，冒泡排序 是相邻的两个元素比较，交换也发生在这两个元素之间 ，如果两个元素相等，不用交换。所以冒泡排序稳定。
（ 6 ） 快速排序 ： 在中枢元素和 序列中一个元素 交换的时候，很有可能把前面的元素的稳定性打乱 。还是看一个小实例： 6 4 4 5 4 7 8 9 ，第一趟排序， 中枢元素 6 和 第三个 4 交换就会把元素 4 的 原序列破坏 ，所以快速排序 不稳定。
（ 7 ）归并排序： 在分解的子列中，有 1 个或 2 个元素时， 1 个元素不会交换， 2 个元素如果大小相等也不会交换。在序列合并的过程中，如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，所以，归并排序也是稳定的。
（ 8 ） 基数排序 ： 是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
8种排序的分类，稳定性，时间复杂度和空间复杂度总结：
未完待续，下一篇将主要介绍三大查找，敬请期待！
http://www.cnblogs.com/fredcyt/archive/2012/05/07/2488863.html
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息