[数据结构与算法]数组排序的几种方法

1.冒泡排序

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 ?
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 ?
• 针对所有的元素重复以上的步骤，除了最后一个。 ?
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

let arr = [5, 2, 3, 4, 1];
let bubbleSort = (arr) => {
    // 控制比较轮数
    for (i = 0; i < arr.length - 1; i++) {
        // 控制每轮比较
        for (j = 0; j < arr.length - i - 1; j++) {
            // 前面的数大于后面的数交换位置
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp
            }
        }
    }
    return arr
}
console.log(bubbleSort(arr));

2.选择排序

• 第一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法
• 选择排序算法思想：在冒泡排序上做了优化，减少了交换次数，在首轮选择最小的数放在第一项，一轮之后第一项是有序的了，第二轮从第二项开始选择小的数放在第二项，以此类推，直到整个数组完全有序。

let arr = [15, 8787, 562, 8, 2222, 466, 481, 112, 4545];
let selectSort = (arr) => {
    for (i = 0; i < arr.length - 1; i++) {
        let temp = i;
        for (j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[temp]) {
                let swap = arr[j];
                arr[j] = arr[temp];
                arr[temp] = swap;
            }
        }
    }
    return arr
}
console.log(selectSort(arr));

3.插入排序

• 插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
• 插入排序的基本思想是：每步将一个待排序的记录，按其值的大小插入前面已经排序的数组中适当位置上，直到全部插入完为止。

let arr = [41, 15, 2, 4, 848, 899, 44, 55, 667, 441, 102];
let insertSort = (arr) => {
    for (i = 0; i < arr.length - 1; i++) {
        for (i = 0; i < arr.length - 1; i++) {
            for (j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    let temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp
                }
            }
        }
        return arr
    }
}
console.log(insertSort(arr));