美文网首页
一些经典排序算法的实现

一些经典排序算法的实现

作者: builfen | 来源:发表于2018-05-23 17:06 被阅读0次
/*
 *  The some classical sorting algorithms, implement with JavaScript
 *  Author: mengshi
 *  Date: 2018.05.12
 */

/*
 * Name: bubble sort
 * Time: O(n^2), best ~ O(n), worst ~ O(n^2)
 * Space: O(1)
 * Stability: yes
 * Feature: exchange algorithms
 */
function bubble(arr) {
    for (var i=0; i < arr.length; i++) {
        for (var j=arr.length; j >= i j--) {
            if (arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }

    return arr;
}

/*
 * Name: select sort
 * Time: O(n^2), best ~ O(n^2), worst ~ O(n^2)
 * Space: O(1)
 * Stability: yes
 * Feature: select algorithms
 */
function select(arr) {
    for (var i=0; i < arr.length; i++) {
        var min = i;
        for (var j=arr.length; j > i; j--) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }

        if (i != min) {
            [arr[i], arr[min]] = [arr[min], arr[i]]
        }
    }

    return arr;
}

/*
 * Name: insert sort
 * Time: O(n^2), best ~ O(n), worst ~ O(n^2)
 * Space: O(1)
 * Stability: yes
 * Feature: insert algorithms
 */
function insert_sort(arr, step) {
    for (var i = step; i < arr.length; i+=step) {
        var mi = i;

        while (mi-step >= 0 && arr[mi-step] > arr[mi]) {
            [arr[mi], arr[mi-step]] = [arr[mi-step], arr[mi]];
            mi-=step;
        }
    }
}

function insert(arr) {
    insert_sort(arr, 1);
}

/*
 * Name: shell sort
 * Time: O(nlogn) ~ O(n^2), best ~ O(nlogn), worst ~ O(n^2)
 * Space: O(1)
 * Stability: no
 * Feature: insert algorithms
 */
function shell(arr) {
    var l = arr.length;

    while ((l = parseInt(l/2)) >= 1) {
        insert_sort(arr, l);
    }
}

/*
 * Name: merge sort
 * Time: O(nlogn), best ~ O(nlogn), worst ~ O(nlogn)
 * Space: O(n)
 * Stability: yes
 * Feature: merge algorithms
 */
function merge_sort(left, right) {
    var temp = []

    while (left.length > 0 && right.length > 0) {
        var x = left.shift(), y = right.shift()
        if (x <= y) {
            temp.push(x);
            right.unshift(y);
        } else {
            temp.push(y);
            left.unshift(x);
        }
    }

    if (left.length == 0) {
        return temp.concat(right);
    } else {
        return temp.concat(left);
    }
}

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

    var left  = arr.slice(0, arr.length/2);
    var right = arr.slice(arr.length/2);

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

/*
 * Name: heap sort
 * Time: O(nlogn), best ~ O(nlogn), worst ~ O(nlogn)
 * Space: O(1)
 * Stability: no
 * Feature: select algorithms
 */
function heap_adjust(arr, l, n) {
    var temp = arr[l];

    for(var j = l*2; j <= n; j*=2) {
        if (j < n && arr[j] < arr[j+1]) {
            j++;
        }

        if (temp >= arr[j]) {
            break;
        }

        arr[l] = arr[j];
        l = j;
    }

    arr[l] = temp;
}

function heap(arr) {
    var n = arr.length - 1
    for (var l = parseInt(n/2); l >= 0; l--) {
        heap_adjust(arr, l, n);
    }

    for (; n >= 0; n--) {
        [arr[0], arr[n]] = [arr[n], arr[0]]
        heap_adjust(arr, 0, n-1);
    }
}

/*
 * Name: quick sort
 * Time: O(nlogn), best ~ O(nlogn), worst ~ O(n^2)
 * Space: O(logn) - O(n)
 * Stability: no
 * Feature: exchange algorithms
 */
function partition(arr, low, high) {
    var key = arr[low];

    while (low < high) {
        while (low < high && arr[high] >= key) {
            high--;
        }
        [arr[low], arr[high]] = [arr[high], arr[low]];

        while (low < high && arr[low] <= key) {
            low++;
        }
        [arr[low], arr[high]] = [arr[high], arr[low]];
    }

    return low;
}

function quick_sort(arr, low, high) {
    if (low < high) {
        pivot = partition(arr, low, high);

        quick_sort(arr, low, pivot-1);
        quick_sort(arr, pivot+1, high);
    }
}

function quick(arr) {
    quick_sort(arr, 0, arr.length-1);
}

/*
 * program main function
 */
function main() {
    var arr = new Array(50, 10, 90, 30, 70, 40, 80, 60, 20);

    shell(arr);
    console.info(arr);
}

main();

相关文章

  • 一文搞定十大经典排序算法(Java实现)

    本文总结十大经典排序算法及变形,并提供Java实现。参考文章:十大经典排序算法总结(Java语言实现)快速排序算法...

  • 序言-算法

    此文集将介绍一些经典的算法,从经典的排序算法开始不定期的补充纠错更新 1、经典排序算法 1.1桶排序Bucket ...

  • python 排序算法

    文章概述 介绍各大常用经典的排序算法和效率,以及python实现常用算法(冒泡排序,选择排序,快速排序,插入排序)...

  • 2018-06-30

    排序算法之归并排序 归并排序算法是排序算法中的经典算法之一,其核心思想是利用归并的思想实现的排序方法,该算法采用经...

  • 排序算法

    小胡子哥:聊一聊排序算法白话经典算法系列之五 归并排序的实现

  • 【非比较类排序算法】计数排序、桶排序(PHP实现)

    常见的经典非比较类排序算法有计数排序、桶排序。区别于比较类排序,非比较类排序利用额外的内存空间实现更快排序,算法以...

  • 排序算法之归并排序

    归并排序(Merge Sort) 归并排序是利用归并的思想实现排序的方式,该算法采用的是经典的分治算法 归并排序过...

  • 归并排序&快速排序

    归并排序 利用归并的思想实现排序方法,该算法采用经典的分治策略,分而治之。 代码实现 基础设置 归并排序 —— 非...

  • JavaScript实现经典排序算法

    使用JavaScript实现的经典排序算法 util 冒泡 简单选择 直接插入 快速排序 堆排序 归并排序

  • <算法入门>快速理解7种排序算法 | python3

    算法是程序的灵魂,而排序算法 是算法的入门经典,作者在此用python亲自实现了7种主流的排序算法,并做简短的说明...

网友评论

      本文标题:一些经典排序算法的实现

      本文链接:https://www.haomeiwen.com/subject/kxtdjftx.html