Javascript中 Array.sort 原理學習

介紹

sort()是JS中用來排序的一個方法,在我們學習各種經典排序算法的時候, 發現都「白學」了。其實在代碼中一個sort()就可以解決,並且時間複雜度和空間複雜度相對都不會過高。其實sort()不光可以對數組進行排序, 基本數據類型的數組都可以, 並且可以實現對對象數組的排序。

這個sort其實遠比我們想像的更加智能，它會基於要排序的數據量選擇性能更加優秀的排序算法來實現排序。

原理

為什麼sort()都可以排序呢? 而且時間和空間複雜度都還比較優良, 有沒有人想過sort()裡面是怎麼實現的呢?

sort根據數組的長度進行區分的

當你的數組長度是小於一個定值的, 它會直接進行一個插入排序。

當長度大於定值時,有可能會merge排序或者是quick排序, merge和quick會將整個數組進行劃分,進行遞歸,一旦劃分的子數組長度小於定值時, 將不再遞歸劃分,直接進行插入排序。為什麼會這麼排序呢?

原因是,在數據量小的時候，插入排序的常數代價非常低,雖然時間複雜度是O(n平方)，但是常數項比較低，此時, 在數據量比較小的時候,優勢就展現出來了。

這個定值是多少？有些人說是60，但是我覺得值得去研究。

數據量大的時候用merge或quick排序

那麼問題又來而來,當數據量比較大需要進行劃分的時候,什麼時候用merge,什麼時候用quick呢?

這就要取決數組的類型了,當是基本數據類型的時候,會用quick, 當是對象類型的時候會用merge。

因為當是基本數據類型的時候不需要考慮穩定性的因素,但是對象類型就要考慮了, 因為對象不止用來排序的這一個屬性, 可能已經在其他屬性已經排好序了, 在此番排序之後還需要保證數組的穩定性。

排序算法對比圖標

插入排序思路

代碼實現

function swap(arr, i, j){
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function insertSort(arr){
if(!arr || arr.length <=1) {
return;
}
for(let i=1; i< arr.length;i++) {
for(let j=i-1; j >= 0; j--) {
if(arr[j] > arr[j+1]) {
swap(arr, j, j+1);
}
else {
break;
}
}
}
}
// let arr = [2,5,3,1,4];
let arr = [8, 3, 4, 5, 11, 6, 7, 9, 10];
insertSort(arr);
console.log(arr);

快速排序思路

快速排序是對冒泡排序的一種改進，採用遞歸分治的方法進行求解。而快排相比冒泡是一種不穩定排序,時間複雜度最壞是O(n^2),平均時間複雜度為O(nlogn),最好情況的時間複雜度為O(nlogn)。

對於快排來說，「基本思想」是這樣的

代碼實現

function swap(arr, i, j){
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function quickSort(arr, from, to) {
// 遞歸出口
if(from > to) {
return;
}
// 設置基準元素
let flag = arr[from];
// 設置兩個哨兵
let left = from;
let right = to;
while(left < right) {
// 1.必須先移動右側哨兵
while(left < right && arr[right] <= flag){
right--;
}
// 2. 移動左側哨兵
while(left < right && arr[left] >= flag){
left++;
}
if(left < right) {
swap(arr, left, right);
}
}
arr[from] = arr[left];
arr[left] = flag;
// 遞歸
quickSort(arr, from, left-1);
quickSort(arr, left+1, to);
}
let arr = [8, 3, 4, 5, 11, 6, 7, 9, 10];
quickSort(arr, 0, arr.length-1);
console.log(arr);

歸併排序原理

歸併和快排都是「基於分治算法」的，分治算法其實應用挺多的，很多分治會用到遞歸，但事實上「分治和遞歸是兩把事」。分治就是分而治之，可以採用遞歸實現，也可以自己遍歷實現非遞歸方式。而歸併排序就是先將問題分解成代價較小的子問題，子問題再採取代價較小的合併方式完成一個排序。

至於歸併的思想是這樣的：

第一次：整串先進行劃分成一個一個單獨，第一次是將序列中(1 2 3 4 5 6---)兩兩歸併成有序，歸併完(xx xx xx xx----)這樣局部有序的序列。

第二次就是兩兩歸併成若干四個(1 2 3 4 5 6 7 8 ----)「每個小局部是有序的」。

就這樣一直到最後這個串串只剩一個，然而這個耗費的總次數logn。每次操作的時間複雜的又是O(n)。所以總共的時間複雜度為O(nlogn).

代碼實現

private static void mergesort(int[] array, int left, int right) {
int mid=(left+right)/2;
if(left<right)
{
mergesort(array, left, mid);
mergesort(array, mid+1, right);
merge(array, left,mid, right);
}
}
private static void merge(int[] array, int l, int mid, int r) {
int lindex=l;int rindex=mid+1;
int team[]=new int[r-l+1];
int teamindex=0;

while (lindex<=mid&&rindex<=r) {//先左右比較合併
if(array[lindex]<=array[rindex])
{
team[teamindex++]=array[lindex++];
}
else {
team[teamindex++]=array[rindex++];
}
}
while(lindex<=mid)//當一個越界後剩餘按序列添加即可
{
team[teamindex++]=array[lindex++];
}
while(rindex<=r)
{
team[teamindex++]=array[rindex++];
}
for(int i=0;i<teamindex;i++)
{
array[l+i]=team[i];
}
}