对计算机中存储的数据执行的两种最常见操作是排序和检索，排序和检索算法对于前端开发尤其重要，对此我会对这两种算法做深入的研究，而不会和书上一样只是会贴代码而已，下面我会一步步从自己的理解的思路来一步步学习各个排序的思想。不过这些算法依赖于javascript中的数组来存储数据。最后我会来测试下基本算法(冒泡排序，选择排序，插入排序)的那个效率更高！

 

下面啊，我们先可以来封装常规数组操作的函数，比如：插入新数据，显示数组数据，还有交换数组元素等操作来调用不同的排序算法。

 

我们先来封装一个类 CArray，代码如下：

 

 

function CArray(numElements) {

    this.dataStore = [];

    this.pos = 0;

    this.numElements = numElements;

    this.insert = insert;

    this.toString = toString;

    this.clear = clear;

    this.swap = swap;    

    for(var i = 0; i < numElements.length; i++) {

        this.dataStore[i] = numElements[i];

    }            

}

  其中this.dataStore 是一个数组来保存数组中的所有元素，this.pos是一个索引值，默认为0，从第一个开始，this.numElements是保存所有的数组元素，insert方法是向数组中插入一个元素的方法；toString是显示数组中所有元素的方法；clear方法是清除数组中所有的元素，swap方法是交换数组中元素的位置的方法，此方法对排序很有用处，下面我们会用到他们。下面我们来封装下各个方法如下：

 

 

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 restr = "";

    for(var i = 0; i < this.dataStore.length; i++) {

        restr += this.dataStore[i] + " ";

        if(i > 0 && i % 10 == 0) {

            restr+= "\n";

        }

    }

    return restr;

}

function swap(arr,index1,index2) {

    var temp = arr[index1];

    arr[index1] = arr[index2];

    arr[index2] = temp;

}

 

上面方法封装先放在这里，下面我们先来研究下排序算法，稍后会使用到上面的方法。

 

一：冒泡排序：

     冒泡排序在三种基本排序(冒泡排序，选择排序，插入排序)中效率是最慢的一种排序算法；它的实现原理是：数组里面的数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，那么较大的值会浮动到数组的右侧，而较小的值会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时会将他们进行交换。

 

下面我们先来看一下简单的冒泡排序的demo如下：

 

E   A  D B  H

 

经过第一次排序后，这个列表变成：

 

A  E  D  B  H

 

前2个元素进行了交换。接下来再次排序又会变成如下：

 

A   D   E   B   H

 

第二个和第三个元素进行了互换。继续进行排序

 

A   D  B  E  H

 

第三个和第四个元素进行了互换，最后，第二个和第三个元素还会再次互换，得到最终顺序为： A   B  D  E  H

 

下面我们可以来写一个冒泡排序的函数 bubbleSort(),代码如下：

 

 

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);

            }

        }

    }

}

 

下面是所有的JS代码如下

 

 

function CArray(numElements) {

    this.dataStore = [];

    this.pos = 0;

    this.numElements = numElements;

    this.insert = insert;

    this.toString = toString;

    this.clear = clear;

    this.swap = swap;

    this.bubbleSort = bubbleSort;

    for(var i = 0; i < numElements.length; i++) {

        this.dataStore[i] = numElements[i];

    }

            

    }

    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 restr = "";

        for(var i = 0; i < this.dataStore.length; i++) {

            restr += this.dataStore[i] + " ";

            if(i > 0 && i % 10 == 0) {

                restr+= "\n";

            }

        }

        return restr;

    }

    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 = [0,9,1,8,7,6,2,3,5,4];

var myNums = new CArray(numElements);

myNums.bubbleSort();

console.log(myNums.toString());

代码分析如下：

 

假设数组为 [0,9,1,8,7,6,2,3,5,4];

 

