脚本宝典收集整理的这篇文章主要介绍了javascript代码实例教程-javascript数据结构与算法--基本排序算法分析，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。小宝典致力于为广大程序猿（媛）提供高品质的代码服务，请大家多多光顾小站，小宝典在此谢过。 对计算机中存储的数据执行的两种最常见操作是排序和检索，排序和检索算法对于前端开发尤其重要，对此我会对这两种算法做深入的研究，而不会和书上一样只是会贴代码而已，下面我会一步步从自己的理解的思路来一步步学习各个排序的思想。不过这些算法依赖于javascript中的数组来存储数据。最后我会来测试下基本算法(冒泡排序，选择排序，插入排序)的那个效率更高！
下面啊，我们先可以来封装常规数组操作的函数，比如：插入新数据，显示数组数据，还有交换数组元素等操作来调用不同的排序算法。
我们先来封装一个类 CArray，代码如下：
function CArray(numElements) {
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] + " ";
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毫秒
所以这三种基本排序的性能分别为 插入排序 > 选择排序 > 冒泡排序；
基本排序的理解先到此为止；下次我们会来理解下高级排序算法；
觉得可用，就经常来吧！ 脚本宝典 欢迎评论哦！ js脚本，巧夺天工，精雕玉琢。小宝典献丑了！
以上是脚本宝典为你收集整理的javascript代码实例教程-javascript数据结构与算法--基本排序算法分析全部内容，希望文章能够帮你解决javascript代码实例教程-javascript数据结构与算法--基本排序算法分析所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。