排序就是将一组对象按照某种逻辑重新排列的过程。

初级排序算法

选择排序

不断重复找到最小的元素，移到相应位置。{0-N} = {0, 1, 2,..N}, {n} = swap( nums[n], min{ nums[n~nums.length] } )

1
2
3
4
5
6
7
let nums = [1,3,5,2,4];
for(let i =0; i< nums.length; i++) {
    for(let j = i; j < nums.length; j++) {
        minNum = min(minNum, nums[j]);
    }
    swap(minNum, nums[i]);
}

有 N 次交换和N+(N-1)+..+2+1~N^2/2次比较

插入排序

每次将一个数插入有序数组的适当位置。{0-N} = {0, 1, 2,..N},{n} = { nums[0~n]}.swap( less(nums[n], nums[n-1]) )

1
2
3
4
5
6
7
for(let i=0;i<nums.length; i++) {
    for(let j = i; j >0; j--){
        if(num[j] < nums[j-1]) {
            swap(nums[j], nums[j-1]);
        }
    }
}

插入排序所需的时间与输入的元素的初始顺序有关，最坏情况下需要N^2/2次比较和N^2/2次交换，最好需要N-1次比较和0次交换

归并排序

要将一个数组排序，可以递归地将它分成两半分别排序，然后在合并起来。{0-N} = merge( {0-N/2}, {N/2-N} );
merge(n) = { min( {0-n/2}, {n/2-n} ) }。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function sort(nums, lo, hi) {
   let  mid = (lo + hi ) / 2;
    sort(nums, lo, mid);
    sort(nums, mid+1, hi);
    merge(nums,lo, mid, hi);
}
function merge(nums, low, mid, high) {
    let i = lo, j = mid +1;
    for(let k = lo; k <= high, k++) {
        aux[k] = nums[k];
    }
    for(let k =lo; k<=high;k++) {
        if(i>mid) a[k] = aux[j++];
        else if(j > hi) a[k] = aux[i++];
        else if(less(aux[j], aux[k])) a[k] = aux[j++];
        else a[k] = aux[i++];
    }
}

时间复杂度NlgN,空间复杂度N,比初级算法较优

快速排序

当两个子数组有序时，就完成了排序。{0-N} = {0-K} + {K-N};partition(n) = swap( n1<k, k<n2 ),k = nums[lo]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function sort(nums, lo, hi) {
    let j = partition(nums,lo, hi);
    sort(nums, lo, j-1);
    sort(nums, j+1, hi);
}
function partition(nums, lo ,hi) {
    let i = lo, j = hi, k = nums[lo];
    while(true) {
        while(a[++i] < k) if(i = hi) break;
        while(a[++j] > k) if(j = lo) break;
        if(i>j) break;
        swap(nums[i], nums[j]);
    }
    swap(nums[lo], nums[j]);
    return j;
}

时间复杂度NlgN,空间复杂度lgN