常见排序算法

插入排序

1. 直接插入排序 (insertion sort)

这是一种最简单的排序算法，基本操作是：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表
当N很小时，这种算法很快。N很大时很慢。

// 直接插入排序算法
function insertSort(arr, compare) {
    for(let i=1; i< arr.length; i++) {
        if(compare(arr[i], arr[i-1])) {
            let temp = arr[i-1];
            arr[i-1] = arr[i];
            arr[i] = temp;
            for(let n=i-2; n>=0 && compare(arr[n+1], arr[n]); n--){
                let temp = arr[n];
                arr[n] = arr[n+1];
                arr[n+1] = temp;
            }
        }
    }
    return arr;
}

function compare (a, b) {
    return a < b;
}

const arr = [1,2,5,4,3,7,8,9,5,4,3,2,1];

const sortedArr = insertSort(arr, compare);

算法简洁，容易实现，但它的效率不高。

从空间上看，只需要一个用于交换时的temp，因此空间复杂度为O(1)

从时间上看，在一趟插入排序中，第二个for循环的次数取决于待插入记录的关键字与有序表中记录的关键字之间的关系。

当数组为正序时，算法所需比较次数为n-1次(每趟比较1次，共有n-1趟);
当数组为逆序时，所需比较次数为最大值(2+n)(n-1)/2 (首项加末项，乘项数，除以2)，记录移动次数为最大值(3+(n+1))(n-1)/2

时间复杂度为O(n²);

2. 其他插入排序

折半插入排序

在关键字比较时采用折半查找的方法，减少了比较次数，但记录移动次数不变，因此时间复杂度不变。

2-路插入排序、表插入排序、希尔排序等

归并排序 (Merge sort)

“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。  
归并操作无论是顺序存储结构还是链式存储结构都能在O(M+N)的时间量级上实现。  

function mergeSort(arr) {
    if(arr.length === 1) 
        return arr;

    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    const result = [];

    for(var i = 0, j = 0; i < left.length && j < right.length;) {
        if(compare(left[i], right[j])) {
            result.push(left[i++]);
        } else { 
            result.push(right[j++]);
        }
    }

    return i === left.length ? result.concat(right.slice(j)) : result.concat(left.slice(i));
}

function compare(a, b) {
    return a <= b;
}

冒泡排序 (Bubble sort)

过称：首先比较第一个记录和第二个记录，若逆序，则交换，然后比较第二个记录和第三个记录，以此类推，直到第n-1个记录和第n个记录，完成一趟冒泡排序，此时最大的记录被移动到了最后一个位置。然后进行第2趟、第3趟...。直到第n-1趟 或 在这一趟排序过程中没有进行过交换记录的操作。

function bubbleSort (arr, compare) {
    for(let i=0; i<arr.length-1; i++) {
        for(let j=i; j<arr.length-1; j++) {
            if(compare(arr[j+1], arr[j])) {
                let temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

function compare (a, b) {
    return a < b;
}

时间复杂度：若为正序，需要进行n-1次关键字比较，不移动记录；若为逆序，需要进行n-1趟排序，进行(1+(n-1))(n)/2次比较和等数量级的移动。因此总时间复杂度为O(n²)。

快速排序

基本过程：

1\. 在数据集之中，选择一个元素作为"基准"（pivot）。  
2\. 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。  
3\. 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止  

function quickSort(arr) {

    if (arr.length <= 1) {
        return arr;
    }

    const left = [];
    const right = [];
    const pivot = arr[0];

    for (let i = 1; i < arr.length; i++) {

        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return quickSort(left).concat(pivot, quickSort(right));
}

时间复杂度和空间复杂度

时间复杂度和空间复杂度