Daily English - 2015/01/30 – 算法(排序)
(function () { /* 通排序 最快最简单的排序 */ var data = [100, 50, 75, 25, 1, 20, 90, 30, 80, 40, 60, 50], result = [], barrel = [], i, j, item; //初始化桶 m = 桶数 for (i = 0; i < 101; i++) { barrel[i] = 0; } //插入桶 n = 排序数的个数 for (i = 0; item = data[i]; i++) { barrel[item]++; } //遍历桶 m for (i = 0; i < barrel.length; i++) { //输出排序数 n if (barrel[i] !== 0) { for (j = 0; j < barrel[i]; j++) { result.push(i); } } } console.log(result.join(", ")); // O(m+n+m+n) = O(2*(m+n)) = O(M+N) }());
(function () { /* 冒泡排序 基本思想:每次比较两个相邻的元素,如果他们的顺序错误就把他们交换过来。 原理:每一趟只能确定将一个数归位。 */ var data = [100, 50, 75, 25, 1, 20, 90, 30, 80, 40, 60, 50], length = data.length - 1, inLength, i, j, vitem; for (i = 0; i < length; i++) { inLength = length - i; for (j = 0; j < inLength; j++) { if (data[j] > data[j + 1]) { vitem = data[j + 1]; data[j + 1] = data[j]; data[j] = vitem; } } } console.log(data.join(", ")); // O(N²) }());
(function () { /* 快排序 快排每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止。 每次交换是跳跃式的,总的比较和交换次数就少了。确定基准数两面相对其是正确的顺序。 基于“二分”思想 */ var data = [6, 9, 3, 7, 1, 5, 4, 8, 2, 3], quickSort = function (left, right) { var mid = data[left], i = left, j = right, vitem; if (left > right) { return; } while (i !== j) { while (data[j] >= mid && i < j) { j--; } while (data[i] <= mid && i < j) { i++; } if (i < j) { vitem = data[j]; data[j] = data[i]; data[i] = vitem; } } data[left] = data[i]; data[i] = mid; quickSort(left, i - 1); quickSort(i + 1, right); }; quickSort(0, data.length - 1); console.log(data.join(", ")); // O(NlogN) }());
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。