1. outer为10的时候

    1. inner为0，值为0，inner+1为1，值为9，不符合，不交换。

    2. inner为1，值为9，inner+1为2 值为1，交换，数组变为[0,1,9,8,7,6,2,3,5,4]

    3. inner为2，值为9，inner+1为3，值为8，交换 数组变为[0,1,8,9,7,6,2,3,5,4]

    4. inner为3，值为9，inner+1 为4，值为7，交换，数组变为[0,1,8,7,9,6,2,3,5,4]

    5, inner为4，值为9，inner+1 为5，值为6，交换，数组变为 [0,1,8,7,6,9,2,3,5,4]

    6. inner为5，值为9，inner+1 为6，值为2，交换，数组变为[0,1,8,7,6,2,9,3,5,4]

    7. inner为6，值为9，inner+1 为7，值为3，交换，数组变为[0,1,8,7,6,2,3,9,5,4]

    8. inner为7，值为9，inner+1 为8，值为5，交换，数组变为[0,1,8,7,6,2,3,5,9,4]

    9. inner为8，值为9，inner+1为9，值为4，交换，数组变为[0,1,8,7,6,2,3,5,4,9]

   10. inner为9，值为9，inner+1 不符合，不交换。

 

2. outer为9的时候

    1. inner为0，值为0，inner+1 不符合，不交换。

    2. inner为1 值为1，inner+1值为8 不符合 不交换。

    3. inner为2 值为8，inner+1值为7，交换，数组变为 [0,1,7,8,6,2,3,5,4,9]

    4. inner为3，值为8，inner+1值为6，交换，数组变为[0,1,7,6,8,2,3,5,4,9]

    5. inner为4 值为8 inner+1值为2 交换 数组变为 [0,1,7,6,2,8,3,5,4,9]

    6. inner为5 值为8，inner+1值为3，交换，数组变为[0,1,7,6,2,3,8,5,4,9]

    7. inner为6 值为8，inner+1值为5，交换 数组变为[0,1,7,6,2,3,5,8,4,9]

    8. inner为7 值为8，inner+1值为4，交换 数组变为[0,1,7,6,2,3,5,4,8,9]

    9. inner为8 值为8，inner+1值为9，不符合 不交换。

 

3. outer为8的时候

   1. inner为0，值为0，inner+1 不符合，不交换。

   2. inner为1 值为1，inner+1值为7 不符合 不交换。

   3. inner为2 值为7，inner+1值为6，交换 数组变为 [0,1,6,7,2,3,5,4,8,9]

   4. inner为3 值为7，inner+1值为2，交换，数组变为[0,1,6,2,7,3,5,4,8,9]

   5. inner为4 值为7，inner+1值为3，交换，数组变为[0,1,6,2,3,7,5,4,8,9]

   6 inner为5 值为7 inner+1值为5，交换，数组变为[0,1,6,2,3,5,7,4,8,9]

   7. inner为6 值为7 inner+1 值为4，交换，数组变为[0,1,6,2,3,5,4,7,8,9]

   8. inner为7 值为7，inner+1值为8，不符合。

 

4. outer为7的时候

   1. inner为0，值为0，inner+1 不符合，不交换。

   2. inner为1 值为1，inner+1值为6 不符合 不交换。

   3. inner为2 值为6，inner+1值为2，交换 数组变为[0,1,2,6,3,5,4,7,8,9]

   4. inner为3 值为6，inner+1值为3，交换，数组变为[0,1,2,3,6,5,4,7,8,9]

   5 inner为4 值为6 inner+1值为5，交换，数组变为[0,1,2,3,5,6,4,7,8,9]

   6 inner为5 值为6 inner+1值为4，交换 数组变为[0,1,2,3,5,4,6,7,8,9]

   7 inner为6 值为6，inner+1 值为7，不符合。

 

