image.png

1.桶排序

• 方法一（不能排序重复的元素，且排序的元素不能为负数）

var arr = [3, 1, 0, 23,, 43, 4]
var bucket = [];
var res = [];
//用for in循环过滤23后面的undefined项
for (var i in arr) {
  bucket[arr[i]] = 1;
}
console.log(bucket);
arr.length = 0;

for (var index in bucket) {
  res.push(index);
}
console.log(res);

• 方法二：（可以有重复的元素，但排序的元素不能为负数）

var marks = [1, 5, 3, 2, 7, 4, 0, 0, , 7, 150, 6, 2, 2, 8, 10, 9];
var arr = []
var newArr = [];

for (i = 0; i < marks.length; i++) {
    if (arr[marks[i]]) {
        arr[marks[i]]++
    } else {
        arr[marks[i]] = 1
    }
}

for (j = 0; j < arr.length; j++) {
    if (!arr[j]) {
        continue
    }
    // 有几个重复的值，就push几次
    for (k = 0; k < arr[j]; k++) {
        newArr.push(j)
    }
}
console.log(newArr)

2.冒泡排序

每轮比对，比对数组剩余需要比对的lenght - 1次

var arr = [5, 3, 5, 2, 8, ,0, 3];
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 temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
    //如果数组中有空值，则把它移到最后
    for(var k = 0; k < arr.length; k++){
        if(arr[k] === undefined){
            arr.splice(k, 1);
            arr.length++;
        }
    }
}
console.log(arr);

3.选择排序

var arr = [5, 2, 7, 1, 4];    
for (var i = 0; i < arr.length - 1; i++) {
        var min = arr[i];
        var minIndex = i;
        for (var k = minIndex + 1; k < arr.length; k++) {
            if (min > arr[k]) {
                min = arr[k];
                minIndex = k;
            }
        }
        //换位
        arr[minIndex] = arr[i];
        arr[i] = min;
    }
console.log(arr);

4.快速排序(一分为二)

var arr = [5, 2, 7, 1, 4];
function quickSort(arr) {
    // 终止条件
    if (arr.length <= 1) {
        return arr;
    }
    // 取中点(可以是任意值)var middleIndex = 0;
    var middleIndex = parseInt(arr.length / 2);
    var middle = arr[middleIndex];
    // 分左右
    var ltArray = [];
    var gtArray = [];
    for (var i = 0; i < arr.length; i++) {
        // 略过中间的分割条件
        if (i === middleIndex) {
            continue;
        }
        if (arr[i] < middle) {
            ltArray.push(arr[i]);
        } else {
            gtArray.push(arr[i]);
        }
    }
    return quickSort(ltArray).concat([middle], quickSort(gtArray));
}
console.log(quickSort(arr));

5.sort排序

用于对数组的元素进行排序。

var arr = [1, 5, 3, 2, 7, 4, 7, 15, 6, 2, 8, 10, 9];
arr.sort();
console.log(arr);   //[1, 10, 15, 2, 2, 3, 4, 5, 6, 7, 7, 8, 9]

// 正序：由小到大
arr.sort(function(a, b) {
    return a - b;
});
console.log(arr);   //[1, 2, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 15]
// 倒序：由大到小
arr.sort(function(a, b) {
    return b - a;
});
console.log(arr);   //[15, 10, 9, 8, 7, 7, 6, 5, 4, 3, 2, 2, 1]

• 重写sort()

var arr = [1, 5, 3, 2, 7, 4, 7, 15, 6, , 2, 8, 10, 9];

function sort1(arr, fn) {
    var s = 0;
    for (var k = 0; k < arr.length; k++) {
        if (arr[k] === undefined) {
            arr.splice(k, 1);
            arr.length++;
            s++;
        }
    }
    var len = arr.length - s;
    while (len > 0) {
        for (var i = 0; i < len; i++) {
            if (fn && fn(arr[i], arr[i + 1]) > 0) {
                var temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            } else {
                var a = Number(String(arr[i])[0]);
                var b = Number(String(arr[i + 1])[0]);
                if (a - b > 0) {
                    var temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
        len--;
    }
}

//从小到大 a - b > 0 - > arr[i] - arr[i + 1] > 0-- > arr[i] > arr[i + 1];
//从大到小 b - a > 0 - > arr[i + 1] - arr[i] > 0-- - > arr[i] < arr[i + 1];
sort1(arr, function(a, b) {
    return a - b;
})
sort1(arr);
console.log(arr);   //[1, 10, 15, 2, 2, 3, 4, 5, 6, 7, 7, 8, 9, empty]
//只能排序，数组项的第一位（个位）

• sort倒序遍历字符

var arr = ["a", "c", "d", "b", "e", "g"];

arr.sort(function(a, b) {
    return b.charCodeAt(0) - a.charCodeAt(0);
})
console.log(arr);   //["g", "e", "d", "c", "b", "a"]

• 用sort将数组随机乱序

var arr = [1, 5, 3, 2, 7, 4, 7, 15, 6, , 2, 8, 10, 9];

arr.sort(function(){
    return Math.random()-0.5;
});
console.log(arr);

• 洗牌算法（Fisher-Yates随机置乱算法 ）

算法步骤为：

1. 建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值；
2. 生成一个从 0 到 n - 1 的随机数 x；
3. 输出 arr 下标为 x 的数值，即为第一个随机数；
4. 将 arr 的尾元素和下标为 x 的元素互换；
5. 同2，生成一个从 0 到 n - 2 的随机数 x；
6. 输出 arr 下标为 x 的数值，为第二个随机数；
7. 将 arr 的倒数第二个元素和下标为 x 的元素互换；

8.                  ……                 
   

9. 如上，直到输出 m 个数为止

各种排序的时间复杂度对比