谈javascript实现八种排序

开学一个月，我多次梦到笔试中出现了数据结构算法，对数据结构的恐惧比任何“怪物”都多。呵呵，看来真的有必要复习一下常用的数据结构，以免“噩梦”成真。

数据组织等编程基础的重要性不用多说，直接进入正题。

排序算法分为内部排序和外部排序。内部排序使用内存，所以这里只讨论内部排序。

1.插入排序：直接插入排序和希尔排序

2.选择排序：简单选择排序和堆排序

3.交换排序：冒泡排序和快速排序

4.合并和排序

5.基数排序

直接插入排序

基本思路：在一组待排序的数字中，假设前面的(n-1)[n=2]个数字已经是有序的，先把第n个数字插入到前面的有序数字中，这样n个数字也是有序的。重复这个循环，直到你知道一切都井井有条。

贝壳的分类

基本思想：算法首先将一组待排序的数字按照一定的增量d(n/2，n为待排序的数字)分成若干组，每组记录的下标相差d，每组中的所有元素直接插入排序，然后以小的增量(d/2)分组，再在每组中直接插入排序。当增量减少到1时，排序在直接插入排序后完成。

简单选择排序

基本思路：在一组待排序的数字中，选择最小的数字与第一个位置的数字进行交换，然后在剩余的数字中找出最小的数字与第二个位置的数字进行交换，从而搜索un直到倒数第二个数字和最后一个数字。

堆排序

基本思想：堆排序是一种树选择排序，是对直接选择排序的有效改进。

含有n个元素的序列(h1，h2，当且仅当它们满足(hi=h2i，hi=2i 1)或(hi=h2i，hi=2i 1)(i=1，2，n/2)。这里只讨论满足前一个条件的堆。从堆的定义可以看出，堆的顶元素(即第一个元素)一定是最大的项(大顶堆)。完全二叉树可以直观地表达堆的结构。堆的顶部是根，其余的是左子树和右子树。最初，待排序的数字序列被视为按顺序存储的二叉树，当堆的根节点数最大时，调整它们的存储顺序使其成为一个堆。然后用堆的最后一个节点交换根节点。然后重新调整之前的数字(n-1)使其成为一个堆。以此类推，直到堆中只有两个节点，并交换它们，最后得到一个有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一个是构建堆，另一个是在堆的顶部和堆的最后一个元素之间交换位置。所以堆排序由两个函数组成。一是建堆的渗透功能，二是反复调用渗透功能实现排序的功能。

冒泡排序

基本思路：在一组要排序的数字中，对范围内当前没有排序的所有数字，从上到下比较调整相邻的两个数，使大的往下沉，小的往上升。也就是说，每当两个相邻的数字进行比较，发现与排序要求相反时，它们就会互换。

快速排序

基本思路：选择一个引用元素，通常是第一个元素或者最后一个元素，通过扫描一次将待排序的列分为两部分，一部分小于引用元素，另一部分大于等于引用元素。此时，引用元素在被排序后处于其正确的位置，然后用相同的方法递归排序被划分的两个部分。

合并分类

基本排序：Merge排序法是将两个(或多个)有序表合并成一个新的有序表，即把要排序的序列分成若干个子序列，每个子序列都是有序的。然后有序子序列被合并成一个整体有序序列。

基数排序

基本思路：将所有需要比较的值(正整数)统一为相同的位数长度，在位数较短的前面补零。然后，从最低位开始，依次排序一次。这样，从最低阶到最高阶，序列就变成了有序序列。

代码演示地址：http://lovermap.sinaapp.com/test/sort.html

现在我们分析八种排序算法的稳定性。

(请结合前面整理的基本思路来理解整理的稳定性(8种整理的基本思路前面已经提到过了，这里就不重复了)，否则可能会有些模糊)

(1)直接插入排序：一般插入排序从有序序列的最后一个元素开始，如果比它大，就直接插入到它后面；否则，它总是向前比较。如果找到与插入元素相等的，将其插入到相等元素之后。插入排序稳定。

(2)希尔排序：希尔排序是指根据不同的步长对元素进行插入和排序。一次插入排序是稳定的，不会改变相同元素的相对顺序。但是在不同的插入排序过程中，相同的元素可能会在各自的插入排序中移动，稳定性会被破坏，所以Hill Sorting是不稳定的。

(3)简单选择排序：如果当前元素比一个选择中的元素小，并且较小的元素出现在等于当前元素的元素后面，交换后稳定性会被破坏。光线可能有点模糊。我们举个小例子：858410。在第一次扫描中，第一个元素8将与4交换，因此原始序列中两个8的相对序列与原始序列不一致，因此选择排序不稳定。

(4)堆排序：堆排序的过程是从第n/2个及其子节点中选择最大的(大顶堆)或最小的(小顶堆)，这三个元素之间的选择肯定不会破坏稳定性。然而，当为父节点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)合并排序：如果分解后的子列中有一两个元素，则一个元素不交换，两个元素大小相等则不交换。在序列合并的过程中，如果当前两个元素相等，我们将前一个序列中的元素保存在结果序列的前面，所以合并排序是稳定的。

(8)基数排序：先按较低的顺序排序，再进行收集；然后按照高位排序，再进行收集；以此类推，直到最高位。有时候，有些属性有优先顺序。首先，它们按低优先级排序，然后按高优先级排序。最后，高优先级优先，同样的低优先级优先。基数排序是基于分别排序和收集，所以是稳定的。

8类分类、稳定性、时间复杂度和空间复杂度的总结；

以上就是本文的全部内容，希望大家喜欢。