可视化的排序过程

可视化的排序过程

下面是一个日本程序员制做的一个可视化的排序过程,包括了各种经典的排序算法,你可以调整速度和需要排序的个数。酷壳以前也介绍过几篇相关的文章 一个排序算法比较的网站一个显示排序过程的Python脚本 关于各种排序算法的运行复杂度比较,请参看Wikipedia的排序算法比较


关注CoolShell微信公众账号和微信小程序

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——
好烂啊有点差凑合看看还不错很精彩 (64 人打了分,平均分: 4.94 )
Loading...

可视化的排序过程》的相关评论

  1. ソートアルゴリズムを映像化してみた – js do it

    html, body{
    padding: 0px;
    margin: 0px;
    background: white;
    }

    .graphical-sort{
    position: relative;
    width: 100%;
    height: 100%;
    padding-top: 40px;

    }

    .graphical-sort .bars-container{
    height: 100%;
    background: #222;
    white-space: nowrap;
    overflow: hidden;
    }

    .graphical-sort .bars-container span{
    display: inline-block;
    position: relative;
    height: 100%;
    background: #35bddb;
    border-left: 1px solid #222;

    -webkit-box-sizing: border-box;
    -moz-box-sizing: border-box;
    box-sizing: border-box;
    }

    .graphical-sort .bars-container span.highlight{
    background: #aee496;
    }

    .graphical-sort .controller{
    position: absolute;
    font-size: 10px;
    white-space: nowrap;
    overflow: visible;
    top: 0px;

    }
    .graphical-sort .controller .widget{
    margin-right: 5px;
    }

    .graphical-sort .controller .speed-amount{
    display: inline-block;
    width: 25px;
    }

    .graphical-sort .controller .speed-slider{
    display: inline-block;
    width: 95px;
    }

    $(function(){
    // —————————————–
    // Bubble sort
    // —————————————–
    function bubbleSort(){
    var array = this.values
    var length = array.length
    for(var i = length – 1; 0 < i; i–){
    for(var j = 0; j < i; j++){
    this.compare(j, j + 1)
    }
    }
    }

    // —————————————–
    // Selection sort
    // —————————————–
    function selectionSort(){
    var array = this.values
    var length = array.length
    for(var i = 0; i < length – 1; i++){
    var minIndex = i
    var minValue = array[minIndex]
    for (var j = i + 1; j < length; j++) {
    this.highlight(j, minIndex)
    if (array[j] < minValue) {
    minIndex = j
    minValue = array[minIndex]
    }
    }
    this.compare(i, minIndex)
    }
    return array
    }
    // —————————————–
    // Shaker Sort
    // —————————————–
    function shakerSort(){
    var array = this.values
    var length = array.length
    var left = 0
    var right = length – 1
    var lastSwappedLeft = left
    var lastSwappedRight = right

    while(left < right){
    lastSwappedRight = 0
    for(var i = left; i array[i + 1]){
    this.swap(i, i + 1)
    lastSwappedRight = i
    }else{
    this.highlight(i, i + 1)
    }
    }
    right = lastSwappedRight

    lastSwappedLeft = length – 1
    for(var j = right; left array[j]){
    this.swap(j – 1, j)
    lastSwappedLeft = j
    }else{
    this.highlight(j – 1, j)
    }
    }
    left = lastSwappedLeft
    }
    }
    // —————————————–
    // Insertion sort
    // —————————————–
    function insertionSort(){
    var array = this.values
    var length = array.length
    for(var i = 1; i < length; i++){
    for(var j = i; 0 array[j]){
    this.swap(j – 1, j)
    }else{
    this.highlight(j – 1, j)
    break
    }
    }
    }
    }

    // —————————————–
    // Shell Sort
    // —————————————–
    function shellSort(){
    var array = this.values
    var length = array.length
    var gap = 1
    while(gap 1){
    gap = Math.floor(gap / 3)
    for(var i = gap; i < length; i++){
    for(var j = i; 0 array[j]){
    this.swap(j – gap, j)
    }else{
    this.highlight(j – gap, j)
    break
    }
    }
    }
    }
    }

    // —————————————–
    // Quick sort
    // —————————————–
    function quickSort(first, last){
    // TODO: あとで書き直す
    var array = this.values
    first = (first === undefined) ? 0 : first
    last = (last === undefined) ? (array.length – 1) : last

    var pivotIndex = Math.floor((first + last) / 2)
    var pivotValue = array[pivotIndex]
    var f = first, l = last
    while(true){
    while(true){
    this.highlight(f, pivotIndex)
    if(!(array[f] < pivotValue)) break
    f++
    }
    while(true){
    this.highlight(l, pivotIndex)
    if(!(pivotValue < array[l])) break
    l–
    }
    if(l <= f){
    break
    }
    if(pivotIndex === l){
    pivotIndex = f
    }
    if(pivotIndex === l){
    pivotIndex = l
    }
    this.compare(f, l)
    f++; l–
    }
    if(first < f – 1) quickSort.call(this, first, f – 1)
    if(l + 1 < last) quickSort.call(this, l + 1, last)
    }

    // —————————————–
    // Merge sort
    // —————————————–
    function mergeSort(first, last){
    var array = this.values
    first = (first === undefined) ? 0 : first
    last = (last === undefined) ? array.length – 1 : last
    if (last – first < 1) {
    return
    }
    var middle = Math.floor((first + last) / 2)
    mergeSort.call(this, first, middle)
    mergeSort.call(this, middle + 1, last)

    var f = first
    var m = middle

    while (f <= m && m + 1 = array[m + 1]) {
    this.insertBefore(m + 1, f)
    m++
    }
    f++
    }
    }

    // —————————————–
    // Heap sort
    // —————————————–
    function swapUp(array, current){
    var parent = Math.floor((current – 1) / 2)
    while(current != 0){
    if (!(array[current] > array[parent])) {
    this.highlight(current, parent)
    break
    }
    this.swap(current, parent)
    current = parent
    parent = Math.floor((current – 1) / 2)
    }
    }

    function swapDown(array, current, length){
    var child = current * 2 + 1
    while(true){
    if(array[child] = array[child]){
    this.highlight(current, child)
    break
    }
    if(length <= child){
    break
    }
    this.swap(current, child)
    current = child
    child = current * 2 + 1
    }
    }

    function heapify(array){
    for(var i = 0; i < array.length; i++){
    swapUp.call(this, array, i)
    }
    }

    function heapSort(){
    var array = this.values
    heapify.call(this, array)
    for(var i = array.length – 1; 0 array[i]){
    this.swap(0, i)
    }else{
    this.highlight(0, i)
    }
    swapDown.call(this, array, 0, i)
    }
    }

    // —————————————–
    // Bogo sort
    // —————————————–
    function bogoSort(){
    var array = this.values
    this.bogoSortCompleted = false
    var length = array.length
    // shffle
    for(var i = 0; i < length; i++){
    var j = Math.floor(Math.random() * length)
    this.swap(i, j)
    }

    // check
    for(var i = 0; i array[i + 1]){
    return // incomplete
    }
    }
    this.bogoSortCompleted = true
    }
    bogoSort.name = “bogoSort”

    // —————————————–
    // Main
    // —————————————–
    var sort = GraphicalSort()

    // default sort function
    sort.sortFunc = bubbleSort

    var view = $(“#view”)
    view.width($(window).width()).height($(window).height() – 125)
    sort.show(view)

    // —————————————–
    // Sort menu
    // —————————————–
    var sortMenu = {
    “Bubble”: bubbleSort,
    “Selection”: selectionSort,
    “Shaker”: shakerSort,
    “Insertion”: insertionSort,
    “Shell”: shellSort,
    “Quick”: quickSort,
    “Merge”: mergeSort,
    “Heap”: heapSort,
    “Bogo”: bogoSort
    }

    var menu = $(“”).insertBefore(view).css({
    marginBottom: 10,
    fontSize: 12
    })
    $.each(sortMenu, function(name, func){
    var radio = $(“”).attr(“id”, name).appendTo(menu)
    var label = $(“”).attr(“for”, name).text(name).appendTo(menu)

    radio.click(function(){
    sort.sortFunc = func
    sort.displayBars()
    })

    if(sort.sortFunc === func){
    radio.attr(“checked”, “true”)
    }
    })
    menu.buttonset()
    })

    (function(){
    var PROFILE = false
    //var PROFILE = true

    // —————————————–
    // Utils
    // —————————————–
    jQuery.fn.swap = function(b){
    b = jQuery(b)[0];
    var a = this[0];
    var temp = a.parentNode.insertBefore(document.createTextNode(”), a);
    b.parentNode.insertBefore(a, b);
    temp.parentNode.insertBefore(b, temp);
    temp.parentNode.removeChild(temp);
    return this;
    }

    Array.prototype.insert = function(value, index){
    var array = this
    for(var i = array.length – 1; index <= i; i–){
    array[i + 1] = array[i]
    }
    array[index] = value
    }

    Array.prototype.insertBefore = function(from, to){
    this.insert(this[from], to)
    if(to < from){
    from += 1
    }
    this.splice(from, 1)
    }
    Array.prototype.swap = function(a, b){
    var temp = this[a]
    this[a] = this[b]
    this[b] = temp
    }

    function range(min, max){
    var array = []
    while(min < max){
    array.push(min)
    min++
    }
    return array
    }

    function randrange(min, max){
    return Math.floor(Math.random() * (max – min)) + min
    }

    function shuffle(array){
    var length = array.length
    for(var i = 0; i < length; i++){
    var j = randrange(0, length)
    var temp = array[i]
    array[i] = array[j]
    array[j] = temp
    }
    return array
    }

    window.profile = {
    nowProfiling: false,
    start: function(name){
    if(PROFILE === false) return
    if(this.nowProfiling){
    console.profileEnd()
    }
    this.nowProfiling = true
    console.profile(name)
    },
    end: function(){
    if(PROFILE === false) return
    this.nowProfiling = false
    console.profileEnd()
    }
    }

    // —————————————–
    // Queue class
    // —————————————–
    var Queue = Class.$extend({
    __init__: function(){
    this.length = 0
    this.i = 0
    this.queue = []
    },

    get: function(){
    if(this.length === 0)
    return undefined
    this.length–
    return this.queue[this.i++]
    },

    put: function(value){
    this.queue.push(value)
    this.length++
    }
    })

    // —————————————–
    // Controller class
    // —————————————–
    Controller = Class.$extend({
    widget: $("”),
    reset: $.noop,
    onSpeedChange: $.noop,
    onLengthChange: $.noop,

    __init__: function(defaults){
    this.element = $(“”)
    var restart = this._createRestartButton()
    var buttonset = this._createLengthButtonSet(defaults.length)
    var slider = this._createSpeedSlider(defaults.speed)
    this.element.append(restart).append(buttonset).append(slider)
    },

    _createRestartButton: function(){
    var self = this
    var button = $(“Restart”).button().click(function(){
    self.restart()
    })
    return this.widget.clone().append(button)
    },

    _createSpeedSlider: function(defaultSpeed){
    var self = this
    var amount = $(“”).text(defaultSpeed)
    var slider = $(“”)
    slider.slider({
    min: 1,
    max: 300,
    value: defaultSpeed,
    slide: function(event, ui){
    amount.text(ui.value)
    self.onSpeedChange(ui.value)
    }
    })

    var sliderWrapper = $(“”).append(amount).append(slider)
    return this.widget.clone().text(“Speed: “).append(sliderWrapper)
    },

    _createLengthButtonSet: function(defaultLength){
    var self = this
    var buttonset = this.widget.clone().addClass(“length-button”)
    var radioName = “graphical-sort-radio”
    var _label = $(“”)
    var _radio = $(“”).attr(“name”, radioName)
    $.each([5, 10, 30, 50, 100, 200], function(i, length){
    var label = _label.clone().text(length).attr(“for”, radioName + length)
    var radio = _radio.clone().attr(“id”, radioName + length).val(length)
    buttonset.append(label).append(radio)
    })
    buttonset.find(“input[value=” + defaultLength + “]”).attr(“checked”, “checked”)
    buttonset.buttonset()
    buttonset.click(function(event, ui){
    self.onLengthChange(parseInt(event.target.value))
    })
    return buttonset
    }
    })
    // —————————————–
    // Bar class
    // —————————————–
    var Bar = Class.$extend({
    __init__: function(value){
    this.value = value
    },
    createElement: function(){
    var bar = $(“”)
    return bar
    }
    })

    // —————————————–
    // Bars class
    // —————————————–
    var Bars = Class.$extend({
    __init__: function(length, container){
    this.length = length
    this.container = container
    this.bars = []
    var values = this.values = shuffle(range(1, length+1))

    for(var i = 0; i this.values[b]){
    this.values.swap(a, b)
    command = C.swap
    }
    this.task.put([a, b, command])
    },

    // graphical API
    highlight: function(a, b){
    this.task.put([a, b, C.highlight])
    },

    // graphical API
    swap: function(a, b){
    this.values.swap( a, b)
    this.task.put([a, b, C.swap])
    },

    // graphical API
    insertBefore: function(from, to){
    this.values.insertBefore(from, to)
    this.task.put([from, to, C.insert])
    },

    show: function(viewElement){
    if(this.sortFunc === undefined){
    throw Error(“sort function is undefined”)
    }
    this.$sort = $(“”)
    this.$sort.append(this._createController().element)
    this.container = $(“”)
    this.$sort.append(this.container)

    viewElement.append(this.$sort)
    this.displayBars()
    },

    displayBars: function(){
    clearTimeout(this.currentTaskId)
    this.bars = Bars(this.length, this.container)
    this.values = this.bars.values
    this.container.empty().append(this.bars.elements)
    this._initTask()

    profile.start()
    this._setTimeout()
    },

    complete: function(){
    this.container.find(“span”).removeClass(“highlight”)
    if(this.sortFunc.name === “bogoSort”){
    if(this.bogoSortCompleted === false){
    this._initTask()
    this._setTimeout()
    return
    }
    }
    profile.end()
    },

    _createController: function(){
    this.controller = Controller({
    speed: this.speed,
    length: this.length
    })
    return this._setEventToController(this.controller)
    },

    _setEventToController: function(controller){
    var self = this
    controller.onLengthChange = function(length){
    self.length = length
    self.displayBars()
    }
    controller.onSpeedChange = function(speed){
    self.speed = speed
    }
    controller.restart = function(){
    self.displayBars()
    }
    return controller
    },

    _initTask: function(){
    this.task = Queue()
    this.sortFunc()
    },

    _next: function(){
    var order = this.task.get()
    if(order === undefined){
    this.complete()
    return
    }
    var command = order[2]
    if(command === C.insert){
    this.bars.insert(order[0], order[1])
    }else{
    this.bars.swap(order[0], order[1], command)
    }

    this._setTimeout()

    },

    _setTimeout: function(){
    var self = this
    var interval = 2000 / this.speed
    this.currentTaskId = setTimeout(function(){
    self._next()
    }, interval)
    }
    })

    })()

  2. 一个中国人写的可视化排序以及一个框架:http://blog.zhaojie.me/2011/03/sorting-animations-with-jscex.html

  3. 在计算机科学中,Bogo排序(bogo-sort)是个既不实用又原始的排序算法,其原理等同将一堆卡片抛起,落在桌上后检查卡片是否已整齐排列好,若非就再抛一次。其名字源自Quantum bogodynamics,又称bozo sort、blort sort或猴子排序(参见无限猴子定理)。 —-wikipedia
    哈哈哈哈

  4. 插入排序在演示的时候,同样选择了最低的速度,以及30个柱子来排序,速度好像特别的快哇,插入排序有这么高的效率?

  5. 如果可以反应出空间利用率就更加高了, 有些算法不是一眼就能看明白,图形化的不够。。。不过对图像学习者可以很好的通过塔来把握数据结构,当年我们上数据结构课程的时候老师照着清华大学的严蔚敏教授的蓝皮数据结构教材在黑板上抄写快速排序的代码,差距阿,感慨一下。

  6. 在计算机科学中,Bogo排序(bogo-sort)是个既不实用又原始的排序演算法,其原理等同将一堆卡片抛起,落在桌上后检查卡片是否已整齐排列好,若非就再抛一次。其名字源自Quantum bogodynamics,又称bozo sort、blort sort或猴子排序(参见无限猴子定理)。

  7. 在Python下自己写了下这些排序,结果发现均不如内建sorted()函数快。。。囧,为什么啊?

  8. 其平均时间复杂度是 O(n × n!),在最坏情况所需时间是无限。它并非一个稳定的算法。

发表评论

电子邮件地址不会被公开。 必填项已用*标注