5. outer为6的时候

   1. inner为0，值为0，inner+1 不符合，不交换。

   2. inner为1 值为1，inner+1值为2 不符合 不交换。

   3. inner为2 值为2，inner+1值为3 不符合 不交换。

   4. inner为3 值为3，inner+1值为5，不符合 不交换。

   5. inner为4 值为5，inner+1 值为4 交换，数组变为[0,1,2,3,4,5,6,7,8,9]

 

再下面继续循环都不符合条件，所以如上就是最后一步了。这就是冒泡排序。

 

二：选择排序

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

 

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

 

以下是一个对只有五个元素的列表进行选择排序的简单列子，初始列表为：

 

E   A   D   H  B

 

第一次排序会找到最小值，并将它和列表的第一个元素进行互换。

 

A   E   D  H  B

 

接下来查找第一个元素后面的最小值(第一个元素此时已经就位)，并对他们进行互换。

 

A   B  D  H  E

 

D也已经就位，因此下一步会对E和H进行互换，列表已按顺序排好；

 

A   B   D   E  H

 

下面我们就可以来编写选择排序算法的selectionSort()方法了；如下代码：

 

 

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]) {

                swap(this.dataStore,inner,min); 

            }

        }

    }

}

 

下面是所有的JS代码如下：

 

 

function CArray(numElements) {

    this.dataStore = [];

    this.pos = 0;

    this.numElements = numElements;

    this.insert = insert;

    this.toString = toString;

    this.clear = clear;

    this.swap = swap;

    this.selectionSort = selectionSort;    

    for(var i = 0; i < numElements.length; i++) {

        this.dataStore[i] = numElements[i];

    }        

}

        

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 restr = "";

    for(var i = 0; i < this.dataStore.length; i++) {

        restr += this.dataStore[i] + " ";

        if(i > 0 && i % 10 == 0) {

            restr+= "\n";

        }

    }

    return restr;

}

function swap(arr,index1,index2) {

    var temp = arr[index1];

    arr[index1] = arr[index2];

    arr[index2] = temp;

}

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]) {

                swap(this.dataStore,inner,min); 

            }

        }

    }

}

 

// 选择排序测试代码

 

var numElements = [9,0,1,8,7,6,2,3,5,4];

 

var myNums = new CArray(numElements);

 

myNums.selectionSort();

 

console.log("------");

 

console.log(myNums.toString());

 

代码分析如下：

 

