當前位置：
首頁 >
前端技术
> javascript
>内容正文
javascript
JS写的排序算法演示
生活随笔
收集整理的這篇文章主要介紹了
JS写的排序算法演示
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
看到網上有老外寫的，就拿起自已之前完成的jmgraph畫圖組件也寫了一個。
想了解jmgraph的請移步：https://github.com/jiamao/jmgraph
當前演示請查看：http://graph.jm47.com/example/sort.html
?
<!doctype html> <html><head><meta content="text/html; charset=UTF-8" http-equiv="content-type" /><title>排序算法演示</title> <meta name="viewport" content="width=device-width,initial-scale=1"> <script src="http://mat1.gtimg.com/www/mobi/js/zepto.min.js"></script><!--[if lt IE 9]><script type="text/javascript" src="../../jmgraph/src/lib/excanvas.js"></script><![endif]--> <!--<script type="text/javascript" src="../src/jmgraph.debug.js"></script> --><script type="text/javascript" src="../dist/jmGraph.min.js"></script></head><button id="btn_quick" href="#">快速排序</button><button id="btn_straightinsertion" href="#">直接插入排序</button><button id="btn_shell" href="#">希爾排序</button><button id="btn_simpleselection" href="#">簡單選擇排序</button><button id="btn_simpleselection2" href="#">二元選擇排序</button><button id="btn_bubble" href="#">冒泡排序</button><body style="width:100%;"><div id="mycanvas" style="border:1px solid #ddd;width:100%;"></div> </body><script type="text/javascript">//排序管理對象function jmSort() {//原始數組個數this.arrCount = 20;//原始數組this.source = [];var container = document.getElementById('mycanvas');this.canvasWidth = Math.min(600, document.getElementById('mycanvas').offsetWidth - 10);container.style.width = this.canvasWidth + 'px';this.canvasHeight = Math.min(450, window.innerHeight - 10);container.style.height = this.canvasHeight + 'px';this.graph = new jmGraph('mycanvas',this.canvasWidth,this.canvasHeight); this.rectStyle = {stroke:'rgb(173,173,209)',lineWidth:1,close:true,fill: 'rgb(8,209,54)'};this.disableStyle = {stroke:'rgba(173,173,209,0.8)',lineWidth:1,close:true,fill: 'rgba(88,196,113,0.5)'};//this.rectStyle.shadow = this.graph.createShadow(2,2,2,'rgb(39,40,34)');this.selectRectStyle = {stroke:'rgb(120,20,80)',lineWidth:1,zIndex: 100,close:true,fill: 'rgba(255,180,5,0.7)'};//this.selectRectStyle.shadow = this.graph.createShadow(4,4,6,'rgb(39,40,34)');//基準樣式this.datumRectStyle = {stroke:'rgb(224,84,68)',lineWidth:2,close:true,zIndex: 50,lineType: 'dotted',fill: 'rgba(224,84,68,0.7)'};this.labelStyle = {stroke:'rgb(120,20,80)',textAlign: 'center',textBaseline: 'middle',font: '12px Arial',lineWidth:1};}//延遲數組循環 jmSort.prototype.arrayTimeout = function(arr, fun, endfun, t, index, end) {index = index || 0;end = end || arr.length;var t = t || 200;var self = this;function intervalArr() {if(index >= end) {endfun && endfun(); return;}var r = fun(index, arr[index], function(){index ++;self.timeoutHandler = setTimeout(intervalArr, t);});if(r === false) {endfun && endfun(); return}}intervalArr();}//柱子移動動畫 jmSort.prototype.rectAnimate = function(rect, cb) {if(typeof index == 'function') {cb = index;index = 0;}if(!rect.length) {rect = [rect];}var tox = [];var offx = [];var pos = [];var count = rect.length;for(var i=0;i<count;i++) {pos[i] = rect[i].rect.position();//重新計算其x坐標 tox[i] = this.xStep * rect[i].index + 10;offx[i] = (tox[i] - pos[i].x) / 20;}var self = this;function move() {var complete = 0;for(var i=0;i<count;i++) {pos[i].x += offx[i];if(offx[i] ==0 || (offx[i] > 0 && pos[i].x >= tox[i]) || (offx[i] < 0 && pos[i].x <= tox[i])) {pos[i].x = tox[i]; complete++; } }self.graph.redraw();if(complete >= count) {cb && cb();}else {self.aniTimeoutHandler = setTimeout(move, 20);} }move(); }//播放動畫 jmSort.prototype.play = function(frames, callback) {if(typeof frames == 'function') {callback = frames;frames = null;}frames = frames || this.frames;if(frames.length == 0) {callback && callback();return;}var f = frames.splice(0,1)[0];//取最早的一個var self = this;if(f.move && f.move.length) {//var count = 0;//for(var i=0;i<f.move.length;i++) {this.rectAnimate(f.move, function(){//count ++;//if(count >= f.move.length) { self.play(callback);//} });//} }else if(f.sels) {this.selectRect.apply(this, f.sels);this.play(callback);//setTimeout(function(){// self.play(callback);//}, 40); }else if(f.datum) {if(this.datumLine) {var start = this.datumLine.start();var end = this.datumLine.end();start.y = end.y = f.datum.rect.position().y;this.datumLine.visible = true;}this.play(callback);}else if(f.refresh) {this.refreshGraph(f.refresh);this.play(callback);} else {this.play(callback);} }//初始化排序條件，原始數組 jmSort.prototype.init = function(){this.source = [];this.frames = [];var max = 100;var offy = this.canvasHeight - 20;this.graph.children.clear();//當前 x軸分布單位寬度this.xStep = (this.canvasWidth - 20) / this.arrCount;for(var i=0;i<this.arrCount;i++) {var v = {};v.value = Math.floor(Math.random() * max);v.height = v.value / max * offy;this.source.push(v);}//畫基準線this.datumLine = this.graph.createLine({x:0,y:0},{x:this.canvasWidth,y:0},this.datumRectStyle);this.datumLine.visible = false;this.graph.children.add(this.datumLine);this.refreshGraph(this.source);}jmSort.prototype.reset = function() {if(this.timeoutHandler) clearTimeout(this.timeoutHandler);if(this.aniTimeoutHandler) clearTimeout(this.aniTimeoutHandler);if(this.datumLine) this.datumLine.visible = false;//this.refreshGraph(); this.init(); }//刷新畫布 jmSort.prototype.refreshGraph = function(arr) {arr = arr || this.source;//this.graph.children.clear();var offy = this.canvasHeight - 20;for(var i=0;i<arr.length;i++) { if(arr[i].rect) {var pos = arr[i].rect.position();pos.x = this.xStep * i + 10;}else { var pos = {};pos.x = this.xStep * i + 10;pos.y = offy - arr[i].height;arr[i].rect = this.graph.createShape('rect',{position:pos,width: 10, height: arr[i].height, style: this.rectStyle});var label = this.graph.createShape('label',{style:this.labelStyle,position:{x:0,y:arr[i].height},value:arr[i].value,width:10,height:20});arr[i].rect.children.add(label);this.graph.children.add(arr[i].rect);}//this.graph.children.add(arr[i].rect); }this.graph.redraw();}//選中某幾個值，則加亮顯示 jmSort.prototype.selectRect = function(datum, sels, area) {var self = this;this.graph.children.each(function(i, rect) {if(!rect.is('jmRect')) return;if(sels && sels.indexOf(rect) > -1) {rect.style = self.selectRectStyle;}else if(datum && datum.indexOf(rect) > -1) {rect.style = self.datumRectStyle;}else if(area && area.indexOf(rect) > -1) {rect.style = self.rectStyle;} else {rect.style = self.disableStyle;}});this.graph.refresh();}//快速排序//取其中一個值，把小于此值的放到其左邊，大于此值的放到其右邊//如此遞歸 jmSort.prototype.quickSort = function(arr, callback) {if(typeof arr == 'function') {callback = arr;arr = null;}arr = arr || this.source;var self = this;function sort(source, oldleft, oldrigth) {if(source.length <= 1) return source;//取一個值做為比較對象，這里直接取中間的值（任務一個都可）var mindex = Math.floor(source.length /2); var m = source[mindex];//基準值 self.frames.push({datum: m});//選中當前區域var area = [];for(var i=0;i<source.length;i++) {area.push(source[i].rect);}self.frames.push({sels:[[m.rect],null, area]});var left = mindex>0?source.slice(0, mindex):[];var right = mindex>0&&mindex<source.length-1?source.slice(mindex+1):[];var middle = [m];var index = oldleft?oldleft.length:0;for(var i=0;i<source.length;i++) {var s = source[i];self.frames.push({sels:[[m.rect],[s.rect], area]});var f = {move:[]};var sindex = i;if(s.value < m.value) {if(i < mindex) continue;left.push(s);var rindex = right.indexOf(s);right.splice(rindex, 1);sindex = left.length - 1;f.move.push({rect: s.rect,index: sindex + index});var movearr = middle.concat(right);for(var j=0;j<rindex+middle.length;j++) {f.move.push({rect: movearr[j].rect,index: sindex + index + j + 1});}}else if(s.value > m.value) {if(i > mindex) continue;var lindex = left.indexOf(s); left.splice(lindex, 1);right.unshift(s);sindex = left.length + middle.length;f.move.push({rect: s.rect,index: sindex + index});var movearr = left.concat(middle);for(var j=lindex;j<movearr.length;j++) { f.move.push({rect: movearr[j].rect,index: index + j});}}else if(i != mindex) {if(i < mindex) {var lindex = left.indexOf(s);left.splice(lindex, 1);middle.unshift(s);sindex = left.length;f.move.push({rect: s.rect,index: sindex + index});for(var j=lindex;j<left.length;j++) {f.move.push({rect: left[j].rect,index: index + j});}}if(i > mindex) {var rindex = right.indexOf(s);right.splice(right.indexOf(s), 1);middle.push(s);sindex = left.length + middle.length - 1;f.move.push({rect: s.rect,index: sindex + index});for(var j=0;j<rindex;j++) {f.move.push({rect: right[j].rect,index: sindex + index + j + 1});}} }if(f.move.length) self.frames.push(f);}return sort(left, oldleft, middle.concat(right, oldrigth||[])).concat(middle, sort(right, (oldleft||[]).concat(left, middle)));} var result = sort(arr); this.play(function(){callback && callback(result);});return result;}//直接插入排序//將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。 jmSort.prototype.straightInsertionSort = function(arr, dk, callback) {if(typeof arr == 'function') {callback = arr;arr= null;}if(typeof dk == 'function') {callback = dk;dk= 0;}arr = arr || this.source;dk = dk || 1;//拷貝一份var result = arr.slice(0);var self = this;for(var i=dk;i<result.length;i++) {var k = i;var j = k - dk;while(j>=0) {var v = result[k];var pre = result[j];this.frames.push({sels: [[v.rect], [pre.rect]]});if(v.value < pre.value) {result[j] = v;result[k] = pre;v.index = j;pre.index = k;this.frames.push({move: [{rect: pre.rect,index:k}, {rect:v.rect,index:j}]});k = j;j -= dk;}else {break;}} }callback && callback(result);return result; }//希爾排序//先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。 jmSort.prototype.shellSort = function(arr, callback) {if(typeof arr == 'function') {callback = arr;arr = null;}arr = arr || this.source;var dk = Math.floor(arr.length / 2);var result = arr;while(dk >= 1) {result = this.straightInsertionSort(result, dk);dk = Math.floor(dk / 2);}this.play(function(){callback && callback(result);});return result;}//簡單選擇排序//在要排序的一組數中，選出最小（或者最大）的一個數與第1個位置的數交換；然后在剩下的數當中再找最小（或者最大）的與第2個位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最后一個數）比較為止。 jmSort.prototype.simpleSelectionSort = function(arr, callback) {if(typeof arr == 'function') {callback = arr;arr = null;}arr = arr || this.source.slice(0);for(var i=0;i<arr.length-1;i++) {var min = arr[i];var minindex = i;for(var j=i+1;j<arr.length;j++) {if(min.value > arr[j].value) {min = arr[j];minindex = j;}//this.frames.push({sels:[[min.rect], [arr[j].rect]]}); }if(minindex != i) {this.frames.push({sels:[[min.rect], [arr[i].rect]]});this.frames.push({move: [{rect: min.rect, index: i}, {rect: arr[i].rect, index: minindex}]});arr[minindex] = arr[i];arr[i] = min;} }this.play(function(){callback && callback(arr);});return arr;}//二元選擇排序//簡單選擇排序，每趟循環只能確定一個元素排序后的定位。我們可以考慮改進為每趟循環確定兩個元素（當前趟最大和最小記錄）的位置,從而減少排序所需的循環次數。改進后對n個數據進行排序，最多只需進行[n/2]趟循環即可 jmSort.prototype.selection2Sort = function(arr, callback) {if(typeof arr == 'function') {callback = arr;arr = null;}arr = arr || this.source.slice(0);var index = -1;var self = this;var end = Math.floor(arr.length / 2);for(var i=0;i<end;i++) {//取最小值和最大值var min = arr[i];var max = arr[i];var minindex = i;var maxindex = i;for(var j=i+1;j<arr.length-i;j++) {if(min.value > arr[j].value) {min = arr[j];minindex = j;}if(max.value <= arr[j].value) {max = arr[j];maxindex = j;}}var maxpos = j - 1;this.frames.push({sels:[[min.rect, arr[i].rect], [max.rect, arr[maxpos].rect]]});if(minindex != i) { this.frames.push({move: [{rect: min.rect, index: i}, {rect: arr[i].rect, index: minindex}]});arr[minindex] = arr[i];arr[i] = min;//如果最大值是當前起始值，則它被換到最小值位置上了//需要重新改變最大值的索引為找到的最小值的索引if(maxindex == i) {maxindex = minindex;}}if(maxindex != maxpos) { this.frames.push({move: [{rect: max.rect, index: maxpos}, {rect: arr[maxpos].rect, index: maxindex}]});arr[maxindex] = arr[maxpos];arr[maxpos] = min;} }this.play(function(){callback && callback(arr);});return arr;}//冒泡排序//在要排序的一組數中，對當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換。 jmSort.prototype.bubbleSort = function(arr, callback) {if(typeof arr == 'function') {callback = arr;arr = null;}arr = arr || this.source.slice(0);var i = arr.length - 1;while(i > 0) {var pos = 0;for(var j=0;j<i;j++) {this.frames.push({sels: [[arr[j].rect],[arr[j+1].rect]]});if(arr[j].value > arr[j+1].value) {pos = j;var tmp=arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;this.frames.push({move: [{rect: tmp.rect,index: arr.indexOf(tmp)},{rect: arr[j].rect,index: arr.indexOf(arr[j])}]});}}i=pos;}this.play(function(){callback && callback(arr);});}$(function(){//開始var sort = new jmSort();sort.init();sort.selection2Sort(function(ret){console.log(ret);}); $('#btn_quick').click(function(){sort.reset();sort.quickSort(null,null,null,function(ret) {this.datumLine.visible = false;this.selectRect(ret);console.log(ret);}); return false;});$('#btn_straightinsertion').click(function(){sort.reset();sort.straightInsertionSort(function(result){sort.play();console.log(result);});return false; });$('#btn_shell').click(function(){sort.reset();sort.shellSort();return false; });$('#btn_simpleselection').click(function(){sort.reset();sort.simpleSelectionSort(); return false;});$('#btn_simpleselection2').click(function(){sort.reset();sort.selection2Sort();return false; });$('#btn_bubble').click(function(){sort.reset();sort.bubbleSort();return false;});});</script> </html>?
轉載于:https://www.cnblogs.com/jiamao/p/4679320.html
總結
以上是生活随笔為你收集整理的JS写的排序算法演示的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [SSH] Eclipse+Struts
- 下一篇： 重构alert，confirm