数据结构与算法 - 高级排序算法

【1】 高级排序算法

1.希尔排序

这个算法在插入排序的基础上做了很大的改善。希尔排序的核心理念与插入排序不同，它会首先比较距离较远的元素，而非相邻的元素。，用这个算法遍历数据集时，所有元素之间的距离会不断减小。工作原理：定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。有一些公开定义的间隔序列。（算法用到的间隔序列提前定义好）；

function shellsort() {
    var dataStore = this;
    var gaps = [5, 3, 1];
    for (var g = 0; g < gaps.length; ++g) {
        for (var i = gaps[g]; i < dataStore.length; ++i) {
            var temp = dataStore[i];
            for (var j = i; j >= gaps[g] && dataStore[j-gaps[g]] > temp;
                j -= gaps[g]) {
                dataStore[j] = dataStore[j - gaps[g]];
            }
            dataStore[j] = temp;
        }
    }
    return this;
}
Array.prototype.shellsort = shellsort;

计算动态间隔序列
var N = dataStore.length;
var h = 1;
while (h < N/3) {
h = 3*h +1;
}

动态计算间隔序列的希尔排序

function shellsort1() {
    var dataStore = this;
    <!-- 动态间隔序列 -->
    var N = dataStore.length;
    var h = 1;
    while (h < N/3) {
        h = 3 * h + 1;
    }

    while (h >= 1) {
        for (var i = h; i < N; i++) {
            for (var j = i; j >= h && dataStore[j] < dataStore[j-h]; j -= h) {
                dataStore.swap(j, j-h);
            }
        }
        h = (h-1)/3;
    }
}

2.归并排序

把一系列排好序的子序列合并成一个大的完整的有序序列。
1.自顶向下的归并排序，这种算法的递归深度对它来讲太深了。所以我们将使用一种非递归的方式来实现这个算法，即自底向上的归并排序；
2.自底向上的归并排序。

function mergeSort(arr) {
    if (arr.length < 2) {
        return;
    }
    var step = 1;
    var left, right;
    while (step < arr.length) {
        left = 0;
        right = step;
        while (right + step <= arr.length) {
            mergeArrays(arr, left, left+step, right, right+step);
            left = right + step;
            right = left + step;
        }
        if (right < arr.length) {
            mergeArrays(arr, left, left+step, right, arr.length);
        }
        step *= 2;
    }
}

function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
    var rightArr = new Array(stopRight - startRight + 1);
    var leftArr = new Array(stopLeft - startLeft + 1);
    k = startRight;
    for (var i = 0; i < (rightArr.length-1); ++i) {
        rightArr[i] = arr[k];
        ++k;
    }

    k = startLeft;
    for (var i = 0; i < (leftArr.length-1); ++i) {
        leftArr[i] = arr[k];
        ++k;
    }

    rightArr[rightArr.length-1] = Infinity; // a sentinel value
    leftArr[leftArr.length-1] = Infinity; // a sentinel value
    var m = 0;
    var n = 0;
    for (var k = startLeft; k < stopRight; ++k) {
        if (leftArr[m] <= rightArr[n]) {
            arr[k] = leftArr[m];
            m++;
        }
        else {
            arr[k] = rightArr[n];
            n++;
        }
    }
    print("left array - ", leftArr);
    print("right array - ", rightArr);
}

3.快速排序

处理大数据集最快的排序算法之一。是一种分而治之的算法，通过递归的方式将数据一次分解为包含较小元素和较大元素的不同子序列。

首先要在列表中选择一个元素作为基准值，数据排序围绕基准值进行，
将列表中小于基准值的的元素移到数组的底部，
将大于基准值的元素移动到数组的底部。

function qSort(arr) {
    if (arr.length == 0) {
        return [];
    }
    var left = [];
    var right = [];
    var pivot = arr[0];
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {

           left.push(arr[i]);
        } else {

           right.push(arr[i]);
        }
    }
    return qSort(left).concat(pivot, qSort(right));
}
var a = [];
for (var i = 0; i < 10; ++i) {
   a[i] = Math.floor((Math.random()*100)+1);
}
print(a);
print(qSort(a));

需要知道的是：快速排序算法非常适用于大型数据集合；而在小数据集时性能反而会有所下降