JS六种排序算法
diamond280
8年前
<p>// 冒泡排序</p> <p>// 循环的最大值从length递减</p> <p>// 基本就是每次循环只能排好最后一个 然后递减到第一个</p> <pre> <code class="language-javascript">function bubbleSort(){ var changedData = new Array(); var index = 0; console.log("冒泡调用"); for (var j = a.length; j >0 ; j--) { for (var i = 0; i < j; i++) { if(a[i]>a[i+1]){ var z = 0; z = a[i+1]; a[i+1] = a[i]; a[i] = z; } changedData[index] = a.toString(); index++; }//one }//two showDateChange(changedData); }</code></pre> <p>// 选择排序</p> <p>// 外循环 j选取当前元素 到length-1</p> <p>// 内循环 j+1开始 到length 逐个比较出最小值min</p> <p>// 交换 min 和 a[j]</p> <pre> <code class="language-javascript">function selectionSort(){ var changedData = new Array(); var index = 0; console.log("选择调用"); for (var j = 0; j < a.length-1; j++) { var min = a[j]; var minIndex = j; for (var i = j+1; i < a.length; i++) { if(a[i] < min) { min = a[i]; minIndex = i; } }//one a[minIndex] = a[j]; a[j] = min; // changedData[index] = a.toString(); index++; }//two showDateChange(changedData); }</code></pre> <p>// 插入排序</p> <p>// 从下标1开始 往后选择直到最后</p> <p>// 每个选中的和他前面的所有比较</p> <p>// 直到找到比他小的 排在他后面</p> <p>// 相当于从1开始 每次都排好之前的i+1个 直到length</p> <p>// 和冒泡相反</p> <pre> <code class="language-javascript">function insertionSort(){ var changedData = new Array(); var index = 0; console.log("插入排序"); for (var j = 1; j < a.length; j++) { var now = a[j]; var i = j - 1; while(i>=0 && now<a[i]){ // 向后移数组 a[i+1] = a[i]; i--; }//one a[i+1] = now; changedData[index] = a.toString(); index++; }//two showDateChange(changedData); }</code></pre> <p>// 希尔排序</p> <p>// 间隔改变的插入排序</p> <p>// 传统插入排序 比较前面的相邻对象</p> <p>// 希尔排序比较前面的第h个对象 直到h间隔不存在更改</p> <p>// 改变h 直到 h=1</p> <pre> <code class="language-javascript">function shellSort(){ var changedData = new Array(); var index = 0; console.log("希尔排序"); var N = a.length; var h = 1; if (h < N/3) { h = h*3 + 1;//设置间隔 } while(h > 0){ for (var j = h; j < a.length; j++) { for (var i = j;i >= h && a[i] < a[i-h]; i -= h) { var z; z = a[i]; a[i] = a[i-h]; a[i-h] = z; // changedData[index] = a.toString(); index++; } } h = (h-1)/3;//改变间隔 } showDateChange(changedData); }</code></pre> <p>// 归并排序</p> <p>// 数据分为 step为间隔的小数组</p> <p>// 将小数组排序 step变大 直到为1/2个数组</p> <p>// 将前后两个已排序的数组 再排序</p> <pre> <code class="language-javascript">function mergeSort(arr){ var changedData = new Array(); console.log("归并排序"); if (arr.length < 2) { return; } var step = 1; var left; var right; while(step < arr.length){ left = 0; right = step; while(right + step <= arr.length){ mergeArrays(arr,left,left+step,right,right+step); left = right + step; right = left + step; } if (right < arr.length) { mergeArrays(arr,left,left+step,right,arr.length); } step *= 2; } function mergeArrays(arr,startLeft,stopLeft,startRight,stopRight){ var leftArray = new Array(stopLeft - startLeft +1); var rightArray = new Array(stopRight - startRight +1); k = startRight; for (var i = 0; i < rightArray.length-1; i++) { rightArray[i] = arr[k]; k++; } k = startLeft; for (var i = 0; i < leftArray.length-1; i++) { leftArray[i] = arr[k]; k++; } rightArray[rightArray.length-1] = Infinity; leftArray[leftArray.length-1] = Infinity; var m = 0; var n = 0; for (var k = startLeft; k < stopRight; k++) { if (leftArray[m] <= rightArray[n]) { arr[k] = leftArray[m]; m++; }else{ arr[k] = rightArray[n]; n++; } } arr += "";//转化为字符串 changedData.push(arr); } showDateChange(changedData); }</code></pre> <p>// 快速排序</p> <p>// 没实现可视化排序</p> <pre> <code class="language-javascript">function quickSort(){ console.log("快速排序"); function qSort(list){ if (list.length == 0) { return list; } // 选取基数 var pivotIndex = Math.floor(list.length/2); var pivot = list.splice(pivotIndex,1)[0]; var left = []; var right = []; for (var i = 0; i < list.length; i++) { if (list[i] > pivot) { right.push(list[i]); }else{ left.push(list[i]); } } // 递归 更换基数 并且排序其左右 return qSort(left).concat([pivot],qSort(right)); } a = qSort(a); showDate(); }</code></pre> <p> </p> <p>来自:https://segmentfault.com/a/1190000007013104</p> <p> </p>