可视化的排序过程
下面是一个日本程序员制做的一个可视化的排序过程，包括了各种经典的排序算法，你可以调整速度和需要排序的个数。酷壳以前也介绍过几篇相关的文章 一个排序算法比较的网站，一个显示排序过程的Python脚本 关于各种排序算法的运行复杂度比较，请参看Wikipedia的排序算法比较。
（转载本站文章请注明作者和出处 酷 壳 – CoolShell ，请勿用于任何商业用途）
(67 人打了分，平均分： 4.76 )
Loading... (67 人打了分，平均分： 4.76 )Loading...
《可视化的排序过程》的相关评论
你想说什么？
链接被吞了？
来人啊 快补链接
坐等链接~~~
太监
立等链接～～～
对不起，wordpress 对 iframe 支持有问题。现在好了。
bogo好幽默。。
我了个去，bogo我等了半小时都没好。。。bogo是在排序么？
bogo悲催了啊，它这是在排序吗？
很直观，谢谢！
bogo太悲剧了…
ソートアルゴリズムを映像化してみた – 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)
}
})
})()
好吊！！！
应该输出每次和最终的工作量（比较和交互的次数）
自己之前写过一个3d的版本: http://bit.ly/hW73AZ （需要安装 python2.7 和 vpython）
一个中国人写的可视化排序以及一个框架：http://blog.zhaojie.me/2011/03/sorting-animations-with-jscex.html
在计算机科学中，Bogo排序（bogo-sort）是个既不实用又原始的排序算法，其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自Quantum bogodynamics，又称bozo sort、blort sort或猴子排序（参见无限猴子定理）。 —-wikipedia
哈哈哈哈
很直观
Stanford的某个C++的课上见过这个意思的演示, 而且还是带声音的, 通过声音频率判断是什么排序.
bogo是在开玩笑啊，这种只是利用计算机计算上的优势的算法效率太低了。
bogo就是在赌人品
插入排序在演示的时候，同样选择了最低的速度，以及30个柱子来排序，速度好像特别的快哇，插入排序有这么高的效率？
如果可以反应出空间利用率就更加高了， 有些算法不是一眼就能看明白，图形化的不够。。。不过对图像学习者可以很好的通过塔来把握数据结构，当年我们上数据结构课程的时候老师照着清华大学的严蔚敏教授的蓝皮数据结构教材在黑板上抄写快速排序的代码，差距阿，感慨一下。
bogo,真的算排序？
在计算机科学中，Bogo排序（bogo-sort）是个既不实用又原始的排序演算法，其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自Quantum bogodynamics，又称bozo sort、blort sort或猴子排序（参见无限猴子定理）。
@momo5269
用firebug来单步调试各种排序方式就更加直观了
用眼睛看。。。个人觉得Merge和Heap速度最快。。。
在Python下自己写了下这些排序，结果发现均不如内建sorted()函数快。。。囧，为什么啊？
@yuxcer 因为 sorted() 是用 C 写的 ;-)
数量多了之后，才看到了快速排序的速度
微软的IE test driver页面有一个可视化的快排
Bogo 是啥玩意儿啊？由永远也排不完。
@Seamlik
看了维基百科，笑死了。Bogo就是生成随机顺序，如果恰好排好，就结束，否则继续……
Bogo笑死我了
bogo设速度300，五个格 OK
其平均时间复杂度是 O(n × n!)，在最坏情况所需时间是无限。它并非一个稳定的算法。
sound of sorting
http://panthema.net/2013/sound-of-sorting/