注意: デフォルトでは、小さい行から大きい行の順に表示されます。
バブルソート
各ラウンドでは、順番のないセクションから最も大きな数字をそのセクションの最後に配置します。
let bubbleSort = function (array) {
let length = array.length
for (let i = length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
[array[j], array[j + 1]] = [array[j + 1], array[j]] //読めない場合は、ES6 Deconstructing Assignmentsで検索してほしい。
}
}
}
return array
};
時間の複雑さ：O(N2)
空間の複雑さ：O(1)
選択ソート
選択ソートの比較プロセスは、バブルソートと同じです。しかし、探索の過程で探索の現在のラウンドが完了してから、交換を行うまで、最大数とその添え字のうち選択されますので、バブルソートに相対的なソートの選択は、交換操作の利点が低減されます。
let selectSort = function (array) {
let length = array.length
for (let i = length - 1; i > 0; i--) {
let max = array[0]
let index = 0
for (let j = 1; j <= i; j++) {
if (max < array[j]) {
max = array[j]
index = j
}
}
[array[index], array[i]] = [array[i], array[index]]
}
return array
};
時間の複雑さ：O(N2)
空間の複雑さ：O(1)
挿入ソート
ローカル・オーダーの考え方は、添え字0から始まり、正しい位置に配置されるまで、数字の左側の数字にトラバースするたびに比較され、交換され、その後、数字の左側の数字にトラバースするたびに、カードが配置されたときにトランプの通常の習慣と一致しています。
let insertSort = function (array) {
let length = array.length
for (let i = 1; i < length; i++) { //挿入を比較する必要がないので、1から始める。
let current = i
while (current > 0 && array[current] < array[current - 1]) {
[array[current], array[current - 1]] = [array[current - 1], array[current]]
current--
}
}
return array
};
もちろん、挿入の局所的に順序付けられた部分の比較のために、バイナリ検索の使用は、より効率的にする必要があります挿入操作は、一度削除し、一度挿入するスプライスメソッドを使用することができます、あなたはそれを自分で試すことができます。
挿入ソートの最悪のシナリオは、基本的にバブリングソートと同じで、例えば[7,6,5,4,3,2,1]のように各比較が完了する場合です。
時間の複雑さ：最悪O(N2)、不安定
空間の複雑さ：O(1)
ヒルソート
このアイデアは、区間ごとにグループ化し、各グループをソートすることです。区間は、最初に大きくなり、次に小さくなり、区間が1になるまでソートされます。
区間比較プロセスは、例えば、配列のような[2、5、4、3、4、1]を、[4、、2、、6、]を取得するために区間分割のための2に、つまり、グループの通常のフォントの数は、数字のグループの太字斜体、それぞれを比較し、交換し、[2、、4、、6、]を取得するために、つまり、行が終了するたびに、順序の間隔に等しく、行は、間隔がすべての順序を確保するために、順序で1になるまで、間隔が再びソートに削減された後になります。間隔が順序で1である、すべての順序を確認することができます。
ここでは、初期インターバルが配列の長さの半分で、インターバルが毎回半分になる例としてコードを示します：
let shellSort = function (array) {
let length = array.length
let gap = Math.floor(length / 2) //初期間隔
while (gap >= 1) {
for (let i = gap; i < length; i++) {
let current = i
while (current >= gap && array[current] < array[current - gap]) {
[array[current], array[current - gap]] = [array[current - gap], array[current]]
current = current - gap
}
}
gap = Math.floor(gap / 2) //区間削減
}
return array
};
時間の複雑さ：O(N1)からO(N2)の間の間隔を取る方法に関連しています。
空間の複雑さ：O(1)
高速ソート
アイデアは、分割して征服することです、特定の数を選択し、各比較処理で、その左側にこの数より小さいすべての数、その右側にこの数より大きいすべての数、つまり、現在の操作でこの番号が最終的な順序の位置にあるようにすることができますし、左右にそれぞれ再帰的にその操作。
重要なステップは、選択された数字を最終的にソートされた位置に配置する方法です。ステップ全体を完了させるために再帰を必要とする関数を実装することから始めましょう。
まず、真ん中のピボットの取り方を決め、配列の一番左、一番右、真ん中の3つの数字を選び、ソートして入れ替え、真ん中の数字を真ん中のピボットとして、配列の一番右側に配置します。
function pivot(arr, left, mid, right) { if (arr[left] > arr[mid]) { swap(arr, left, mid) } if (arr[left] > arr[right]) { swap(arr, left, right) } if (arr[mid] < arr[right]) { swap(arr, mid, right) }}
その後、ダブルポインタを介して、それぞれ、添え字0と長さ-2から加算と減算を開始するには、左ポインタは、数のピボットよりも見つけるために、右ポインタは、小さな数の数のピボットよりも見つけるために、左ポインタが右ポインタよりも大きくなるまで、2つの交換されます。明らかに、この時点で、左のポインタは、ピボット番号の真ん中よりも最も左と大きいを見つけるために、ピボット、操作を達成するために正しい位置にピボットの交換のためのピボット。
function quickSort(arr) {
quick(arr, 0, arr.length - 1)
return arr
}
function quick(arr, left, right) {
if (left >= right) return
let mid = Math.floor(left + (right - left) / 2)
pivot(arr, left, mid, right)
let i = left
let j = right - 1
while (true) {
while (arr[i] < arr[right]) {
i++
}
while (arr[j] > arr[right]) {
j--
}
if (i < j) {
swap(arr, i, j)
i++
j--
} else {
break
}
}
//間違いがあれば訂正を歓迎する。=right
swap(arr, i, right)
//分割と征服
quick(arr, left, i - 1)
quick(arr, i + 1, right)
}
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
配列[3,2,1,5,7,4,6]を見てみましょう。
3つの数字を選んでください： [, 2, 1, , 7, 4, ]。
ピボットを5に選択し、配列の右端に置きます。
左ポインタ ++, ピボットより大きい数字を探す: 6
右ポインター --, ピボットより小さい数字を求めます: 4
交換： [, 2, 1, 4, 7, , ]。
左ポインタ ++, ピボットより大きい数字を探す: 7
右ポインター --, ピボットより小さい数字を求めます: 4
左ポインタ＞右ポインタ、ピボットと左ポインタの交換： [, 2, 1, 4, , , 7 ]。
これで、ミドルピボットの左側がそれより小さく、右側がそれより大きくなり、ミドルピボットがソート後の位置になるように、ソートのラウンドが完了します。次のステップでは、ミドルピボットの左側と右側について、上記の処理を再帰的に行います。
時間の複雑さ：二分速度での除算、平均O(NlogN)
空間の複雑さ：O(1)
レイジー・ライティングでは、空間の複雑さを犠牲にする必要があります。
let quickSort = function(array) {
if (array.length <= 1) {
return array;
}
let pivotIndex = Math.floor(array.length / 2);
let pivot = array.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let i = 0; i < array.length; i++) {
if (array[i] < pivot) {
left.push(array[i])
} else {
right.push(array[i])
}
}
return [...quickSort(left), pivot, ...quickSort(right)]
}
時間の複雑さ：O(NlogN)
空間の複雑さ：O(N)
サブサンプション・ソート
アイデアは、再帰的にグループ化してからマージすることであり、再帰的な回帰プロセスは、マージするための最初の2つの2つの数字であり、最小単位をマージし、マージするための2つのグループをマージし、合併の最外層が完了するまで、そのように。
let mergeSort = (arr) => { if (arr.length <= 1) {
return arr;
}
let mid = Math.floor(arr.length / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
};
//左右マージ関数
let merge = (left, right) => {
if (left.length === 0) {
return right;
}
if (right.length === 0) {
return left;
}
return left[0] < right[0] ? [left[0]].concat(merge(left.slice(1), right))
: [right[0]].concat(merge(right.slice(1), left));
};
時間の複雑さ：T[n] = 2T[n/2] + O(n)、すなわちO(NlogN)
空間の複雑さ：O(N)
計数ソート
時間のために空間を犠牲に。
トラバーサル処理では、ハッシュテーブルを使用して、出現した数字とその回数を保存し、すべての出現回数の最小数と最大数を記録し、最後に、最小数から最大数まで順番に配列に入れます。
let countSort = (arr) => {
if (arr.length < 2) return arr;
let hashTable = {},
max = arr[0],
min = arr[0],
result = [];
for (let i = 0; i < arr.length; i++) {
if (!(arr[i] in hashTable)) {
hashTable[arr[i]] = 1;
} else {
hashTable[arr[i]] += 1;
}
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
for (let i = min; i <= max; i++) {
if (i in hashTable) {
for (let j = 0; j < hashTable[i]; j++) {
result.push(i);
}
}
}
return result;
};
時間の複雑さ：O(N+k)、kはハッシュテーブルの長さ
空間の複雑さ：O(k)
バケットソート
基本的な考え方：まず配列の最大値と最小値を求め、バケツの数を k とします。最小値と最大値の間を k 個の区間に分割し、それぞれの区間をバケツとします。配列の要素をそれぞれのバケツに割り当てます。各バケット内で通常のソートを行い、最後に結合します。基本ソートも計数ソートもバケットソートと見なせます。
以下は、leetcode 347の最初のK個の高頻度要素の例です。質問の説明は、「整数の空でない配列が与えられたら、上位k個の最も頻度の高い要素を返しなさい。
このアイデアは、ハッシュテーブルを使用して、最初のトラバーサル中に発生した回数と発生回数を記録することです。
そして、配列を作成し、数字の出現頻度を配列の添え字として使用し、対応する配列の添え字に預けるだけです。
var topKFrequent = function(nums, k) {
let map = new Map()
for(let i = 0; i< nums.length; i++){
if(map.has(nums[i])){
map.set(nums[i], map.get(nums[i]) + 1)
}else{
map.set(nums[i], 1)
}
}
//バケットソートは、出現数に従って、対応する添え字にソートする。
let arr = []
for(let [key,value] of map){
if(arr[value]){
arr[value].push(key)
}else{
arr[value] = [key]
}
}
let result = []
let temp = arr.filter(item => item !== undefined)
let current = temp.length - 1
let count = k
while(count > 0){
result.push(...temp[current])
count -= temp[current].length
current--
}
return result
};
ベースソートは非常に古いソートであり、一般的に、それぞれの番号に応じて、それぞれ、最も低い位置から始めて、大きな数字を並べ替えるために使用され、コードを与えることはありません。
ヒープソート
最後に、より難解なヒープソートを紹介します。
ヒープとは、以下の性質を持つ完全な2分木のことです。各ノードは、その左と右の子ノードの値以上の値を持ち、ビッグ・トップ・ヒープと呼ばれます。
時間の複雑さ：平均Ο
注：多数の演算例でテストしていませんので、間違いがあれば訂正を歓迎します。
