算法

【原创】
以下是自己写的某些算法的JS实现

快排 （一）

      function quickSort(arrData) {
                var arr = arrData.slice();
                var left = 0,
                    right = arr.length - 1
                if (right <= left) return arr;
                var pivot = arr[0]
                while (left < right) {
                    while (arr[right] >= pivot && left < right) {
                        right--
                    }
                    arr[left] = arr[right];
                    if(left<right){
                        left++;
                    }
                    while (arr[left] < pivot && left < right) {
                        left++
                    }
                    arr[right] = arr[left]
                    right--;
                }
                arr[left] = pivot;
                let leftArr = arr.slice(0, left);
                let rightArr = arr.slice(left + 1);
                return quickSort(leftArr).concat(pivot).concat(quickSort(rightArr));                 
            }

快排（二）

function quickSort(arrData,left,right) {
   var arr = arrData;
   left = left||0,
       right = right||arr.length - 1;
   var lastRight = right;
   var lastLeft = left;

   if (right < 1) return [];
   var pivot = arr[left];
   while (left < right) {
       while (arr[right] >= pivot && left < right) {
           right--
       }
       
       if(left<right){
           arr[left] = arr[right];
           left++;
       }
       while (arr[left] < pivot && left < right) {
           left++
       }
       arr[right] = arr[left]
       right--;
   }
   arr[left] = pivot;
   let rightArr,leftArr;
   if(left + 1 < lastRight){
       rightArr = quickSort(arr,left + 1,lastRight);
   }else if(left + 1 === lastRight){
       rightArr = [arr[left+1]]
   }else{
       rightArr = [];
   }
   if(lastLeft < left-1){
       leftArr = quickSort(arr,lastLeft,left-1)
   }else if(lastLeft === left-1){
       leftArr = [arr[lastLeft]]
   }else{
       leftArr = [];
   }
   return [...leftArr,(pivot),...rightArr];                 
}

希尔排序

 function hellSort(arr){
    let len = arr.length;
    let gap = Math.floor(len/2),i = 0,j=0,k;
    while(gap >= 1){
        i = 0;
        while(i<gap){
            j=i;
            while(j<len){
                k=j;
                while(arr[k] > arr[k+gap] && k+gap<len && k>=0){
                    [arr[k],arr[k+gap]] = [arr[k+gap],arr[k]];
                    k -= gap;
                }
                j += gap;

            };
            i++;
        }
        gap = Math.floor(gap/2);
    }
    return arr;
}

插排

// 插入排序
function insertSort(arrData){
     let arr = arrData;
     let i=1,k;
     while(i<arr.length){
         
         k = i;
         let temp = arr[i];
         while(temp<arr[k-1] && k >= 1){             
            arr[k] = arr[k-1]
             k--;
         }
         arr[k] = temp;
         i++;
     }
     return arr;
}

二分插排

// 二分查找插入 插入排序的优化
function binaryInsert(arrData){
    var arr = arrData;
    let k,i=1,j; //从第二个位置开始
    while(i<arr.length){
        k = Math.floor(i/2);
        if(arr[i] < arr[k]){
            while(arr[i] < arr[k] && k>=0){
                k--;
            }
        }
        if(arr[i] > arr[k]){
            while(arr[i] > arr[k] && k<i){
                k++;
            }
        }
        
        j=i;
        let temp = arr[j];
        while(j>k && j>=1){
            arr[j] = arr[j-1] ;
            j--;
        }
        arr[j] = temp;
        i++;
    }
    return arr;
}

归并排序

function concatSort(arr){
    let gap = 1,i=0;
    let t = 2;
    let len = arr.length;
    while(gap < len){
        let resArr =[];
        i=0;
        while(i < len){
            let start1 = i;
            let end1 = Math.min(start1+gap-1, len-1);

            let start2 = Math.min(end1+1,len-1);
            let end2 =  Math.min(start2 + gap-1,len-1);

            if(end1 >= len-1){
                // 最后一个不成对出现，
                // 没有start2 不排序
                while(start1 <= end1 ){
                    resArr[i] = arr[start1++];
                    i++;
                }
            }else{
                // 成对的比较，拿出最小的，放到一个数组里面
                while(start1 <= end1 && start2 <= end2 ){
                    resArr[i] = arr[start1] <= arr[start2] ? arr[start1++]:arr[start2++];
                    i++;
                }
                while(start1 <= end1){
                    resArr[i] = arr[start1++];
                    i++;
                }
                while(start2<= end2){
                    resArr[i] = arr[start2++];
                    i++;
                }
            }

         }
         arr = resArr;
        gap*=t;
    }
    return arr;
}