JS常见简单算法排序
我们面试中经常会遇到排序算法问题，我整理了冒泡排序、选择排序、插入插排等常见简单排序方法。希望此文想对了解排序的前端同学有所帮助。
封装排序数组
为了简单高效演示算法的实现思路，我先封装一个构造函数。以下排序我们默认都是从小到大排序，因为不论从大到小或者从小到大思路都一样。
function ArrayList() {
// 创建排序数组
this.list = [6, 3, 8, 5, 4, 1, 9, 7];
// 排序结果以 - 分割展示
this.toString = function () {
return this.list.join('-')
}
// 交换数组 m 和 n 的位置
this.swap = function (m, n) {
var temp = this.list[n];
this.list[n] = this.list[m];
this.list[m] = temp;
}
}
冒泡排序
冒泡排序是依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。
ArrayList.prototype.bubblesort = function () {
// 第一个元素和第二个元素互换，大的放在后面, 9放最后面 [6, 3, 8, 5, 4, 1, 9, 7] => [3, 6, 5, 4, 1, 8, 7, 9]
// 除了最后一个元素9，接着比较大小互换位置 [3, 6, 5, 4, 1, 8, 7, 9] => [3, 5, 4, 1, 6, 7, 8, 9]
// 除了最后一个元素9和倒二个元素8，接着比较大小互换位置 [3, 5, 4, 1, 6, 7, 8, 9] => [3, 4, 1, 5, 6, 7, 8, 9]
// 以此类推... [3, 4, 1, 5, 6, 7, 8, 9] => [3, 1, 4, 5, 6, 7, 8, 9]
var len = this.list.length;
for (var j = len - 1; j >= 0; j--) {
for (var i = 0; i < j; i++) {
if (this.list[i] > this.list[i + 1]) {
this.swap(i, i + 1);
}
}
}
return this.toString(); // 1-3-4-5-6-7-8-9
}
冒泡排序的比较次数是 1 + 2 +3 + ... + N - 1 = N(N - 1)/2，大O表示法为O(N^2)。如果每两次比较交换一次那么冒泡排序的交换次数为 N(N - 1)/4。
选择排序
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
ArrayList.prototype.selectsort = function () {
// 遍历一轮找到最小元素1，他的下标为5，下标0和下标5对换位置 [6, 3, 8, 5, 4, 1, 9, 7] => [1, 3, 8, 5, 4, 6, 9, 7]
// 再从第二个元素开始遍历，找到最小值，互换位置 [1, 3, 8, 5, 4, 6, 9, 7] => [1, 3, 8, 5, 4, 6, 9, 7]
// 以此类推... [1, 3, 8, 5, 4, 6, 9, 7] => [1, 3, 4, 5, 8, 6, 9, 7]
var len = this.list.length;
for (var j = 0; j < len - 1; j++) {
var min = j;
for (var i = j; i < len - 1; i++) {
if (this.list[min] > this.list[i + 1]) {
min = i + 1;
}
}
this.swap(min, j);
}
return this.toString(); // 1-3-4-5-6-7-8-9
}
选择排序的比较次数是 N - 1 + N - 2 + N - 3 + ... + 1 = N*(N - 1)/2, 大O表示法为O(N^2)。 但是交换次数为 N - 1，比冒泡排序少很多。
插入排序
插入排序将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
ArrayList.prototype.insertsort = function () {
// 获取第二个元素3，和第一个元素6对比，3比6小，交换位置 [6, 3, 8, 5, 4, 1, 9, 7] => [3, 6, 8, 5, 4, 1, 9, 7]
// 获取第三个元素8，8 比前面两个元素 6 和 3 都大 所有位置不变 [3, 6, 8, 5, 4, 1, 9, 7] => [3, 6, 8, 5, 4, 1, 9, 7]
// 以此类推... [3, 6, 8, 5, 4, 1, 9, 7] => [3, 5, 6, 8, 4, 1, 9, 7]
var len = this.list.length;
for (var i = 1; i < len; ++i) {
var j = i, temp = this.list[j];
while (this.list[j - 1] > temp && j > 0) {
this.list[j] = this.list[j - 1];
j--;
}
this.list[j] = temp;
}
return this.toString();
}
var list = new ArrayList(); // 1-3-4-5-6-7-8-9插入排序的比较次数是 (1 + 2 +3 + ...+ N - 1)/2 = N*(N - 1)/4。它的比较次数和冒泡排序和选择排序相比是最少的。不过用大O表示法也为O(N^2)。
以上三种只是简单排序，而插入排序思想是高级排序实现的基础，后期更新介绍希尔排序和快速排序等高级排序内容。
本文内容仅供个人学习、研究或参考使用，不构成任何形式的决策建议、专业指导或法律依据。未经授权，禁止任何单位或个人以商业售卖、虚假宣传、侵权传播等非学习研究目的使用本文内容。如需分享或转载，请保留原文来源信息，不得篡改、删减内容或侵犯相关权益。感谢您的理解与支持！
