排序方法

内置排序

内置排序是由 JS 引擎提供的内置的排序方法，它使用 Array.prototype.sort() 对数组进行排序

• 对简单的数组进行排序：

  let arr = [5, 2, 8, 1, 4];
  arr.sort(function(a, b) {
     return a - b;
  });
  console.log(arr); // 输出：[1, 2, 4, 5, 8]
  

• 对对象数组进行排序：

  let fruits = [
     { name:'apple', price:5, weight:0.3 },
     { name:'banana',price:7, weight:0.8 },
     { name:'pear', price:2, weight:0.5 }
  ]
  //按照price字段升序排列
  fruits.sort(function(a,b){ return a.price - b.price })  
  // 输出：
  // {name: 'pear', price: 2, weight: 0.5}
  // {name: 'apple', price: 5, weight: 0.3}
  // {name: 'banana', price: 7, weight: 0.8}
  

冒泡排序

冒泡排序的工作原理是：重复地遍历要排序的数组，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数组的工作是重复地进行直到没有再需要交换，就说该明数组已经排序完成。

function bubbleSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素，可以使用解构赋值，也可以设置临时变量
                // [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

let arr = [5,8,7,6,1]
arr = bubbleSort(arr)  //输出：[1,5,6,7,8]

选择排序

选择排序是的工作原理是：首先在未排序数组中找到最小（或最大）元素，存放到排序数组的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序数组的末尾。以此类推，直到所有元素均排序完毕。

function selectionSort(arr) {
    let len = arr.length;
    let minIndex, temp;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        
        // 交换元素，可以使用解构赋值，也可以设置临时变量
        // [arr[i],arr[minIndex]] = [arr[minIndex],arr[i]]
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

let arr = [5,8,7,6,1]
arr = selectionSort(arr)  //输出：[1,5,6,7,8]

插入排序

插入排序的工作原理是：通过构建有序数组，对于未排序数据，在已排序数组中从后向前扫描，找到相应位置并插入。

function insertionSort(arr) {
    let len = arr.length;
    let preIndex, current;
    for (let i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

let arr = [5,8,7,6,1]
arr = insertionSort(arr)  //输出：[1,5,6,7,8]

快速排序

快速排序是一种高效的排序算法，它的工作原理是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行。以此达到整个数据变成有序序列。

//快速排序方法
function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        let partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
}
//分割方法
function partition(arr, left, right) {
    let pivot = left;
    let index = pivot + 1;
    for (let i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            [arr[i], arr[index]] = [arr[index], arr[i]];
            index++;
        }
    }
    [arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]];
    return index - 1;
}

let arr = [5,8,7,6,1]
arr = insertionSort(arr)  //输出：[1,5,6,7,8]