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

浏览数：20 / 时间：2015年06月08日

高级排序算法是处理大型数据集的最高效排序算法，它是处理的数据集可以达到上百万个元素，而不仅仅是几百个或者几千个。现在我们来学习下2种高级排序算法---- 希尔排序和快速排序。

一：希尔排序；

希尔排序的核心理念是：首先比较距离较远的元素，而非相邻的元素。

基本原理：通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。

下面我们来看看数组[0,9,1,8,7,6,2,3,5,4] 来使用希尔排序的原理；如下图：

代码分析如下：

1. 执行 "间隔序列=3的步骤"

A. 那么第一次执行 "间隔序列=3" 的步骤，那么找到位置间隔3的元素为 0 , 8 , 2 , 4

所以这四个数字当中0最小，所以位置不动，还是第一个位置，8是最大的所以位置就移动到之前的4的位置上，4移动到8的位置上，但是2和4比较 2小于4的所以2和4位置继续调换。所以现在的顺序为0 , 2 , 4 , 8，如上图(间隔序列=3)

B. 现在第二次执行 "间隔序列=3" 的步骤，找到元素为 9 , 7 , 3 分析还是和上面的一样 3是最小的，所以移动到原先9的位置上，9就移到到3的位置上，由于7小于9 所以不需要移动，所以现在的顺序为 3 , 7 , 9 如上图(间隔序列=3)

C. 现在第三次执行 "间隔序列=3"的步骤，找到元素 1 , 6 , 5 ,由于1是最小的所以不需要移动，6大于5，所以2者要调换位置所以顺序为 1 , 5 , 6

执行完上面的步骤后，正确的顺序为 [0,3,1,2,7,5,4,9,6,8]

2. 执行 "间隔序列=2"的步骤

A. 第一次查找找到元素 0,1,7,4,6,所以原理还是和上面一样，0和1不需要移动 7和4及6调换位置，因此现在的顺序变为 0,1,4,6,7

B. 第二次查找找到元素 3,2,5,9,8 ，所以顺序变为 2,3,5,8,9

执行完上面的步骤后，正确的顺序为 [0,2,1,3,4,5,6,8,7,9] 如上图(间隔序列=2)

3. 执行 "间隔序列=1"的步骤；

数组的顺序就变为 [0,1,2,3,4,5,6,7,8,9].如上图(间隔序列=1)

JS代码如下：

function CArray(numElements,gaps) {
    this.dataStore = [];
    this.pos = 0;
    this.numElements = numElements;
    this.gaps = gaps;
    this.insert = insert;
    this.toString = toString;
    this.clear = clear;
    this.shellSort = shellSort;
    for(var i = 0; i < numElements.length; i++) {
        this.dataStore[i] = numElements[i];
    }            
}
function clear() {
    for(var i = 0; i < this.dataStore.length; i++) {
        this.dataStore[i] = 0;
    }
}
function insert(element) {
    this.dataStore[this.pos++] = element;
}
function toString() {
    var restr = "";
    for(var i = 0; i < this.dataStore.length; i++) {
        restr += this.dataStore[i] + " ";
        if(i > 0 && i % 10 == 0) {
            restr+= "\n";
        }
    }
    return restr;
}
        
function shellSort() {
    for(var g = 0; g < this.gaps.length; ++g) {
        for(var i = this.gaps[g]; i < this.dataStore.length; ++i) {
            var temp = this.dataStore[i];
            for(var j = i; j >= this.gaps[g] && this.dataStore[j - this.gaps[g]] > temp; j -= this.gaps[g]) {
                this.dataStore[j] = this.dataStore[j - this.gaps[g]];
            }
            this.dataStore[j] = temp;
        }
    }
}
// 希尔排序测试代码
var numElements = [0,9,1,8,7,6,2,3,5,4];
var gaps = [3,2,1];
var myNums = new CArray(numElements,gaps);
myNums.shellSort();
console.log(myNums.toString());

二：快速排序

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大的元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。

这个算法首先要在列表中选择一个元素来作为基准值，数据排序围绕基准值进行，将列表中小于基准值的元素移动到数组的左边，将大于基准值的元素移动到数组的右边，如下图所示：

技术分享

基本原理是：

选择一个基准元素，将列表分割成2个子序列。基准元素的选择可以有3种方式，可以选择第一个元素作为基准元素，也可以把中间的值作为基准元素，还可以把最后一个元素作为基准的元素。
对列表重新排序，将所有小于基准值的元素放在基准值的前面，所有大于基准值的元素放在基准值的后面。
分别对较小元素的子序列和较大元素的子序列的重复步骤1和2.

下面是JS的代码如下：

// 快速排序
function qSort(list) {
    if(list.length == 0) {
        return [];
    }
    // 存储小于基准值的值
    var left = [];
    // 存储大于基准值的值
    var right = [];
    var pivot = list[0];
    for(var i = 1; i < list.length; i++) {
        if(list[i] < pivot) {
            left.push(list[i]);
        }else {
            right.push(list[i])
        }
    }
    return qSort(left).concat(pivot,qSort(right));
}
// 快速排序测试代码
var numElements = [44,75,23,43,55,12,64,77,33];
var list = qSort(numElements);
console.log(list);  // [12, 23, 33, 43, 44, 55, 64, 75, 77]