代碼如下:
//js實(shí)現(xiàn)選擇排序
function selectSort(arr) {
var len = arr.length;
for (var i = 0; i < arr.length - 1; i++) {
var minIndex = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
var temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
console.log(arr)
}
//js實(shí)現(xiàn)插入排序
function insertSort(arr) {
var len = arr.length;
for (var i = 1; i < len; i++) {
var insertValue = arr[i];
var insertIndex = i - 1;
while (insertIndex >= 0 && arr[insertIndex] > insertValue) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
if (insertIndex != i - 1) {
arr[insertIndex + 1] = insertValue;
}
}
}
//js實(shí)現(xiàn)希爾排序(移動(dòng)法)
function shellSort(arr) {
var len = arr.length;
//必須向下取整嫉髓,不然gap是個(gè)小數(shù)观腊,現(xiàn)象古怪
for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (var i = gap; i < len; i++) {
//插入的索引
var index = i - gap;
//插入值
var val = arr[i];
while (index >= 0 && arr[index] > val) {
arr[index + gap] = arr[index];
index -= gap;
}
if (index != i - gap) {
arr[index + gap] = val;
}
}
}
}
//快速排序
function quickSort(arr, left, right) {
//終止遞歸
if (left > right) {
return;
}
var l = left;
var r = right;
var base = arr[left];
var temp = 0;
//完成值交換
while (l != r) {
//從右找比基準(zhǔn)值大的
while (arr[r] >= base && l < r) {
r--;
}
//從左找比基準(zhǔn)小的值
while (arr[l] <= base && l < r) {
l++;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
//講基準(zhǔn)值與終點(diǎn)值交換
arr[left] = arr[l];
arr[l] = base;
//向左遞歸
quickSort(arr, left, l - 1);
//向右遞歸
quickSort(arr, r + 1, right);
}
//隨機(jī)快排,降低最壞時(shí)間復(fù)雜度出現(xiàn)
//1.獲取隨機(jī)索引
//low低位算行,high高位
function getRandomIndex (low, high) {
var randomNum = Math.floor(Math.random()*high);
return randomNum % (high - low + 1);
}
//2.獲取隨機(jī)索引梧油,并交換和第一個(gè)元素的值(在知道第一個(gè)元素比較小的時(shí)候用會(huì)很好)
function randomQuickSort (arr,left,right){
var temp = arr[0];
var index = getRandomIndex(left,right);
arr[0] = arr[index];
arr[index] = temp;
quickSort(arr,left,right);
}
//歸并排序
//1.分
//arr,排序數(shù)組州邢,left左值儡陨,right右值,temp臨時(shí)數(shù)組
function sort (arr,left,right,temp) {
if(left >= right)return;
var mid = left + Math.floor((right - left)/2);
sort(arr,left,mid,temp);
sort(arr,mid+1,right,temp);
merge(arr,left,mid,right,temp);
}
//2.并
function merge (arr,left,mid,rightBound,temp){
var l = left;
var r = mid + 1;
var k = left;
//填充臨時(shí)數(shù)組
while(l <= mid && r <= rightBound){
if(arr[l] <= arr[r]){
temp[k++] = arr[l++];
}else{
temp[k++] = arr[r++];
}
}
//將沒(méi)有比較到的元素填充到臨時(shí)數(shù)組
while(l <= mid){
temp[k++] = arr[l++];
}
while(r <= rightBound){
temp[k++] = arr[r++];
}
//將臨時(shí)數(shù)據(jù)填充到原始數(shù)組里
for(var m = 0; m <= rightBound; m++){
arr[m] = temp[m];
}
}
常用的算法特性:
名稱(chēng) | 平均時(shí)間復(fù)雜度 | 最壞時(shí)間復(fù)雜度 | 最好時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 穩(wěn)定性 |
---|---|---|---|---|---|
選擇 | n^2 | n^2 | n^2 | 1 | 不穩(wěn) |
冒泡 | n^2 | n^2 | n^2 | 1 | 穩(wěn) |
+插入 | n^2 | n^2 | n^2] | 1 | 穩(wěn) |
+堆 | n*(log n) | n*(log n) | n*(log n) | 1 | 不穩(wěn) |
希爾 | n^1.3 | n^2 | n | 1 | 不穩(wěn) |
+歸并 | n*(log n) | n*(log n) | n*(log n) | n | 穩(wěn) |
+快排 | n*(log n) | n^2 | n*(log n) | n*(log n) | 不穩(wěn) |
桶 | n + k | n^2 | n | n + k | 穩(wěn) |
計(jì)數(shù) | n + k | n + k | n + k | n + k | 穩(wěn) |
基數(shù) | n * k | n * k | n * k | n + k | 穩(wěn) |
算法長(zhǎng)時(shí)間不寫(xiě)就容易忘記量淌,建議大家有空多寫(xiě)寫(xiě)骗村,對(duì)于我們解決問(wèn)題思路的養(yǎng)成也很有幫助。