快速排序是数组常用的排序算法，采用分而治之的思想，需要用到递归，故需要先了解递。
- Array.prototype.sort(callback)接受一个 回调函数 比如
testArr.sort((a,b) => a-b) 正在研究中
那sort用的是什么排序算法呢？那就要看Chrome V8引擎的源码了。
sort方法源码
DEFINE_METHOD(
GlobalArray.prototype,
sort(comparefn) {
CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
if (!IS_UNDEFINED(comparefn) && !IS_CALLABLE(comparefn)) {
throw %make_type_error(kBadSortComparisonFunction, comparefn);
}
var array = TO_OBJECT(this);
var length = TO_LENGTH(array.length);
return InnerArraySort(array, length, comparefn);
}
);
InnerArraySort方法源码
function InnerArraySort(array, length, comparefn) {
// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.
if (!IS_CALLABLE(comparefn)) {
comparefn = function (x, y) {
if (x === y) return 0;
if (%_IsSmi(x) && %_IsSmi(y)) {
return %SmiLexicographicCompare(x, y);
}
x = TO_STRING(x);
y = TO_STRING(y);
if (x == y) return 0;
else return x < y ? -1 : 1;
};
}
function InsertionSort(a, from, to) {
...
};
...
function QuickSort(a, from, to) {
var third_index = 0;
while (true) {
// Insertion sort is faster for short arrays.
if (to - from <= 10) {
InsertionSort(a, from, to);
return;
}
if (to - from > 1000) {
third_index = GetThirdIndex(a, from, to);
} else {
third_index = from + ((to - from) >> 1);
}
// Find a pivot as the median of first, last and middle element.
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];
var c01 = comparefn(v0, v1);
if (c01 > 0) {
// v1 < v0, so swap them.
var tmp = v0;
v0 = v1;
v1 = tmp;
} // v0 <= v1.
var c02 = comparefn(v0, v2);
if (c02 >= 0) {
// v2 <= v0 <= v1.
var tmp = v0;
v0 = v2;
v2 = v1;
v1 = tmp;
} else {
// v0 <= v1 && v0 < v2
var c12 = comparefn(v1, v2);
if (c12 > 0) {
// v0 <= v2 < v1
var tmp = v1;
v1 = v2;
v2 = tmp;
}
}
// v0 <= v1 <= v2
a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1; // Upper bound of elements lower than pivot.
var high_start = to - 1; // Lower bound of elements greater than pivot.
a[third_index] = a[low_end];
a[low_end] = pivot;
// From low_end to i are elements equal to pivot.
// From i to high_start are elements that haven't been compared yet.
partition: for (var i = low_end + 1; i < high_start; i++) {
var element = a[i];
var order = comparefn(element, pivot);
if (order < 0) {
a[i] = a[low_end];
a[low_end] = element;
low_end++;
} else if (order > 0) {
do {
high_start--;
if (high_start == i) break partition;
var top_elem = a[high_start];
order = comparefn(top_elem, pivot);
} while (order > 0);
a[i] = a[high_start];
a[high_start] = element;
if (order < 0) {
element = a[i];
a[i] = a[low_end];
a[low_end] = element;
low_end++;
}
}
}
if (to - high_start < low_end - from) {
QuickSort(a, high_start, to);
to = low_end;
} else {
QuickSort(a, from, low_end);
from = high_start;
}
}
};
...
QuickSort(array, 0, num_non_undefined);
...
return array;
}
- 这一步最重要的是QuickSort，从代码和注释中可以看出sort使用的是插入排序和快速排序结合的排序算法。数组长度不超过10时，使用插入排序。长度超过10使用快速排序。在数组较短时插入排序更有效率。
自己实现的mysort（） 方法
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>冒泡排序</title>
<style>
* {
margin: 0;
padding: 0;
}
header {
text-align: center;
font-size: 30px;
font-weight: 900;
line-height: 100px;
width: 100%;
height: 100px;
background-color: #888;
border-bottom: 1px solid #000;
color: #fff;
box-sizing: border-box;
}
aside {
position: absolute;
padding-left: 10px;
top: 100px;
left: 0;
bottom: 0;
width: 250px;
background-color: #ddd;
box-sizing: border-box;
border: 1px solid #000;
border-top: 0;
}
main {
position: absolute;
top: 100px;
right: 0;
left: 250px;
bottom: 0;
background-color: #fff;
}
#algorithm,
#data_structure {
margin-left: 60px;
}
form {
width: 95%;
height: 300px;
margin: 20px auto;
border: 1px solid #000;
}
#array_info {
display: block;
}
input {
width: 99%;
height: 30px;
border: 1px solid #000;
margin: 5px auto;
font-size: 20px;
}
#result_info {
display: block;
}
#sortButton {
background-color: royalblue;
width: 200px;
height: 40px;
border-radius: 5px;
}
h3 {
margin-bottom: 10px;
}
</style>
</head>
<body>
<!-- 布局容器 -->
<!-- 头部区域 -->
<header>
数据结构与算法
</header>
<!-- 侧边栏 -->
<aside>
<h3>*******数据结构*******</h3>
<ol id="data_structure">
<li>数组</li>
<li>栈</li>
<li>队列和双端队列</li>
<li>链表</li>
<li>集合</li>
<li>字典和散列表</li>
<li>树</li>
<li>二叉堆</li>
<li>图</li>
</ol>
<h3>*******算法*******</h3>
<ol id="algorithm">
<li>排序</li>
<li>递归</li>
<li>搜索</li>
</ol>
</aside>
<!-- 主体 -->
<main>
<h3>这是前段程序员必须掌握的排序算法</h3>
请输入你要排序的数组,主要需要用英文逗号分隔，中文排序不生效。 例如：3,4,5,10,1,2,3,56,6,7,7
<input type="text" id="array_info">
排序后的结果
<input type="text" id="result_info">
<input type="button" id="sortButton" value="点击开始快速排序">
</main>
<script>
// 快速排序的调用函数
Array.prototype.mysort = function ( left = 0, right = this.length -1) {
if (this.length === 0) return this
let index = partition(this, left, right)
if (left < index - 1) this.mysort( left, index - 1)
if (index < right) this.mysort(index, right)
return this
// partition是一个策略函数,传进 数组和左右指针了，可以进行划分排序，返回划分关键节点位置，以便下一次递归调用时候传参
function partition(arr, left, right) {
const pivot = arr[Math.floor((left + right) / 2)]
while (left <= right) {
while (arr[left] < pivot) {
left++
}
while (arr[right] > pivot) {
right--
}
if (left <= right) {
;[arr[left], arr[right]] = [arr[right], arr[left]]
left++;
right--;
}
}
return left
}
}
const btn = document.querySelector('#sortButton')
btn.addEventListener('click', function () {
const array_info = document.querySelector('#array_info').value
const testArr = array_info.split(',')
document.querySelector('#result_info').value = testArr.mysort()
})
</script>
</body>
</html>