假设数组为：[9,0,1,8,7,6,2,3,5,4]

    1. 当min为0的时候，值为9，inner为1，值为0，所以调换位置，数组变为[0,9,1,8,7,6,2,3,5,4]

    2. 当min为0的时候都不符合，所以当min为1的时候，值为9，inner为2，值为1，所以数组变为[0,1,9,8,7,6,2,3,5,4]

    3. 当min为1的时候，值为1，内部循环也不符合，所以现在当min为2的时候，值为9，inner为3的时候，值为8，所以调换位置，数组变为

        [0,1,8,9,7,6,2,3,5,4]

    4. 当min为2的时候，值为8，inner为4的时候，值为7，所以调换位置，数组为[0,1,7,9,8,6,2,3,5,4].

    5. 当min为2的时候，值为7，inner为5的时候，值为6，所以调换位置，数组为[0,1,6,9,8,7,2,3,5,4].

    6. 当min为2的时候，值为6，inner为6的时候，值为2，所以调换位置 数组为[0,1,2,9,8,7,6,3,5,4].

    7. 当min为2的时候，值为2，不符合条件，所以当min为3的时候，值为9，所以inner为4，值为8，所以调换位置，数组变为[0,1,2,8,9,7,6,3,5,4]

    8. 当min为3的时候，值为8，inner为5的时候值为7，所以调换位置，数组变为[0,1,2,7,9,8,6,3,5,4]

    9. 当min为3的时候，值为7，inner为6的时候值为6，所以调换位置 数组变为[0,1,2,6,9,8,7,3,5,4]

   10 当min为3的时候，值为6，inner为7的时候值为3 所以调换位置 数组变为[0,1,2,3,9,8,7,6,5,4]

   11 当min为3的时候 值为3 不符合条件，所以当min为4的时候，值为9，inner为5的时候，值为8，所以调换位置，数组变为

        [0,1,2,3,8,9,7,6,5,4]

   12 当min为4的时候，值为8，inner为6的时候，值为7，所以调换位置，数组变为[0,1,2,3,7,9,8,6,5,4].

   13 当min为4的时候，值为7，inner为7的时候，值为6，所以调换位置，数组变为[0,1,2,3,6,9,8,7,5,4].

   14 当min为4的时候，值为6，inner为8的时候，值为5，所以调换位置，数组变为[0,1,2,3,5,9,8,7,6,4].

   15 当min为4的时候，值为5，inner为9的时候，值为4，所以调换位置，数组变为[0,1,2,3,4,9,8,7,6,5].

   16 当min为5的时候，值为9，inner为6的时候，值为8，所以调换位置，数组变为[0,1,2,3,4,8,9,7,6,5].

   17 当min为5的时候，值为8，inner为7的时候，值为7，所以调换位置，数组变为[0,1,2,3,4,7,9,8,6,5].

   18 当min为5的时候，值为7，inner为8的时候，值为6，所以调换位置，数组变为[0,1,2,3,4,6,9,8,7,5].

   19 当min为5的时候，值为6，inner为9的时候，值为5，所以调换位置，数组变为[0,1,2,3,4,5,9,8,7,6].

   20 当min为6的时候，值为9，inner为7的时候，值为8，所以调换位置，数组变为[0,1,2,3,4,5,8,9,7,6].

   21 当min为6的时候，值为8，inner为8的时候，值为7，所以调换位置，数组变为[0,1,2,3,4,5,7,9,8,6].

   22 当min为6的时候，值为7，inner为9的时候，值为6，所以调换位置，数组变为[0,1,2,3,4,5,6,9,8,7].

   23.当min为7的时候，值为9，inner为8的时候，值为8，所以调换位置，数组变为[0,1,2,3,4,5,6,8,9,7].

   24 当min为7的时候，值为8，inner为9的时候，值为7，所以调换位置，数组变为[0,1,2,3,4,5,6,7,9,8].

  25 当min为8的时候，值为9，inner为9的时候 值为8，所以调换位置，数组最终变为[0,1,2,3,4,,5,6,7,8,9]

 

三：插入排序

原理：插入排序类似于人类按数字或字母顺序对数据进行排序。列如：让班里的每个学生上交一张写有他的名字，学生证号以及个人简介的索引卡片。学生交上来的卡片是没有顺序的，但是我想让这些卡片按字母顺序排好，这样就可以很容易地与班级花名册进行对照了。

 

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

 

插入排序有2个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。

 

插入排序的代码如下：

 

 

// 插入排序

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;

    }

}

 

下面是所有的JS代码如下：

 

 

function CArray(numElements) {

    this.dataStore = [];

    this.pos = 0;

    this.numElements = numElements;

    this.insert = insert;

    this.toString = toString;

    this.clear = clear;

    this.swap = swap;

    this.insertionSort = insertionSort;

    for(var i = 0; i < numElements.length; i++) {

        this.dataStore[i] = numElements[i];

    }        

}

        

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 restr = "";

    for(var i = 0; i < this.dataStore.length; i++) {

        restr += this.dataStore[i] + " ";

        if(i > 0 && i % 10 == 0) {

            restr+= "\n";

        }

    }

    return restr;

}

function swap(arr,index1,index2) {

    var temp = arr[index1];

    arr[index1] = arr[index2];

    arr[index2] = temp;

}

// 插入排序

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;

    }

}

 

// 插入排序的测试代码

 

var numElements = [9,0,1,8,7,6,2,3,5,4];

 

var myNums = new CArray(numElements);

 

myNums.insertionSort();

 

