基本排序算法

这里介绍的基本排序算法其核心思想是指对一组数据按照一定的顺序重新排列。重新排列时用到的技术是一组嵌套的 for 循环。其中外循环会遍历数组的每一项，内循环则用于比较元素。

在讲这几个基本排序之前，先初始化一个类，因为下面所有的排序都是基于这个类实现的。

function CArray(numElements) {
    this.dataStore = [];
    this.pos = 0;
    this.numElements = numElements;
    this.insert = insert;
    this.toString = toString;
    this.clear = clear;
    this.setData = setData;
    this.bubbleSort = bubbleSort;
    this.swap = swap;
	for ( var i = 0; i < numElements; ++i ) {
		this.dataStore[i] = i;
	} 
}

function setData() {
    for ( var i = 0; i < this.numElements; ++i ) {
       this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1));
    }
}

function clear() {
	for ( var i = 0; i < this.dataStore.length; ++i ) {
	   this.dataStore[i] = 0;
	}
}


function insert(element) {
    this.dataStore[this.pos++] = element;
}


function toString() {
	var retstr = "";
	for ( var i = 0; i < this.dataStore.length; ++i ) {
	   retstr += this.dataStore[i] + " ";
	   if (i > 0 & i % 10 == 0) {
	      retstr += "\n";
	   }
	}
	return retstr;
}


function swap(arr, index1, index2) {
	var temp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = temp;
}

上面的类包含下面几个功能

插入新数据
显示数组数据
调用不同的排序算法
交换数组元素

冒泡排序

冒泡排序算法，它是最慢的排序算法之一，但也是一种最容易实现的排序算法

之所以叫冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换

如下图演示了如何对一个大的数字数据集合进行冒泡排序的过程

冒泡排序的过程

function bubbleSort() {
        var numElements = this.dataStore.length;
        var temp;
        for ( var outer = numElements; outer >= 2; --outer) {
           for ( var inner = 0; inner <= outer - 1; ++inner ) {
              if (this.dataStore[inner] > this.dataStore[inner + 1]) {
                 swap(this.dataStore, inner, inner + 1);
              }
 	   } 
 	}
}

初始化个例子：

var numElements = 10;
var mynums = new CArray(numElements);
mynums.setData();
document.write(mynums.toString());
mynums.bubbleSort();
document.write('<br />');
document.write(mynums.toString());

排序结果如下：

增加一行代码，就可看到这个数组在排序过程中的当前状态

function bubbleSort() {
    var numElements = this.dataStore.length;
    var temp;
    for (var outer = numElements; outer >= 2; --outer) {
       for (var inner = 0; inner <= outer - 1; ++inner) {

          if (this.dataStore[inner] > this.dataStore[inner + 1]) {
             swap(this.dataStore, inner, inner + 1);
          }
		}
        document.write('<br />');
        document.write(this.toString());
    }
}

排序结果如下：

通过这个输出结果，我们可以更加容易地看出小的值是如何移到数组开头的，大的值又是如何移到数组末尾的。

选择排序

选择排序从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。

选择排序会用到嵌套循环。外循环从数组的第一个元素移动到倒数第二个元素;内循环从第二个数组元素移动到最后一个元素，查找比当前外循环所指向的元素小的元素。每次内循环迭代后，数组中最小的值都会被赋值到合适的位置。

选择排序算法的原理：

function selectionSort() {
    var min, temp;
    for (var outer = 0; outer <= this.dataStore.length-2; ++outer) {
       min = outer;
       for (var inner = outer + 1;
           inner <= this.dataStore.length-1; ++inner) {
          if (this.dataStore[inner] < this.dataStore[min]) {
			  min = inner; 
		  }
          swap(this.dataStore, outer, min);
          document.write('<br />');
          document.write(this.toString());
       }
    } 
}

var numElements = 10;
var mynums = new CArray(numElements);
mynums.setData();
mynums.selectionSort();

排序结果如下：

插入排序

插入排序类似于人类按数字或字母顺序对数据进行排序

举个例子，将卡片带回办公室，清理好书桌，然后拿起第一张卡片。卡片上的姓氏是 Smith。我把它放到桌子的左上角，然后再拿起第二张卡片。这张卡片上的姓氏是 Brown。我把 Smith 移右，把 Brown 放到 Smith 的前面。下一张卡片是 Williams，可以把它放到桌面最右边，而不用移动其他任何卡片。下一张卡片是 Acklin。这张卡片必须放在这些卡片的最前面，因此其他所有卡片必须向右移动一个位置来为 Acklin 这张卡片腾出位置。这就是插入排序的排序原理。

插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置，就像之前介绍的姓氏卡片一样。

function insertionSort() {
        var temp, inner;
        for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
           temp = this.dataStore[outer];
           inner = outer;
           while (inner > 0 && (this.dataStore[inner - 1] >= temp)) {
              this.dataStore[inner] = this.dataStore[inner - 1];
--inner; }
           this.dataStore[inner] = temp;
           document.write('<br />');
       	   document.write(this.toString());
        }
}

var numElements = 10;
var mynums = new CArray(numElements);
mynums.setData();
mynums.insertionSort();

排序结果如下：

这段输出结果清楚地显示了插入排序的运行并非通过数据交换，而是通过将较大的数组元素移动到右侧，为数组左侧的较小元素腾出位置。

基本排序算法的计时比较

这三种排序算法的复杂度非常相似，从理论上来说，它们的执行效率也应该差不多。要确定这三种算法的性能差异，我们可以使用一个非正式的计时系统来比较它们对数据集合进行排序所花费的时间。能够对算法进行计时非常重要，因为，对 100 个或 1000 个元素进行排序时，你看不出这些排序算法的差异。但是如果对上百万个元素进行排序，这些排序算法之间可能存在巨大的不同。

这个函数的运行方式如下所示:

var start = new Date().getTime();

要记录代码执行的时间，首先启动计时器，执行代码，然后在代码执行结束时停止计时器。计时器停止时记录的时间与计时器启动时记录的时间之差就是排序所花费的时间。

有了度量排序算法效率的工具，那我们就来做一些测试，对它们进行比较

为了比较基本排序算法，我们将在数组大小分别为100、1000和10 000时对这三种排序算法计时。我们预期在数据大小为 100 和 1000 的情况下看不出这些算法的差异，但是在数据大小为 10000时可以看到。

测试代码如下：

var numElements = 100;    //测试数据100、1000、10000
var nums = new CArray(numElements);
nums.setData();
var start = new Date().getTime();
nums.bubbleSort();
var stop = new Date().getTime();
var elapsed = stop - start;
document.write("对" + numElements + "个元素执行冒泡排序消耗的时间为:" +
elapsed + "毫秒。<br />");
start = new Date().getTime();
nums.selectionSort();
stop = new Date().getTime();
elapsed = stop - start;
document.write("对" + numElements + "个元素执行选择排序消耗的时间为:" +
elapsed + "毫秒。<br />");
start = new Date().getTime();
nums.insertionSort();
stop = new Date().getTime();
elapsed = stop - start;
document.write("对" + numElements + "个元素执行插入排序消耗的时间为:" +
elapsed + "毫秒。");

测试数据100结果：

测试数据1000结果：

测试数据10000结果：

通过上面的结果，可得出选择排序和插入排序要比冒泡排序快，插入排序是这三种算法中最快的。不过要记住，这些测试必须经过多次的运行，最后得到的结果才可被视为是有效的统计。