- var sort = {
- debug:function(str){
- if(window.console && window.console.log){
- console.log(str);
- }
- },
- swap:function(arr,index1,index2){//数组数据交换
- var temp = arr[index1];
- arr[index1] = arr[index2];
- arr[index2] = temp;
- },
- bubbleSort:function(arr){ //冒泡排序
- this.debug("冒泡排序before:"+arr);
- var len = arr.length;
- for(var outer = 0;outer<len-1;outer++){//比较的轮数
- for(var inner = 0;inner<len-outer-1;inner++){//每轮比较的次数
- if(arr[inner] > arr[inner+1] ){
- this.swap(arr,inner,inner+1)
- }
- }
- this.debug("第"+(outer+1)+"轮后:"+arr);
- }
- this.debug("冒泡排序after:"+arr);
- },
- selectionSort:function(arr){//选择排序
- this.debug("选择排序before:"+arr);
- var min,len = arr.length;
- for (var outer = 0; outer < len -1; outer++) {
- min = outer;
- // 比较最小项目和第outer项之后的剩余数组项, 以寻找更小项
- for (var inner = outer+1; inner < len; inner++) {
- if (arr[inner] <arr[min]) {
- min = inner;
- this.debug("min--"+min);
- }
- }
- this.swap(arr,outer, min);
- this.debug("第"+(outer+1)+"轮后:"+arr);
- }
- this.debug("选择排序after:"+arr);
- },
- insertionSort:function(arr){//插入排序
- this.debug("插入排序before:"+arr);
- var temp,inner,len = arr.length;
- for (var outer = 1; outer < len ; outer++) {
- temp = arr[outer];
- inner = outer;
- while(inner>0 && arr[inner-1] >= temp){
- arr[inner] = arr[inner-1];
- --inner;
- }
- arr[inner] = temp;
- }
- this.debug("插入排序after:"+arr);
- },
- shellSort:function(arr){//希尔排序
- this.debug("希尔排序before:"+arr);
- var gaps = [5,3,1],
- temp;
- for(var g = 0;g <gaps.length; g++){
- for(var i = gaps[g];i<arr.length;i++){
- temp = arr[i];
- for(var j = i;j >= gaps[g] && arr[j-gaps[g]] > temp;j -= gaps[g]){
- arr[j] = arr[j-gaps[g]];
- }
- arr[j] = temp;
- }
- }
- this.debug("希尔排序after:"+arr);
- },
- shellSortDynamic:function(arr){//动态计算间隔序列的希尔排序
- this.debug("动态计算间隔序列的希尔排序before:"+arr);
- var N = arr.length,
- h = 1;
- while(h < N/3){
- h = 3*h +1;
- }
- while(h >= 1){
- for(var i = h;i < N;i++){
- for(var j = i;j >= h && arr[j] < arr[j-h];j -= h){
- this.swap(arr,j,j-h);
- }
- }
- h = (h-1)/3;
- }
- this.debug("动态计算间隔序列的希尔排序after:"+arr);
- },
- mergeSort:function(arr){//归并排序
- this.debug("归并排序before:"+arr);
- var len = arr.length,
- step = 1,
- left,
- right;
- var mergeArray = function(arr,startLeft,stopLeft,startRight,stopRight){
- var rightArr = new Array(stopRight - startRight +1),
- leftArr = new Array(stopLeft - startLeft +1),
- k = startRight,
- m = 0,
- n = 0;
- for(var i = 0;i < (rightArr.length - 1); ++i){
- rightArr[i] = arr[k];
- ++k;
- }
- k = startLeft;
- for(var i = 0;i < (leftArr.length - 1); ++i){
- leftArr[i] = arr[k];
- ++k;
- }
- rightArr[rightArr.length-1] = Infinity; //哨兵值
- leftArr[leftArr.length-1] = Infinity; //哨兵值
- for(var k = startLeft;k < stopRight; ++k){
- if(leftArr[m] <=rightArr[n]){
- arr[k] = leftArr[m];
- m++;
- }else{
- arr[k] = rightArr[n];
- n++
- }
- }
- }
- if(len < 2){
- return;
- }
- while(step < len){
- left = 0;
- right = step;
- while(right + step <= len){
- mergeArray(arr,left,left+step,right,right+step);
- left = right + step;
- right = left + step;
- }
- if(right < len){
- mergeArray(arr,left,left+step,right,len);
- }
- step *= 2;
- }
- this.debug("归并排序after:"+arr);
- },
- quickSort:function(arr){//快速排序
- this.debug("快速排序before:"+arr);
- var _quickSort = function(arr){
- var len = arr.length,
- lesser = [],
- greater = [],
- pivot,
- meCall = arguments.callee;
- if(len == 0){
- return [];
- }
- pivot = arr[0];
- for(var i = 1;i < len; i++){
- if(arr[i] < pivot ){
- lesser.push(arr[i])
- }else{
- greater.push(arr[i])
- }
- }
- return meCall(lesser).concat(pivot,meCall(greater));
- }
- this.debug("快速排序after:"+_quickSort(arr));
- return _quickSort(arr);
- }
- }
- var search = {
- linearSearch:function(arr,data){//线性查找
- for(var i = 0;i<arr.length;i++){
- if(arr[i] == data){
- return i;
- }
- }
- return -1;
- },
- binarySearch:function(arr,data){//二分查找 适用于已排好序的线性结构
- var lowerBound = 0,
- upperBound = arr.length - 1,
- mid;
- while(lowerBound <= upperBound){
- mid = Math.floor((lowerBound+upperBound)/2);
- if(arr[mid] < data){
- lowerBound = mid + 1;
- }else if(arr[mid] > data){
- upperBound = mid - 1;
- }else{
- return mid;
- }
- return -1;
- }
- }
- }
- var tempArr = [3,6,4,2,11,10,5];
- //sort.bubbleSort(tempArr);
- //sort.selectionSort(tempArr);
- //sort.insertionSort(tempArr);
- //sort.shellSort(tempArr);
- //sort.shellSortDynamic(tempArr);
- //sort.mergeSort(tempArr);
- sort.quickSort(tempArr);
- //该片段来自于http://www.codesnippet.cn/detail/2811201514126.html
来源: http://www.codesnippet.cn/detail/2811201514126.html