console.log("------");

 

console.log(myNums.toString());

 

代码分析如下： 

 

数组为 [9,0,1,8,7,6,2,3,5,4];

 

1. outer为1的时候

    temp值为0，inner等于1，this.dataStore[inner-1]值为9 >= 0 因此while条件为true，

    this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[1] = 9,inner自减1 inner为0

    因此this.dataStore[0] = 0;因此数组变为[0,9,1,8,7,6,2,3,5,4]

 

2. outer为2的时候

     1. temp = this.dataStore[outer];temp值为1，inner等于2，this.dataStore[inner-1]值为9 >=1 因此while条件为true，

      this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[2] = 9,inner自减1 inner为1

      因此this.dataStore[1] = 1;因此数组变为[0,1,9,8,7,6,2,3,5,4]

 

     2. inner为1，temp值为1，this.dataStore[inner-1]值为0 >= 1 因此while条件为false.不成立

 

3. outer为3的时候

    1. temp = this.dataStore[outer];temp值为8，inner等于3，this.dataStore[inner-1]值为9 >=8 因此while条件为true，

       this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[3] = 9,inner自减1 inner为2

     因此this.dataStore[2] = 8;因此数组变为[0,1,8,9,7,6,2,3,5,4]

   2. inner为2，temp为8，this.dataStore[inner-1]值为1 >= 8 false不成立。同理inner为1的时候 也不成立。

 

4. outer为4的时候

    1. temp = this.dataStore[outer];temp值为7，inner等于4，this.dataStore[inner-1]值为9 >=7 因此while条件为true，

     this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[4] = 9,inner自减1 inner为3

      因此this.dataStore[3] = 7;因此数组变为[0,1,8,7,9,6,2,3,5,4]

 

    2. inner为3的时候，temp为7，this.dataStore[inner-1]值为8 >=7 因此while条件为true，this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[3] = 8,inner自减1 inner为2

因此this.dataStore[2] = 7;因此数组变为[0,1,7,8,9,6,2,3,5,4]

 

    3. inner为2的时候，temp为7，this.dataStore[inner-1]值为1 >=7 while条件为false，不成立，同理inner为1的时候，也为false，也不成立。

 

5. outer为5的时候：

    1. temp = this.dataStore[outer];temp值为6，inner等于5，this.dataStore[inner-1]值为9 >=6 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[5] = 9,inner自减1 inner为4

因此this.dataStore[4] = 6;因此数组变为[0,1,7,8,6,9,2,3,5,4]

 

    2.inner为4的时候，temp为6，this.dataStore[inner-1]值为8 >=6,因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[4] = 8,inner自减1 inner为3

因此this.dataStore[3] = 6;因此数组变为[0,1,7,6,8,9,2,3,5,4]

 

   3.inner为3的时候，temp为6，this.dataStore[inner-1]值为7 >=6,因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[3] = 7,inner自减1 inner为2

因此this.dataStore[2] = 6;因此数组变为[0,1,6,7,8,9,2,3,5,4]

 

   4. inner为2的时候，temp为6，this.dataStore[inner-1]值为1 >=6,条件为false不符合，同理inner=1也不符合。

 

6. outer为6的时候

   1. temp = this.dataStore[outer];temp值为2，inner等于6，this.dataStore[inner-1]值为9 >=2 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[6] = 9,inner自减1 inner为5

因此this.dataStore[5] = 2;因此数组变为[0,1,6,7,8,2,9,3,5,4]

 

   2.inner为5的时候，temp为2，this.dataStore[inner-1]值为8 >=2,因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[5] = 8,inner自减1 inner为4

因此this.dataStore[4] = 2;因此数组变为[0,1,6,7,2,8,9,3,5,4]

 

   3. inner为4的时候，temp为2，this.dataStore[inner-1]值为7 >=2,因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[4] = 7,inner自减1 inner为3

