快速排序是數(shù)組常用的排序算法，采用分而治之的思想野崇，需要用到遞歸猾普，故需要先了解遞虾啦。
- Array.prototype.sort(callback)接受一個 回調(diào)函數(shù) 比如
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使用的是插入排序和快速排序結(jié)合的排序算法寒匙。數(shù)組長度不超過10時零如，使用插入排序。長度超過10使用快速排序锄弱。在數(shù)組較短時插入排序更有效率考蕾。
自己實現(xiàn)的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>
<!-- 布局容器 -->
<!-- 頭部區(qū)域 -->
<header>
數(shù)據(jù)結(jié)構(gòu)與算法
</header>
<!-- 側(cè)邊欄 -->
<aside>
<h3>*******數(shù)據(jù)結(jié)構(gòu)*******</h3>
<ol id="data_structure">
<li>數(shù)組</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>
請輸入你要排序的數(shù)組,主要需要用英文逗號分隔，中文排序不生效会宪。 例如：3,4,5,10,1,2,3,56,6,7,7
<input type="text" id="array_info">
排序后的結(jié)果
<input type="text" id="result_info">
<input type="button" id="sortButton" value="點擊開始快速排序">
</main>
<script>
// 快速排序的調(diào)用函數(shù)
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是一個策略函數(shù),傳進 數(shù)組和左右指針了辕翰，可以進行劃分排序，返回劃分關(guān)鍵節(jié)點位置狈谊，以便下一次遞歸調(diào)用時候傳參
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>
