前言
O(n^2)的排序算法并不是最优的，最优的排序算法是 O(nlogn) 。
O(n^2)的排序算法相对是比较基础的，因为它是最简单的求解思路，在面临一个问题的时候，都会先尝试用最简单的方法去解决它，这个过程能够加深对问题本身的理解，从而提出更加复杂的解法，或者来优化最开始简单的解法。
对于一些问题，如果你没有思路的话，先拿出最简单的解法，虽然这个解法可能在效率上有一些问题，先将你这个解法摆出来，在这个过程中你可能会想到一些优化的地方，同时面试官也会看到你解题的路径，这也是一种非常好的解题思路。
并非是在所有的场合都去使用 O(nlogn)级别的排序算法的。编码简单，易于实现，是一些简单情景的首选，因为O(n^2)级别的排序算法通常编码比较简单，如果你使用的不是高级的程序设计语言，在底层的情况下类似使用汇编语言，只要性能允许，那么O(n^2)级别的排序算法便于实现，那也是首选。
在一些特殊情况下，简单的排序算法也有更优效果。在某些情况下 O(n^2)的排序算法反而比O(nlogn)级别的排序算法更有效。可以通过简单的排序算法的思想衍生出复杂的排序算法，最典型的就是希尔排序，这个排序算法本质上是通过插入排序的思想进行了一次优化衍生而来的。你可能会通过这些简单的排序算法想到一些更好的更优的排序算法。
用简单的排序算法来作为子过程，改进更复杂的排序算法，对于一些简单的排序算法，由于它们本身的性质，所以可能能够成为一个子过程，用于改进更加复杂的排序算法。
还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。源码仓库
不要完美主义。掌握好“度”。
太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。
学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。
选择排序
选择排序是O(n^2)级别的排序算法。
它的思想是两轮循环，分内轮和外轮。外轮每一次都会将数组中最小的元素的索引与当前轮数作为索引这两个索引位置的元素进行交换。内轮是遍历整个数组，将当前数组中最小的元素的索引求出来，用于在内轮循环结束后可以得到这个索引，从而进行数组元素位置的交换。等外轮循环结束后，排序就完成了。
当然你可以在内轮循环中求出数组中最大元素的索引，外轮循环每一轮都会设置默认最小元素的索引，值为外轮循环的轮数，而内轮循环起始索引值为外轮循环的轮数+1。在内轮循环中进行判断，与最小值索引位置的元素进行比较，谁小，那么最小值索引就变成这个元素的索引，直到当前内轮循环结束位置。
因为求出了当前内轮循环中最小值的索引了，然后交换两个索引位置的元素，之后继续开始下一轮比较，周而复始，直到外轮循环结束。
它的原理是 其实就是有两重循环，外轮是用来控制轮数，内轮循环用来遍历数组，内轮循环 不断的求出数组中最小值或最大值的元素索引。等内轮循环结束之后，就让外轮中每一轮索引位置的数组元素，和内轮循环求出来的最大或最小索引的数据元素交换一下位置，不断的让小的元素或者大的元素往前排，这样就达到了排序的效果。
每一次都是在剩下的数组元素中找出剩余的最大元素或最小元素，之前已经交换到最前面的元素就不再参与了，因为每一次都是数组中剩余的元素进行比较。
取其中最大或者最小的值放到前面，内轮循环遍历完了之后，就进行arr[i]和arr[minIndex]交换位置。选择排序的选择二字，就是不断的选择数组元素中最小值或最大值的索引，然后让它们往前排。
代码示例
SortAlgorithms
// 排序算法
class SortAlgorithms {
constructor () {
this.sortTestHeplper = new SortTestHelper();
}
// 选择排序
selectionSort (array) {
const len = array.length;
for (let i = 0; i < len; i ++) {
let minIndex = i;
for (let j = i + 1; j < len; j ++)
if (array[j] < array[minIndex])
minIndex = j;
this.sortTestHeplper.swap(array, i, minIndex);
} // for
}
}随机生成算法测试用例
SortTestHelper
// 排序测试
class SortTestHelper {
constructor () {}
// 生成随机数 前提： 指定范围内生成 有效随机整数 -
generateRandomByBound (min, max) {
// // 获取 1 - 10 之间的 整数
// const randomNumber = Math.floor(Math.random() * 10) + 1;
// // 获取 1 - min 之间的 整数
// const randomNumber2 = Math.floor(Math.random() * min) + 1;
// 获取 min - max 之间的值
// const result = Math.floor(Math.random() * (max + 1 - min)) + min;
return Math.floor(Math.random() * (max + 1 - min)) + min;
}
// 生成随机重复元素数组 前提：指定数组长度范围 并且 指定 数组元素范围
generateRandomArrayByLengthAndReapetArea (length, rangeLeft, rangeRight) {
const data = new Array(length);
for (var i = 0; i < length; i++)
data[i] = this.generateRandomByBound(rangeLeft, rangeRight);
return data;
}
// 生成随机数组 前提：指点数组长度范围
generateRandomArrayByLength (length) {
const data = this.generateRandomArrayByLengthAndReapetArea(length, 0, length);
return data;
}
// 交换两个数组元素的位置 -
swap (array, indexA, indexB) {
const temp = array[indexA];
array[indexA] = array[indexB];
array[indexB] = temp;
}
// 生成近乎有序的数组 前提：指定数组长度范围 并且 指定随机数组元素 交换次数
generateNearlyOrderedArray (length, swapTimes) {
const data = new Array(length);
for (let i = 0; i < length; i++)
data[i] = i;
const random = this.generateRandomByBound;
let indexA = indexB = 0;
for (let i = 0; i < swapTimes; i++) {
indexA = random(0, length - 1);
indexB = random(0, length - 1);
this.swap(data, indexA, indexB);
}
return data;
}
// 判断一个数组是否是有序 是否是升序 从小到大
isSorted (array, isAsc = true) {
if (isAsc) {
// 升序 从小到大
for (var i = 1; i < array.length; i++)
if (array[i - 1] > array[i])
return false;
return true;
} else {
// 倒序 从大到小
for (var i = 1; i < array.length; i++)
if (array[i - 1] < array[i])
return false;
return true;
}
}
// 打印数组中的内容 指定打印的风格
printArray (array, style) {
let info = "";
info += "[ "
for (var i = 0; i < array.length - 1; i++) {
info += array[i];
info += ", ";
}
if (array.length - 1 >= 0)
info += array[array.length - 1];
else
info += "empty.";
info += " ]";
style(info);
}
}
测试算法的性能
写一个非常重要的测试算法性能的函数。测试之后发现十万数据量比一万数据量的性能相差一百倍。选择排序的时间复杂度是O(n^2)级别的，也就是消耗的时间和数组之间是成一个平方关系的。在一张横轴是数据量而纵轴是运行时间的关系图中可以看出，它们之间的关系是一个二次曲线这样的一个关系。
O(n^2)级别的排序算法在某些情况下也是非常有用的。
Main
// main 函数
class Main {
constructor () {
/////////////////////////////////////////////////////////////
// 创建性能测试对象 ///
const performanceTest = new PerformanceTest(); ///
// 创建一个算法对象 ///
const sortAlgorithms = new SortAlgorithms(); ///
// 创建一个排序测试辅助对象 ///
const sortTestHeplper = new SortTestHelper(); ///
// 指定当前this对象 ///
const that = this; ///
//////////////////////////////////////////////////
// 测试选择排序
function selectionSortTest () {
const n = 10;
// 生成一个随机数组
const arr = sortTestHeplper.generateRandomArrayByLengthAndReapetArea(n, 0, 100000);
// 打印排序前的数组
sortTestHeplper.printArray(arr, (info) => {
that.show(info);
console.log(info);
});
// 选择排序
sortAlgorithms.selectionSort(arr);
// 打印排序后的数组
sortTestHeplper.printArray(arr, (info) => {
that.show(info);
console.log(info);
});
}
that.alterLine("Seletion Sort Area");
selectionSortTest();
}
// 将内容显示在页面上
show (content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine (title) {
let line = `--------------------${title}----------------------`
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}SortAlgorithms
// 排序算法
class SortAlgorithms {
constructor () {
this.sortTestHeplper = new SortTestHelper();
}
// 选择排序
selectionSort (array) {
const len = array.length;
for (let i = 0; i < len; i ++) {
let minIndex = i;
for (let j = i + 1; j < len; j ++)
if (array[j] < array[minIndex])
minIndex = j;
this.sortTestHeplper.swap(array, i, minIndex);
} // for
}
}
PerformanceTest
// 性能测试
class PerformanceTest {
constructor () {}
// 对比堆 主要对比 使用heapify 与 不使用heapify时的性能
testHeap (heap, array, isHeapify) {
const startTime = Date.now();
// 是否支持 heapify
if (isHeapify)
heap.heapify(array);
else {
for (const element of array)
heap.add(element);
}
console.log("heap size:" + heap.size() + "\r\n");
document.body.innerHTML += ("heap size:" + heap.size() + "<br /><br />");
// 使用数组取值
let arr = new Array(heap.size());
for (let i = 0; i < arr.length ; i++)
arr[i] = heap.extractMax();
console.log(
"Array size:" + arr.length + "，heap size:" + heap.size() + "\r\n");
document.body.innerHTML += (
"Array size:" + arr.length + "，heap size:" + heap.size() + "<br /><br />");
// 检验一下是否符合要求
for (let i = 1; i < arr.length; i++)
if (arr[i - 1] < arr[i]) throw new Error("error.");
console.log(
"test heap completed." + "\r\n");
document.body.innerHTML += ("test heap completed." + "<br /><br />");
const endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 计算运行的时间，转换为 天-小时-分钟-秒-毫秒
calcTime (result) {
//获取距离的天数
var day = Math.floor(result / (24 * 60 * 60 * 1000));
//获取距离的小时数
var hours = Math.floor(result / ( 60 * 60 * 1000) % 24);
//获取距离的分钟数
var minutes = Math.floor(result / (60 * 1000) % 60);
//获取距离的秒数
var seconds = Math.floor(result / 1000 % 60);
//获取距离的毫秒数
var milliSeconds = Math.floor(result % 1000);
// 计算时间
day = day < 10 ? "0" + day : day;
hours = hours < 10 ? "0" + hours : hours;
minutes = minutes < 10 ? "0" + minutes : minutes;
seconds = seconds < 10 ? "0" + seconds : seconds;
milliSeconds = milliSeconds < 100 ?
(milliSeconds < 10 ? "00" + milliSeconds : "0" + milliSeconds) : milliSeconds;
// 输出耗时字符串
result = day + "天" + hours + "小时" + minutes + "分" +
seconds + "秒" + milliSeconds + "毫秒" +
" <<<<============>>>> 总毫秒数：" + result;
return result;
}
// 自定义对比
testCustomFn (fn) {
let startTime = Date.now();
fn();
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
}SortTestHelper
// 排序测试
class SortTestHelper {
constructor () {}
// 生成随机数 前提： 指定范围内生成 有效随机整数 -
generateRandomByBound (min, max) {
// // 获取 1 - 10 之间的 整数
// const randomNumber = Math.floor(Math.random() * 10) + 1;
// // 获取 1 - min 之间的 整数
// const randomNumber2 = Math.floor(Math.random() * min) + 1;
// 获取 min - max 之间的值
// const result = Math.floor(Math.random() * (max + 1 - min)) + min;
return Math.floor(Math.random() * (max + 1 - min)) + min;
}
// 生成随机重复元素数组 前提：指定数组长度范围 并且 指定 数组元素范围
generateRandomArrayByLengthAndReapetArea (length, rangeLeft, rangeRight) {
const data = new Array(length);
for (var i = 0; i < length; i++)
data[i] = this.generateRandomByBound(rangeLeft, rangeRight);
return data;
}
// 生成随机数组 前提：指点数组长度范围
generateRandomArrayByLength (length) {
const data = this.generateRandomArrayByLengthAndReapetArea(length, 0, length);
return data;
}
// 交换两个数组元素的位置 -
swap (array, indexA, indexB) {
const temp = array[indexA];
array[indexA] = array[indexB];
array[indexB] = temp;
}
// 生成近乎有序的数组 前提：指定数组长度范围 并且 指定随机数组元素 交换次数
generateNearlyOrderedArray (length, swapTimes) {
const data = new Array(length);
for (let i = 0; i < length; i++)
data[i] = i;
const random = this.generateRandomByBound;
let indexA = indexB = 0;
for (let i = 0; i < swapTimes; i++) {
indexA = random(0, length - 1);
indexB = random(0, length - 1);
this.swap(data, indexA, indexB);
}
return data;
}
// 判断一个数组是否是有序 是否是升序 从小到大
isSorted (array, isAsc = true) {
if (isAsc) {
// 升序 从小到大
for (var i = 1; i < array.length; i++)
if (array[i - 1] > array[i])
return false;
return true;
} else {
// 倒序 从大到小
for (var i = 1; i < array.length; i++)
if (array[i - 1] < array[i])
return false;
return true;
}
}
// 打印数组中的内容 指定打印的风格
printArray (array, style) {
let info = "";
info += "[ "
for (var i = 0; i < array.length - 1; i++) {
info += array[i];
info += ", ";
}
if (array.length - 1 >= 0)
info += array[array.length - 1];
else
info += "empty.";
info += " ]";
style(info);
}
}插入排序
插入排序是O(n^2)级别的排序算法，插入排序的思想其实非常简单。
在玩扑克牌的时候，整理牌的思想大体上就是插入排序，就是看后面牌的每一张牌，然后把牌插入到合适的位置，当你对最后一张牌做完这个操作之后，手里的正副扑克牌也就排序完成了。
插入排序和选择排序的区别
这二者最大的区别，插入排序对于内轮循环它是可以提前结束的，只需要满足某种条件就可以做到提前结束。但是选择排序不管数组是什么样子的，为了要保证找到每一轮中的最小的元素，必须从头到尾的将剩下的整个数组重头到尾扫描一遍，根本没有提前终止的机会。
正因为如此，插入排序理论上要比选择排序要快一些，但实际上，插入排序要比选择排序要慢，所以第一版的插入排序还需要进行优化。
代码示例
SortAlgorithms
// 排序算法
class SortAlgorithms {
constructor () {
this.sortTestHeplper = new SortTestHelper();
}
// 插入排序
insertionSort (array) {
const len = array.length;
const swap = this.sortTestHeplper.swap;
for (let i = 1; i < len; i++) {
for (let j = i; j > 0; j--) {
if (array[j] < array[j - 1])
swap(array, j, j - 1);
else
break;
}
}
}
// 插入排序2 优化内循环的判断，直接放入循环条件中
insertionSort2 (array) {
const len = array.length;
const swap = this.sortTestHeplper.swap;
for (let i = 1; i < len; i++)
for (let j = i; j > 0 && array[j] < array[j - 1]; j--)
swap(array, j, j - 1);
}
// 插入排序3 优化 交换两个索引位置的元素这个操作
insertionSort3 (array) {
const len = array.length;
const swap = this.sortTestHeplper.swap;
for (let i = 1; i < len; i++) {
// 存一下当前的值
const current = array[i];
// 在外面声明索引，以便在内轮循环下面进行赋值操作
let j;
for (j = i; j > 0 && array[j - 1] > current ; j--) {
// 只要比current大的元素 都向后移动一位，
// j 索引 会变成 比current大的元素的原索引 (j - 1)
array[j] = array[j - 1];
}
// 插入时 直接覆盖，没有关系，因为原来的元素以后挪到后一位去了。
array[j] = current;
}
}
}
插入排序法的改进
现在实现的插入排序法还需要再进行优化，虽然插入排序法可以进行提前进行终止循环，但是对比结果是选择排序要比插入排序快一些，所以自己实现的插入排序法还有的优化。
之所以插入排序法比选择排序法要慢，这是因为插入排序法在内循环遍历的同时，还不停的再进行交换。而选择排序法，在内循环遍历的同时只是获取最小元素索引，它是在外循环中内循环的后面才进行交换的，所以选择排序才比插入排序快一些，快在交换这里，因为每一次交换都有三次赋值的操作。
插入排序法原理：插入排序法的外轮循环是从前往后的，内轮循环是从当前往前的。最初是只需要判断当前索引位置的元素是否小于前一位索引的元素，如果小的话才需要进行交换，否则就可以直接终止本次内轮循环了。
因为外轮循环是从前往后的，当前前面一位元素如果不大于当前元素，那么当前前面一位元素的再前面一位元素更加不会大于当前元素的，因此，插入排序才有提前终止本轮内轮循环的条件。
插入排序优化原理：如果当前索引位置的元素小于前一位索引的元素，那么就让前一位索引位置的元素往后挪动一位，周而复始，直到挪不动了，本次内循环就结束了。
在外循环中内循环后面就可以把原当前索引位置的元素放到对应的位置中。没有了交换操作还可以提前终止循环，只是增加了挪动一下元素的操作和内轮循环下面的的一次赋值操作，大大提高了性能，现在插入排序法比选择排序法快一倍。
提前终止是插入排序法的一个非常非常重要的性质，它是一旦找到合适的位置就会提前终止，如果这个数组一开始就是接近有序，那么插入排序法可以很快的找到合适的位置然后提前终止循环，那么插入排序法就会非常的快。
插入排序对于有序的速度甚至比O(nlogn)级别的排序算法还要快。这也就是插入排序非常重要的实际意义，因为很多时候处理的真实数据就是近乎有序的。
比如说一套系统的日志，但是有可能在中间产生了一些错误，或者有一些任务时间过长，所以存在几个无序的元素，那么这个时候使用插入排序，性能会更加的好。在最优的情况下，当你排序的内容是一个完全有序的数组的时候，插入排序将会变成一个O(n)级别的算法。
因为内轮循环每一次都是执行一下，每一次都发现当前位置就是合适的位置，直接结束内轮循环了，进行下一次外轮循环，也正是这个元素，插入排序在更加复杂的排序算法中会作为一个子过程来进行优化。
并不是O(n^2)级别的排序算法都是一无是处的，在某一些情况下它们也是非常有效的。
代码示例
SortAlgorithms
// 排序算法
class SortAlgorithms {
constructor () {
this.sortTestHeplper = new SortTestHelper();
}
// 选择排序
selectionSort (array) {
const len = array.length;
const swap = this.sortTestHeplper.swap;
for (let i = 0; i < len; i ++) {
let minIndex = i;
for (let j = i + 1; j < len; j ++)
if (array[j] < array[minIndex])
minIndex = j;
swap(array, i, minIndex);
} // for
}
// 插入排序
insertionSort (array) {
const len = array.length;
const swap = this.sortTestHeplper.swap;
for (let i = 1; i < len; i++) {
for (let j = i; j > 0; j--) {
if (array[j] < array[j - 1])
swap(array, j, j - 1);
else
break;
}
}
}
// 插入排序2 优化内循环的判断，直接放入循环条件中
insertionSort2 (array) {
const len = array.length;
const swap = this.sortTestHeplper.swap;
for (let i = 1; i < len; i++)
for (let j = i; j > 0 && array[j] < array[j - 1]; j--)
swap(array, j, j - 1);
}
// 插入排序3 优化 交换两个索引位置的元素这个操作
insertionSort3 (array) {
const len = array.length;
const swap = this.sortTestHeplper.swap;
for (let i = 1; i < len; i++) {
// 存一下当前的值
const current = array[i];
// 在外面声明索引，以便在内轮循环下面进行赋值操作
let j;
for (j = i; j > 0 && array[j - 1] > current ; j--) {
// 只要比current大的元素 都向后移动一位，
// j 索引 会变成 比current大的元素的原索引 (j - 1)
array[j] = array[j - 1];
}
// 插入时 直接覆盖，没有关系，因为原来的元素以后挪到后一位去了。
array[j] = current;
}
}
// 插入排序3 优化循环操作， 将for循环改成 while循环
insertionSort4 (array) {
const len = array.length;
const swap = this.sortTestHeplper.swap;
for (let i = 1; i < len; i++) {
// 存一下当前的值
const current = array[i];
// 在外面声明索引，以便在内轮循环下面进行赋值操作
let j = i;
while (j > 0 && array[j - 1] > current)
array[j] = array[-- j];// 让前面的元素向后移动一位，j索引会变成原来前面元素的索引
// 插入时 直接覆盖
array[j] = current;
}
}
}Main
// main 函数
class Main {
constructor () {
/////////////////////////////////////////////////////////////
// 创建性能测试对象 ///
const performanceTest = new PerformanceTest(); ///
// 创建一个算法对象 ///
const sortAlgorithms = new SortAlgorithms(); ///
// 创建一个排序测试辅助对象 ///
const sortTestHeplper = new SortTestHelper(); ///
// 指定当前this对象 ///
const that = this; ///
//////////////////////////////////////////////////
{
// 测试选择排序
function selectionSortTest (selectionSortVersion) {
const n = 10;
// 生成一个随机数组
const arr = sortTestHeplper.generateRandomArrayByLengthAndReapetArea(n, 0, 100000);
// 打印排序前的数组
sortTestHeplper.printArray(arr, (info) => {
that.show(info);
console.log(info);
});
// 选择排序
selectionSortVersion(arr);
// 打印排序后的数组
sortTestHeplper.printArray(arr, (info) => {
that.show(info);
console.log(info);
});
}
// that.alterLine("Seletion Sort Area");
// // selectionSortTest((sortAlgorithms.selectionSort).bind(sortAlgorithms));
// selectionSortTest((arr) => sortAlgorithms.selectionSort(arr));
// 测试选择排序
function insertionSortTest (insertionSortVersion) {
const n = 10;
// 生成一个随机数组
const arr = sortTestHeplper.generateRandomArrayByLengthAndReapetArea(n, 0, 100000);
// 打印排序前的数组
sortTestHeplper.printArray(arr, (info) => {
that.show(info);
console.log(info);
});
// 选择排序
insertionSortVersion(arr);
// 打印排序后的数组
sortTestHeplper.printArray(arr, (info) => {
that.show(info);
console.log(info);
});
}
// that.alterLine("Insertion Sort 1 Area");
// insertionSortTest((arr) => sortAlgorithms.insertionSort(arr));
// that.alterLine("Insertion Sort 2 Area");
// insertionSortTest((arr) => sortAlgorithms.insertionSort2(arr));
// that.alterLine("Insertion Sort 3 Area");
// insertionSortTest((arr) => sortAlgorithms.insertionSort3(arr));
// that.alterLine("Insertion Sort 4 Area");
// insertionSortTest((arr) => sortAlgorithms.insertionSort4(arr));
}
// 测试排序算法的性能
function testSortPerformance (sortVersion, array) {
// 性能测试
const info = performanceTest.testSort(array, sortVersion);
// 返回测试信息
return info;
}
const n = 100000;
// 完全随机
const array = sortTestHeplper.generateRandomArrayByLengthAndReapetArea(n, 0, 1000000);
// 近乎有序的数组
const swapTimes = 100;
const nearlyArray = sortTestHeplper.generateNearlyOrderedArray(n, swapTimes);
// 大量重复元素的数组
const repeat = 10;
const repeatArray = sortTestHeplper.generateRandomArrayByLengthAndReapetArea(n, 0, repeat);
// 根据不同类型的数组来测试性能
function testArrayPerformance (arrayVersion) {
that.alterLine("Seletion Sort Area");
const seletionSortInfo = testSortPerformance(sortAlgorithms.selectionSort, arrayVersion);
that.show(seletionSortInfo);
that.log(seletionSortInfo);
that.alterLine("Insertion Sort 1 Area");
const insertionSort1Info = testSortPerformance(sortAlgorithms.insertionSort, arrayVersion);
that.show(insertionSort1Info);
that.log(insertionSort1Info);
that.alterLine("Insertion Sort 2 Area");
const insertionSort2Info = testSortPerformance(sortAlgorithms.insertionSort2, arrayVersion);
that.show(insertionSort2Info);
that.log(insertionSort2Info);
that.alterLine("Insertion Sort 3 Area");
const insertionSort3Info = testSortPerformance(sortAlgorithms.insertionSort3, arrayVersion);
that.show(insertionSort3Info);
that.log(insertionSort3Info);
that.alterLine("Insertion Sort 4 Area");
const insertionSort4Info = testSortPerformance(sortAlgorithms.insertionSort4, arrayVersion);
that.show(insertionSort4Info);
that.log(insertionSort4Info);
}
that.alertLine("All Random Array Area");
/**
--------------------Seletion Sort Area----------------------
00天00小时00分16秒326毫秒 <<<<============>>>> 总毫秒数：16326
--------------------Insertion Sort 1 Area----------------------
00天00小时00分09秒384毫秒 <<<<============>>>> 总毫秒数：9384
--------------------Insertion Sort 2 Area----------------------
00天00小时00分09秒367毫秒 <<<<============>>>> 总毫秒数：9367
--------------------Insertion Sort 3 Area----------------------
00天00小时00分06秒850毫秒 <<<<============>>>> 总毫秒数：6850
--------------------Insertion Sort 4 Area----------------------
00天00小时00分07秒386毫秒 <<<<============>>>> 总毫秒数：7386
**/
testArrayPerformance(array);
that.alertLine("Nearly Ordered Area");
/**
--------------------Seletion Sort Area----------------------
00天00小时00分14秒486毫秒 <<<<============>>>> 总毫秒数：14486
--------------------Insertion Sort 1 Area----------------------
00天00小时00分00秒029毫秒 <<<<============>>>> 总毫秒数：29
--------------------Insertion Sort 2 Area----------------------
00天00小时00分00秒029毫秒 <<<<============>>>> 总毫秒数：29
--------------------Insertion Sort 3 Area----------------------
00天00小时00分00秒024毫秒 <<<<============>>>> 总毫秒数：24
--------------------Insertion Sort 4 Area----------------------
00天00小时00分00秒021毫秒 <<<<============>>>> 总毫秒数：21
**/
testArrayPerformance(nearlyArray);
that.alertLine("Reapet Array Area");
/**
--------------------Seletion Sort Area----------------------
00天00小时00分15秒933毫秒 <<<<============>>>> 总毫秒数：15933
--------------------Insertion Sort 1 Area----------------------
00天00小时00分08秒477毫秒 <<<<============>>>> 总毫秒数：8477
--------------------Insertion Sort 2 Area----------------------
00天00小时00分08秒449毫秒 <<<<============>>>> 总毫秒数：8449
--------------------Insertion Sort 3 Area----------------------
00天00小时00分06秒176毫秒 <<<<============>>>> 总毫秒数：6176
--------------------Insertion Sort 4 Area----------------------
00天00小时00分06秒142毫秒 <<<<============>>>> 总毫秒数：6142
**/
testArrayPerformance(repeatArray);
}
// 将内容显示在页面上
show (content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 将内容显示在控制台上
log (content) {
console.log(content + "\r\n\r\n");
}
// 展示分割线
alterLine (title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br />`;
}
// 重点分割线
alertLine (title) {
let line = `********************${title}**********************`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
PerformanceTest
// 性能测试
class PerformanceTest {
constructor () {
this.sortTestHelper = new SortTestHelper();
this.sortAlgorithms = new SortAlgorithms();
}
// 对比堆 主要对比 使用heapify 与 不使用heapify时的性能
testHeap (heap, array, isHeapify) {
const startTime = Date.now();
// 是否支持 heapify
if (isHeapify)
heap.heapify(array);
else {
for (const element of array)
heap.add(element);
}
console.log("heap size:" + heap.size() + "\r\n");
document.body.innerHTML += ("heap size:" + heap.size() + "<br /><br />");
// 使用数组取值
let arr = new Array(heap.size());
for (let i = 0; i < arr.length ; i++)
arr[i] = heap.extractMax();
console.log(
"Array size:" + arr.length + "，heap size:" + heap.size() + "\r\n");
document.body.innerHTML += (
"Array size:" + arr.length + "，heap size:" + heap.size() + "<br /><br />");
// 检验一下是否符合要求
for (let i = 1; i < arr.length; i++)
if (arr[i - 1] < arr[i]) throw new Error("error.");
console.log(
"test heap completed." + "\r\n");
document.body.innerHTML += ("test heap completed." + "<br /><br />");
const endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 计算运行的时间，转换为 天-小时-分钟-秒-毫秒
calcTime (result) {
//获取距离的天数
var day = Math.floor(result / (24 * 60 * 60 * 1000));
//获取距离的小时数
var hours = Math.floor(result / ( 60 * 60 * 1000) % 24);
//获取距离的分钟数
var minutes = Math.floor(result / (60 * 1000) % 60);
//获取距离的秒数
var seconds = Math.floor(result / 1000 % 60);
//获取距离的毫秒数
var milliSeconds = Math.floor(result % 1000);
// 计算时间
day = day < 10 ? "0" + day : day;
hours = hours < 10 ? "0" + hours : hours;
minutes = minutes < 10 ? "0" + minutes : minutes;
seconds = seconds < 10 ? "0" + seconds : seconds;
milliSeconds = milliSeconds < 100 ?
(milliSeconds < 10 ? "00" + milliSeconds : "0" + milliSeconds) : milliSeconds;
// 输出耗时字符串
result = day + "天" + hours + "小时" + minutes + "分" +
seconds + "秒" + milliSeconds + "毫秒" +
" <<<<============>>>> 总毫秒数：" + result;
return result;
}
// 自定义对比
testCustomFn (fn) {
let startTime = Date.now();
fn();
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 测试排序算法的性能
testSort (array, sortMethod) {
const newArray = this.sortTestHelper.cloneArray(array);
const sort = sortMethod.bind(this.sortAlgorithms);
return this.testCustomFn(() => {
sort(newArray);
if (!this.sortTestHelper.isSorted(newArray))
throw new Error("sort bad.");
});
}
}SortTestHelper
// 排序测试
class SortTestHelper {
constructor () {}
// 生成随机数 前提： 指定范围内生成 有效随机整数 -
generateRandomByBound (min, max) {
// // 获取 1 - 10 之间的 整数
// const randomNumber = Math.floor(Math.random() * 10) + 1;
// // 获取 1 - min 之间的 整数
// const randomNumber2 = Math.floor(Math.random() * min) + 1;
// 获取 min - max 之间的值
// const result = Math.floor(Math.random() * (max + 1 - min)) + min;
return Math.floor(Math.random() * (max + 1 - min)) + min;
}
// 生成随机重复元素数组 前提：指定数组长度范围 并且 指定 数组元素范围
generateRandomArrayByLengthAndReapetArea (length, rangeLeft, rangeRight) {
const data = new Array(length);
for (var i = 0; i < length; i++)
data[i] = this.generateRandomByBound(rangeLeft, rangeRight);
return data;
}
// 生成随机数组 前提：指点数组长度范围
generateRandomArrayByLength (length) {
const data = this.generateRandomArrayByLengthAndReapetArea(length, 0, length);
return data;
}
// 交换两个数组元素的位置 -
swap (array, indexA, indexB) {
const temp = array[indexA];
array[indexA] = array[indexB];
array[indexB] = temp;
}
// 生成近乎有序的数组 前提：指定数组长度范围 并且 指定随机数组元素 交换次数
generateNearlyOrderedArray (length, swapTimes) {
const data = new Array(length);
for (let i = 0; i < length; i++)
data[i] = i;
const random = this.generateRandomByBound;
let indexA, indexB;
for (let i = 0; i < swapTimes; i++) {
indexA = random(0, length - 1);
indexB = random(0, length - 1);
this.swap(data, indexA, indexB);
}
return data;
}
// 判断一个数组是否是有序 是否是升序 从小到大
isSorted (array, isAsc = true) {
if (isAsc) {
// 升序 从小到大
for (var i = 1; i < array.length; i++)
if (array[i - 1] > array[i])
return false;
return true;
} else {
// 倒序 从大到小
for (var i = 1; i < array.length; i++)
if (array[i - 1] < array[i])
return false;
return true;
}
}
// 克隆一份一模一样的数组
cloneArray (array) {
const newArray = new Array(array.length);
for (let i = 0; i < newArray.length; i ++)
newArray[i] = array[i];
return newArray;
}
// 打印数组中的内容 指定打印的风格
printArray (array, style) {
let info = "";
info += "[ "
for (var i = 0; i < array.length - 1; i++) {
info += array[i];
info += ", ";
}
if (array.length - 1 >= 0)
info += array[array.length - 1];
else
info += "empty.";
info += " ]";
style(info);
}
}
总结
Selection Sort 选择排序 和 Insertion Sort 插入排序都是两种O(n^2)级别的排序算法。
选择排序的思想
它的思想非常的简单，它的缺点也非常的明显，对于任何一个数组，选择排序两重循环，每一轮循环都必须完全的执行完成，正是因为如此选择排序的效率在任何情况下都是非常慢的。
它也可以进行优化，可以从两端同时比较，这样效率都会提高一半左右。
插入排序的思想
虽然它最差的时间复杂度也是O(n^2)级别的，但是在数组近乎有序的情况下，它的性能非常的高，甚至会比O(nlogn)级别的算法还要高，这使得插入排序非常重要的实际意义。
扩展
冒泡排序Bubble Sort
在近乎有序的数据中使用冒泡排序，刚开始接触的第一个排序算法就是冒泡排序，冒泡排序的性能整体上没有插入排序好，后面会对它进行实现，测试一下它在无序和有序情况下的性能，然后像对插入排序一样对冒泡排序进行一下优化。
希尔排序Shell Sort
通过插入排序法还可以引申出一个非常重要的排序法，这个排序法就是希尔排序法，希尔排序整体的思路就是插入排序的延申。
在插入排序中每一次都是和之前的一个元素进行比较，而希尔排序是尝试每一次和之前第h个元素进行比较，这样下来就会将h这个很大的值逐渐缩小到1。一步一步的将一个完全无序的数组变成近乎有序的数组，变成有序性更强的数组，到最后，当h等于1的时候，最终变成了一个排好序的数组。
这个过程让整个算法的时间复杂度发生了质变，所以希尔排序的时间复杂度分析相对是比较难的，选择不同的让h逐渐递减的序列它的排序的复杂度也是不同的。
也可以实现它，从而了解希尔排序的排序过程，当你理解了希尔排序的排序过程，你会发现它的思想和插入排序法是一脉相承的，它有一个很常用的让h递减的序列，在这种情况下希尔排序的时间复杂度能达到n的二分之三次方级别，相对而言它比O(n^2)级别的算法改进了非常的多。
希尔排序本身它也是一个非常实用的方法，它的时间复杂度比O(n^2)低但是O(nlogn)高一点，但是它的实现相对比较简单，所以在某些情况下使用希尔排序会是一种首选，但是对于排序来说，它的最优的时间复杂度会是O(nlogn)级别的。