因此this.dataStore[3] = 2;因此数组变为[0,1,6,2,7,8,9,3,5,4]

 

  4. inner为3的时候，temp为2，this.dataStore[inner-1]值为6 >=2,因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[3] = 6,inner自减1 inner为2

因此this.dataStore[2] = 2;因此数组变为[0,1,2,6,7,8,9,3,5,4]

 

  5. inner为2的时候 不符合，同理inner=1的时候也不符合。

 

7. outer为7的时候

   1. temp = this.dataStore[outer];temp值为3，inner等于7，this.dataStore[inner-1]值为9 >=3 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[7] = 9,inner自减1 inner为6

因此this.dataStore[6] = 3;因此数组变为[0,1,2,6,7,8,3,9,5,4]

 

 

   2. temp = this.dataStore[outer];temp值为3，inner等于6，this.dataStore[inner-1]值为8 >=3 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[6] = 8,inner自减1 inner为5

因此this.dataStore[5] = 3;因此数组变为[0,1,2,6,7,3,8,9,5,4]

 

   3. temp = this.dataStore[outer];temp值为3，inner等于5，this.dataStore[inner-1]值为7 >=3 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[5] = 7,inner自减1 inner为4

因此this.dataStore[4] = 3;因此数组变为[0,1,2,6,3,7,8,9,5,4]

 

   4. temp = this.dataStore[outer];temp值为3，inner等于4，this.dataStore[inner-1]值为6 >=3 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[4] = 6,inner自减1 inner为3

因此this.dataStore[3] = 3;因此数组变为[0,1,2,3,6,7,8,9,5,4]

 

   5. 当inner为3的时候 this.dataStore[inner-1]值为2 >=3 条件为false，所以不成立，同理inner==2或者1.

 

8 outer为8的时候

   1. temp = this.dataStore[outer];temp值为5，inner等于8，this.dataStore[inner-1]值为9 >=5 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[8] = 9,inner自减1 inner为7

因此this.dataStore[7] = 5;因此数组变为[0,1,2,3,6,7,8,5,9,4]

 

  2. temp = this.dataStore[outer];temp值为5，inner等于7，this.dataStore[inner-1]值为8 >=5 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[7] = 8,inner自减1 inner为6

因此this.dataStore[6] = 5;因此数组变为[0,1,2,3,6,7,5,8,9,4]

 

   3. temp = this.dataStore[outer];temp值为5，inner等于6，this.dataStore[inner-1]值为7 >=5 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[6] = 7,inner自减1 inner为5

因此this.dataStore[5] = 5;因此数组变为[0,1,2,3,6,5,7,8,9,4]

 

   4. temp = this.dataStore[outer];temp值为5，inner等于5，this.dataStore[inner-1]值为6 >=5 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[5] = 6,inner自减1 inner为4

因此this.dataStore[4] = 5;因此数组变为[0,1,2,3,5,6,7,8,9,4]

 

  5. 当inner为4的时候 this.dataStore[inner-1]值为3 >=5 因此while条件为false，同理inner=3或者2或者1的时候，都不成立。

 

9. outer为9的时候

   1. temp = this.dataStore[outer];temp值为4，inner等于9，this.dataStore[inner-1]值为9 >=4 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[9] = 9,inner自减1 inner为8

因此this.dataStore[8] = 4;因此数组变为[0,1,2,3,5,6,7,8,4,9]

 

  2. temp = this.dataStore[outer];temp值为4，inner等于8，this.dataStore[inner-1]值为8 >=4 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[8] = 8,inner自减1 inner为7

因此this.dataStore[7] = 4;因此数组变为[0,1,2,3,5,6,7,4,8,9]

 

  3. temp = this.dataStore[outer];temp值为4，inner等于7，this.dataStore[inner-1]值为7 >=4 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[7] = 7,inner自减1 inner为6

