js实现各种排序算法
一、冒泡排序算法
alert(bubbleSort([1,2,32,23,42,54,65,75,65,32])); function bubbleSort(nums){ var i, j,temp; for(i=0;i<nums.length-1;i++){ for(j=0;j<=nums.length-i-1;j++){ if(nums[j+1]<nums[j]){ temp = nums[j+1]; nums[j+1] = nums[j]; nums[j] = temp; } } } return nums; }
从小到大排列，效率 O（n2）,适用于排序小列表。
二、选择排序算法
alert(SelectSortArray([1,2,32,23,42,54,65,75,65,32])); function SelectSortArray(nums) { var min_index; for(var i=0;i<n-1;i++) { min_index=i; for(var j=i+1;j<n;j++)//每次扫描选择最小项 if(nums[j]<nums[min_index]) min_index=j; if(min_index!=i)//找到最小项交换，即将这一项移到列表中的正确位置 { var temp; temp=nums[i]; nums[i]=nums[min_index]; nums[min_index]=temp; } } return nums; }
从小到大排列，效率O（n2），适用于排序小的列表。
三、插入排序算法
alert(InsertSortArray([1,2,32,23,42,54,65,75,65,32])); function InsertSortArray(nums) { var n = nums.length for(var i=1;i<n;i++)//循环从第二个数组元素开始，因为nums[0]作为最初已排序部分 { var temp=nums[i];//temp标记为未排序第一个元素 var j=i-1; while (j>=0 && nums[j]>temp)/*将temp与已排序元素从小到大比较，寻找temp应插入的位置*/ { nums[j+1]=nums[j]; j--; } nums[j+1]=temp; } return nums; }
从小到大排列，最佳效率O（n）；最糟效率O（n2）与冒泡、选择相同，适用于排序小列表
若列表基本有序，则插入排序比冒泡、选择更有效率。
四、壳（Shell）排序——缩小增量排序
alert(ShellSortArray([1,2,32,23,42,54,65,75,65,32])); function ShellSortArray(nums) { var n = nums.length for(var incr=3;incr<0;incr--)//增量递减，以增量3，2，1为例 { for(var L=0;L<(n-1)/incr;L++)//重复分成的每个子列表 { for(var i=L+incr;i<n;i+=incr)//对每个子列表应用插入排序 { var temp=nums[i]; var j=i-incr; while(j>=0&&nums[j]>temp) { arr[j+incr]=nums[j]; j-=incr; } nums[j+incr]=temp; } } } return nums; }
适用于排序小列表。
效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。
壳（Shell）排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。
五、归并排序
function merge(arr, p, q, r) { var crr = []; var a = p, b = q + 1, k = p; while(a <= q && b <= r) { if(arr[a] <= arr[b]) { crr.push(arr[a]); a ++; } else { crr.push(arr[b]); b ++; } k ++; } if(a === q + 1) { while(b <= r) { crr.push(arr[b]); b ++; } } else { while(a <= q) { crr.push(arr[a]); a ++; } } var i = 0, cl = crr.length; while(i < cl) { arr[p++] = crr[i++]; } return arr; } function mergesort(arr, low, high) { if(low === high) { return arr; } else if(high - low === 1) { if(arr[low] > arr[high]) { var temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; } return arr; } else { var mid = parseInt((low+high)/2); arr = mergesort(arr, low, mid); arr = mergesort(arr, mid+1, high); return merge(arr, low, mid, high); } } // 示例 var nums = [88, 32, 22, 32, 87, 88]; alert(mergesort(nums, 0, nums.length - 1));
效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异。
适用于排序大列表，基于分治法。
第六、快速排序
快速排序的算法思想：选定一个枢纽元素，对待排序序列进行分割，分割之后的序列一个部分小于枢纽元素，一个部分大于枢纽元素，再对这两个分割好的子序列进行上述的过程。
var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { //从低到高 left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right)); }; var nums = [88, 32, 22, 32, 87, 88]; alert(quickSort(nums));
平均效率O（nlogn），适用于排序大列表。
第七、堆排序
最大堆：后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字，此时位于堆顶的节点的关键字是整个序列中最大的。
思想：
(1)令i=l,并令temp＝
kl
;
(2)计算i的左孩子j=2i+1;
(3)若j<＝n－1，则转(4),否则转(6);
(4)比较kj和kj+1,若kj+1>kj,则令j＝j＋1，否则j不变；
(5)比较temp和kj，若kj>temp，则令ki等于kj，并令i=j,j=2i+1,并转(3),否则转(6)
(6)令ki等于temp，结束。
-----------------------------------------Code---------------------------
js实现的堆排序/** * 堆排序 * @param items 数组 * @return 排序后的数组 */ function heapSort(items) { items = array2heap(items); //将数组转化为堆 for(var i = items.length - 1; i >= 0; i--) { items = swap(items, 0, i); //将根和位置i的数据交换(用于将最大值放在最后面) items = moveDown(items, 0, i - 1); //数据交换后恢复堆的属性 } return items; } /** * 将数组转换为堆 * @param items 数组 * @return 堆 */ function array2heap(items) { for(var i = Math.ceil(items.length / 2) - 1; i >= 0; i--) { items = moveDown(items, i, items.length - 1); //转换为堆属性 } return items; } /** * 转换为堆 * @param items 数组 * @param first 第一个元素 * @param last 最后一个元素 * @return 堆 */ function moveDown(items, first, last) { var largest = 2 * first + 1; while(largest <= last) { if(largest < last && items[largest] < items[largest + 1]) { largest++; } if(items[first] < items[largest]) { items = swap(items, first, largest); // 交换数据 first = largest; //往下移 largest = 2 * first + 1; } else { largest = last + 1; //跳出循环 } } return items; } /** * 交换数据 * @param items 数组 * @param index1 索引1 * @param index2 索引2 * @return 数据交换后的数组 */ function swap(items, index1, index2) { var tmp = items[index1]; items[index1] = items[index2]; items[index2] = tmp; return items; } var nums = [88, 32, 22, 32, 87, 88]; alert(heapSort(nums ));
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。
堆排序与直接插入排序的区别:
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
