经典排序算法——冒泡
2018-06-14 本文已影响6人
DHFE
参考书籍：《学习JavaScript数据结构与算法》
引言
假设我们有一个没有任何排列顺序的电话号码表（或号码簿）。当需要添加联络人和电话时，你只能将其写在下一个空位上，假定你的联系人列表上有很多人，某天，你要找某个联系人及其电话号码。但是由于联系人没有按照任何顺序来组织，你只能逐个检查，直到找到那个你想要的联系人为止。这个方法太吓人了。
因此，我们需要组织信息集，比如那些存储在数据结构里的信息。排序和搜索算法广泛的运用在待解决的日常问题中。
冒泡排序
在开始排序算法前，我们先创建一个数组（列表）来表示待排序和搜索的数据结构。
function ArrayList() {
var array = []; // {1}
this.insert = function(item) { // {2}
array.push(item);
};
this.toString = function() { // {3}
return array.join();
};
}
ArrayList是一个简单的数据结构，它将项存储在数组中（行{1}）。我们只需要一个插入方法来向数据结构中添加元素（行{2}），最后，为了帮助我们验证结果，toString方法使用JavaScript原生Array类的join()方法，来拼接数组中所有元素至一个单一的字符串，这样我们就可以轻松的在浏览器的控制台输出结果了。
注意ArrayList类并没有任何方法来移除数据或插入数据到特定位置，保持简单为了专注于排序和搜索算法。
学习排序算法时，通常都先学冒泡算法，因为它在所有排序算法中最简单。然而，从运行时间的角度看，冒泡排序是最差的一个。
this.bubbleSort = function () {
var length = array.length; // {1}
for (var i = 0; i < length; i++) { // {2}
for (var j = 0; j < length - 1; j++) { // {3}
if (array[j] > array[j + 1]) { // {4}
swap(array, j, j + 1); // {5}
}
}
}
}
首先，声明一个名为length的变量，用来存储数组的长度（行{1}）。这一步可选，它能帮助我们在行{2}和行{3}时直接使用数组的长度（不用重复的读array.length）。
- 外循环（{2}）会从数组的第一位迭代至最后一位，它控制了在数组中经过多少轮排序（应该是数组中每一项都经过一轮，轮数和数组长度一致）。
- 然后内循环将从第一位迭代至倒数第二位，内循环实际上进行当前项和下一项的比较（{4}）。如果当前项大于下一项，交换（函数
swap()），意思是位置为j+1的值将会被置换到位置j处，反之亦然。
然后声明swap()函数（一个私有函数，只能用在ArrayList类的内部代码中）。
var swap = function(array,index1,index2) {
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
冒泡排序工作流程
该示意图中每一小段表示外循环的一轮，而相邻两项的比较则是在内循环中进行的。
创建一个函数来自动的创建一个未排序的数组。
function createNonSortedArray(size) {
var array = new ArrayList();
for (var i = size; i > 0; i--) {
array.insert(i);
}
return array;
完整：
function ArrayList() {
var array = [];
this.insert = function (item) {
array.push(item);
};
this.toString = function () {
return array.join();
};
this.bubbleSort = function () {
var length = array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
var swap = function (array, index1, index2) {
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
}
function createNonSortedArray(size) {
var array = new ArrayList();
for (var i = size; i > 0; i--) {
array.insert(i);
}
return array;
}
var arr = createNonSortedArray(5);
console.log(arr.toString()); // 5,4,3,2,1
arr.bubbleSort();
console.log(arr.toString()); // 1,2,3,4,5
我们在回到那张示意图看一看，可以继续对算法进行改进。
改进版：
function ArrayList() {
var array = [];
this.insert = function (item) {
array.push(item);
};
this.toString = function () {
return array.join();
};
this.bubbleSort = function () {
var length = array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
var swap = function (array, index1, index2) {
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
}
function createNonSortedArray(size) {
var array = new ArrayList();
for (var i = size; i > 0; i--) {
array.insert(i);
}
return array;
}
var arr = createNonSortedArray(20);
console.log(arr.toString()); // 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1
arr.bubbleSort();
console.log(arr.toString()); // 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
并且我又发现了一个小改进。
最终版：
this.bubbleSort = function () {
var length = array.length;
for (var i = 0; i < length; i++) {
count++;
for (var j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
测试一下：
function ArrayList() {
var array = [];
this.insert = function (item) {
array.push(item);
};
this.toString = function () {
return array.join();
};
this.bubbleSort = function () {
var length = array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
var swap = function (array, index1, index2) {
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
}
function createNonSortedArray(size) {
var array = new ArrayList();
for (var i = size; i > 0; i--) {
array.insert(i);
}
return array;
}
var arr = createNonSortedArray(50);
console.log(arr.toString());
// 50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1
arr.bubbleSort();
console.log(arr.toString());
// 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50
over。