因此this.dataStore[6] = 4;因此数组变为[0,1,2,3,5,6,4,7,8,9]

 

   4. temp = this.dataStore[outer];temp值为4，inner等于6，this.dataStore[inner-1]值为6 >=4 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[6] = 6,inner自减1 inner为5

因此this.dataStore[5] = 4;因此数组变为[0,1,2,3,5,4,6,7,8,9]

 

  5. temp = this.dataStore[outer];temp值为4，inner等于5，this.dataStore[inner-1]值为5 >=4 因此while条件为true，

this.dataStore[inner] = this.dataStore[inner -1];执行这句代码后，this.dataStore[5] = 5,inner自减1 inner为4

因此this.dataStore[4] = 4;因此数组变为[0,1,2,3,4,5,6,7,8,9]

 

以上所有的步骤都是插入排序的过程；

 

四：基本排序算法的计时比较；

下面是所有的JS代码如下：

 

 

function CArray(numElements) {

    this.dataStore = [];

    this.pos = 0;

    this.numElements = numElements;

    this.insert = insert;

    this.toString = toString;

    this.clear = clear;

    this.setData = setData;

    this.swap = swap;

    this.bubbleSort = bubbleSort;

    this.selectionSort = selectionSort;

    this.insertionSort = insertionSort;

          /**

    // 冒泡排序 选择排序 插入排序

    for(var i = 0; i < numElements.length; i++) {

        this.dataStore[i] = numElements[i];

    }

**/    

// 下面是为了测试性能的for循环

    for(var i = 0; i< numElements; ++i) {

        this.dataStore[i] = i;

    }    

}

function setData() {

    for(var i = 0; i < this.dataStore.length; 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 restr = "";

    for(var i = 0; i < this.dataStore.length; i++) {

        restr += this.dataStore[i] + " ";

        if(i > 0 && i % 10 == 0) {

            restr+= "\n";

        }

    }

    return restr;

}

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);

            }

        }

    }

}

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]) {

                swap(this.dataStore,inner,min); 

            }

        }    

    }

}

// 插入排序

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;

    }

}

 

现在我们来分别对上面三种排序先设置10000个随机元素进行排序后，所花费的多长时间，

 

     1. 冒泡排序测试代码如下：

 

var numElements = 10000;

 

var myNums = new CArray(numElements);

 

myNums.setData();     

 

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

 

myNums.bubbleSort();

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

 

var t1 = stop - start;

 

console.log("对"+numElements+"个元素执行冒泡排序消耗的时间为："+t1+"毫秒");

 

     一直刷新会有不同的时间  在chrome浏览器下大概会在700毫秒左右，我就选择了一次的打印如下：

 

    对10000个元素执行冒泡排序消耗的时间为：709毫秒

 

     2. 对选择排序的测试代码如下：

 

 

 var numElements = 10000;

 

 var myNums = new CArray(numElements);

 

 myNums.setData();

 

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

 

 myNums.selectionSort();

 

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

 

 var t2 = stop2 - start2;

 

 console.log("对"+numElements+"个元素执行选择排序消耗的时间为："+t2+"毫秒");

 

    同理和上面一样操作，最后的时间会在200毫秒左右，我一样选择了一次的打印时间如下：

 

    对10000个元素执行选择排序消耗的时间为：224毫秒

 

    3. 对插入排序的测试代码如下：

 

 

var numElements = 10000;

 

var myNums = new CArray(numElements);

 

myNums.setData();

 

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

 

myNums.insertionSort();

 

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

 

var t3 = stop3 - start3;

 

console.log("对"+numElements+"个元素执行插入排序消耗的时间为："+t3+"毫秒");

 

   打印会在100毫秒左右，如下所示：

 

  对10000个元素执行插入排序消耗的时间为：61毫秒

 

所以这三种基本排序的性能分别为  插入排序  >  选择排序 > 冒泡排序；

 

基本排序的理解先到此为止；下次我们会来理解下高级排序算法；