1.冒泡
var arr = [3, 6, 8, 5, 4, 2, 1, 9, 7, 0];
function m(arr) {
for (var i = 0; i < arr.length - 1; i++) {
for (var j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
2.選擇
function x(arr) {
for (var i = 0; i < arr.length - 1; i++) {
var index = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[index]) {
index = j;
}
var temp = arr[i];
arr[i] = arr[index];
arr[index] = arr[i];
}
}
return arr;
}
3.插入
function c(arr) {
for (var i = 0; i < arr.length; i++) {
var a = arr[i];
for (var j = i - 1; j >= 0 && arr[j] > a; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = a;
}
return arr;
}
4.快速
function k(arr) {
if (arr.length <= 1) { return arr }
var p = Math.floor(arr.length / 2);
var point = arr.splice(p, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < point) {
left.push(arr[i]);
} else {
right.push(arr[i])
}
}
return k(left).concat(point, k(right));
}
5.歸并
function g(arr) {
if (arr.length < 2) { return arr };
var mid = Math.round(arr.length / 2);
var left = arr.slice(0, mid);
var right = arr.slice(mid);
return b(g(left), g(right));
}
function b(left, right) {
var a = [];
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
a.push(left.shift());
} else {
a.push(right.shift());
}
}
while (left.length > 0) {
a.push(left.shift());
}
while (right.length > 0) {
a.push(right.shift());
}
return a;
}
6.希爾排序
function sell(arr) {
for (var gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
var a;
// 數(shù)組遍歷 i從第一個(gè)增量開始 從后面的比前面的
for (var i = gap; i < arr.length; i++) {
// 定義一個(gè)變量儲存當(dāng)前的這個(gè)數(shù)
a = arr[i];
var j = i;
// gap不變 是數(shù)組前半段 a是gap后面的數(shù)
while (j - gap >= 0 && arr[j - gap] > a) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = a;
}
}
return arr;
}
7.堆
var len; // 因?yàn)槁暶鞯亩鄠€(gè)函數(shù)都需要數(shù)據(jù)長度殴瘦，所以把len設(shè)置成為全局變量
function buildMaxHeap(arr) { // 建立大頂堆
len = arr.length;
for (var i = Math.floor(len / 2)-1; i >= 0; i--) {//以他的父節(jié)點(diǎn)來進(jìn)行判斷
//i ==取出來的父節(jié)點(diǎn)
heapify(arr, i);
console.log(i);
}
}
function heapify(arr, i) { // 堆調(diào)整
var left = 2 * i + 1,//左邊子節(jié)點(diǎn)
right = 2 * i + 2,//右邊子節(jié)點(diǎn)
largest = i;//把i當(dāng)成大頂堆中的父節(jié)點(diǎn)
if (left < len && arr[left] > arr[largest]) {//不存在的節(jié)點(diǎn)排除
largest = left;//如果左邊的子節(jié)點(diǎn)大于他的父節(jié)點(diǎn) 將其位置交換
}
if (right < len && arr[right] > arr[largest]) {
largest = right;//如果右邊的子節(jié)點(diǎn)大于他的父節(jié)點(diǎn) 將其位置交換
}
if (largest != i) {//如果largest不等于i抛姑，說明他不大于他兩個(gè)子節(jié)點(diǎn)中得其中一個(gè)
swap(arr, i, largest);//將位置交換
heapify(arr, largest);//重新調(diào)用該方法 已達(dá)到維護(hù)完全二叉樹的性質(zhì)
}
}
//交換位置方法
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);//建立新的大頂堆
//因?yàn)?排序后 最頂部已經(jīng)是最大的數(shù)
//這里需要將第一位和最后一位的位置更換 將最后一位取出來
//這時(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;
}
8.基數(shù)
// 定義數(shù)組氯檐，表示桶
var counter = [];
// maxDigit最大位數(shù) _ _ _
function sort(arr, maxDigit) {
var mod = 10;
var dev = 1;
//放桶里面
for (var i = 0; i < maxDigit; i++) {
// 遍歷數(shù)組抱慌，將所有數(shù)放入對應(yīng)桶中
for (var j = 0; j < arr.length; j++) {
// 得到此數(shù)所在的桶
// 123%10 3/1=3
// 123%100 23/10=2.3
// 123%1000 123/100=1.23
var bucket = parseInt((arr[j] % mod) / dev);
// 當(dāng)此桶為空時(shí)
if (counter[bucket] == null) {
// 聲明此桶為二維數(shù)組
counter[bucket] = [];
}
// 將對應(yīng)的數(shù)放入對應(yīng)桶中
counter[bucket].push(arr[j]);
}
//放數(shù)組 再放上邊
var pos = 0;
// 遍歷桶噪径，將桶中的數(shù)依次放入數(shù)組中
for (var j = 0; j < counter.length; j++) {
var value = null;
// 桶不為空時(shí)
if (counter[j] != null) {
// 數(shù)組不為空柱衔，刪除數(shù)組首位元素
while ((value = counter[j].shift()) != null) {
// 放入新數(shù)組
arr[pos++] = value;
}
}
}
mod *= 10, dev *= 10
}
return arr;
}
9.計(jì)數(shù)排序
function countingSort(arr, maxValue) {
var bucket =new Array(maxValue + 1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
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;
}
