1.冒泡排序
for (var i = 0; i < arr.length - 1; i++) {
for (var j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
var max = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = max;
}
}
}
console.log(arr);
2.選擇排序
for (var i = 0; i < arr.length - 1; i++) {
var min_index = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
var min = arr[i];
arr[i] = arr[min_index];
arr[min_index] = min;
}
console.log(arr);
3.快速排序
var quickly = function (arr) {
if (arr.length <= 1) {
return arr;
}
// 取基準(zhǔn)值
var cen = Math.floor(arr.length / 2);
// 取下標(biāo)
var cen1 = arr.splice(arr, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < cen) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickly.left.concat([cen1], quickly.right);
}
console.log(arr);
4.插入排序
var sort = function (a) {
for (var i = 1; i < arr.length; i++) {
var w = arr[i];
for (var j = i - 1; j >= 0 && arr[j] > w; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = w;
}
return a;
}
console.log(sort(arr));
5.歸并排序
var sort = function (arr) {
if (arr.length < 2) {
return arr;
}
var cen = Math.floor(arr.length / 2);
var left = arr.slice(0, cen);
var right = arr.slice(cen);
console.log(left, right);
return sort1(sort(left), sort(right));
}
var sort1 = function (left, right) {
var c = [];
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
c.push(left.shift());
} else {
c.push(right.shift());
}
}
while (left.length > 0) {
c.push(left.shift());
}
while (right.length > 0) {
c.push(right.shift());
}
return c;
}
console.log(sort(arr));
6.堆排序
// 建立大頂堆
function buildMaxHeap(arr) {
len = arr.length;
for (var i = Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i);
}
}
// 堆調(diào)整
var len; // 因為聲明的多個函數(shù)都需要數(shù)據(jù)長度戴尸，所以把len設(shè)置成為全局變量
function buildMaxHeap(arr) { // 建立大頂堆
len = arr.length;
for (var i = Math.floor(len / 2) - 1; i >= 0; i--) { //以他的父節(jié)點來進行判斷
//i ==取出來的父節(jié)點
heapify(arr, i);
console.log(i);
}
}
function heapify(arr, i) { // 堆調(diào)整
var left = 2 * i + 1, //左邊子節(jié)點
right = 2 * i + 2, //右邊子節(jié)點
largest = i; //把i當(dāng)成大頂堆中的父節(jié)點
if (left < len && arr[left] > arr[largest]) { //不存在的節(jié)點排除
largest = left; //如果左邊的子節(jié)點大于他的父節(jié)點 將其位置交換
}
if (right < len && arr[right] > arr[largest]) {
largest = right; //如果右邊的子節(jié)點大于他的父節(jié)點 將其位置交換
}
if (largest != i) { //如果largest不等于i，說明他不大于他兩個子節(jié)點中得其中一個
swap(arr, i, largest); //將位置交換
heapify(arr, largest); //重新調(diào)用該方法 已達到維護完全二叉樹的性質(zhì)
}
}
//交換位置方法
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr); //建立新的大頂堆
//因為 排序后 最頂部已經(jīng)是最大的數(shù)
//這里需要將第一位和最后一位的位置更換 將最后一位取出來
//這時候 就需要保證大頂堆的成立 則需要調(diào)用 堆調(diào)整的方法
// arr.length - 1 最后一位 0 為第一位(即最大值或者最小值)
for (var i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--; //每一次父級-1
heapify(arr, 0); //保證大頂堆的成立
}
return arr;
}
console.log(heapSort(arr));
7.計數(shù)排序
var arr = [45, 56, 23, 54, 12, 5, 71, 25, 3];
function countingSort(arr, maxValue) {
// 根據(jù)數(shù)列的最大值確定統(tǒng)計數(shù)組長度
var bucket = new Array(maxValue + 1),
// 創(chuàng)建結(jié)果數(shù)組的起始索引
sortedIndex = 0,
arrLen = arr.length,
// 最大值加1
bucketLen = maxValue + 1;
console.log(bucketLen);
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
console.log(countingSort(arr, 71));
8.桶排序
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
// 輸入數(shù)據(jù)的最小值
minValue = arr[i];
} else if (arr[i] > maxValue) {
// 輸入數(shù)據(jù)的最大值
maxValue = arr[i];
}
}
// 桶的初始化
// 設(shè)置桶的默認數(shù)量為5
var DEFAULT_BUCKET_SIZE = 5;
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var bucket = new Array(bucketCount);
for (i = 0; i < bucket.length; i++) {
bucket[i] = [];
}
// 利用映射函數(shù)將數(shù)據(jù)分配到各個桶中
for (i = 0; i < arr.length; i++) {
bucket[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < bucket.length; i++) {
sort(bucket[i]);
// 對每個桶進行排序箩朴，這里使用了插入排序
for (var j = 0; j < bucket[i].length; j++) {
arr.push(bucket[i][j]);
}
}
return arr;
}
console.log(bucketSort(arr, 5));
9.基數(shù)排序
var counter = [];
// maxDigit最大位數(shù)
function sort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, mod *= 10, dev *= 10) {
// 遍歷數(shù)組彪见，將所有數(shù)放入對應(yīng)桶中
for (var j = 0; j < arr.length; j++) {
// 得到此數(shù)所在的桶
var bucket = parseInt((arr[j] % mod) / dev);
// 當(dāng)此桶為空時
if (counter[bucket] == null) {
// 聲明此桶為二維數(shù)組
counter[bucket] = [];
}
// 將對應(yīng)的數(shù)放入對應(yīng)桶中
counter[bucket].push(arr[j]);
}
var pos = 0;
// 遍歷桶泰鸡，將桶中的數(shù)依次放入數(shù)組中
for (var j = 0; j < counter.length; j++) {
var value = null;
// 桶不為空時
if (counter[j] != null) {
// 數(shù)組不為空，刪除數(shù)組首位元素
while ((value = counter[j].shift()) != null) {
// 放入新數(shù)組
arr[pos++] = value;
}
}
}
}
return arr;
}
console.log(sort(arr));
10.希爾排序
function shellSort(arr) {
var len = arr.length;
for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (var i = gap; i < len; i++) {
var j = 1;
var current = arr[i];
while (j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
}
}
return arr;
}
console.log(shellSort(arr));
