js排序篇----快速排序,选择排序,冒泡排序,希尔排序

能上代码的尽量不解释,用代码去反向理解文字这是我推崇的,所以请把重点放在代码理解上.

真实开发中 会直接用方法 sort 如下:

let arr = [2,34,242,12,3,2,23,3];

arr.sort((a,b) => a-b);//正序 等同于 arr.sort();
console.log(arr);// [2, 2, 3, 3, 12, 23, 34, 242]


arr.sort((a,b) => b-a);//倒序 等同于 arr.sort().reverse()
console.log(arr); //[242, 34, 23, 12, 3, 3, 2, 2]

但是对于数据量大的处理还是需要通过算法完成.

快速排序

"快速排序"的思想很简单，整个排序过程只需要三步

1. 在数据集之中，选择一个元素作为"基准"（pivot）。
2. 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3. 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

举个例子:(红色为基准)
   数据值:{85, 24, 63, 45, 17, 31, 96, 50}

   第一步:{85, 24, 63, 45, 17, 31, 96, 50}  #45为基准

   第二步:{24,17,31} 45 {85,63,96,50}  #左边为小于45集合 右边为大于45集合

   第三步:17 {24,31} 45 {50} 63 {85,96} #左右集合继续重复一,二步骤

   第四步:17 24 {31} 45 50 63 85 {96} #同上

   第五步:17 24 31 45 50 63 85 96 #当左右集合只有一个元素即可返回

具体代码实现如下:

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 pivot = arr[pivotIndex];
　　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)); //递归 左右集合继续对比 到返回后的数组合并

};

console.log(quickSort([85, 24, 63, 45, 17, 31, 96, 50]));
//(8) [17, 24, 31, 45, 50, 63, 85, 96]

选择排序

算法步骤:

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

举个例子:(红色为最小值)
   数据值:{85, 24, 63, 45, 17, 31, 96, 50}

   第一步: 遍历索引 从0开始 (下面为索引为0的小步骤)

1. {85, 24, 63, 45, 17, 31, 96, 50}  //默认为85 依次从左往右对比
2. {85, 24, 63, 45, 17, 31, 96, 50}  //24小于85 变为最小值
3. {85, 24, 63, 45, 17, 31, 96, 50}  //63大于24 最小值没变
4. {85, 24, 63, 45, 17, 31, 96, 50}  //45大于24 最小值没变
5. {85, 24, 63, 45, 17, 31, 96, 50}  //17小于24 变为最小值
6. {85, 24, 63, 45, 17, 31, 96, 50}  //31大于17 最小值没变
7. 以此类推 所有元素均排序完毕 , 选择出最小值为17与索引为0的85互换位置 ,数组处理后为:{17, 24, 63, 45, 85, 31, 96, 50}

   第二步:遍历索引从1开始(重复第一步骤)

   .........

  第N步后:直到所有元素均排序完毕

 具体代码实现如下:

 var selectionSort = function(arr) {

        var len = arr.length,minIndex, temp;
        for (var i = 0; i < len - 1; i++) {
            minIndex = i;
            for (var j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                    minIndex = j;                 // 将最小数的索引保存
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    };

    console.log(selectionSort([85, 24, 63, 45, 17, 31, 96, 50]));
    //[17, 24, 31, 45, 50, 63, 85, 96]

冒泡排序     

算法步骤: 

1. 依次比较相邻的两个数，如果不符合排序规则，则调换两个数的位置。这样一遍比较下来，能够保证最大（或最小）的数排在最后一位
2. 再对最后一位以外的数组，重复前面的过程，直至全部排序完成。

继续举例: (红色为最大值)   

 数据值:{85, 24, 63, 45, 17, 31, 96, 50}

   第一步: 遍历索引 从0开始 (下面为索引为0的小步骤)

1. {85, 24, 63, 45, 17, 31, 96, 50}  //默认为85 依次从左往右对比
2. {24, 85, 63, 45, 17, 31, 96, 50}  //24小于85 互换位置
3. {24, 63, 85, 45, 17, 31, 96, 50}  //63小于85 互换位置
4. {24, 63, 45, 85, 17, 31, 96, 50}  //45小于85 互换位置
5. {24, 63, 45,  17,85, 31, 96, 50}  //17小于85 互换位置
6. {24, 63, 45,  17,31,85, 96, 50}   //96大于85 不换位置 
7. {24, 63, 45,  17,31,85, 50, 96}   //96大于50 互换位置 第一次遍历结束

   第二步:遍历索引 从0开始(重复第一步骤) 遍历次数<最大索引-1

   .........

  第N步后:遍历索引 从0开始  最大索引-n === 0 为止

 具体代码实现如下:

 var bubbleSort = function(arr) {
        var len = arr.length,i,j;
        for (i = 0; i < len - 1; i++){
            for (j = 0, j < len - 1 - i; j++){ //i位以外的数组，重复循环
                if (arr[j] > arr[j + 1]){
                    var temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    };
    console.log(bubbleSort([85, 24, 63, 45, 17, 31, 96, 50]));

希尔排序

算法步骤:

1. 按照实际需要设定一个步长（我们这里设定 fraction = arr.length / 2，即步长为 5）。这样就可以将数列分组，并对每个分组执行插入排序。所有分组都执行完插入排序，视为第一轮排序完成
2. 待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序

数据值:{85, 24, 63, 45, 17, 31, 96, 50}

   第一步: 计算步长= 8/2 = 4;即分割为4组
      {85, 24, 63, 45, 17, 31, 96, 50}
      85 ************17***********
      ****24************31********

      ********63***********96*****
     *************45***********50

     排序:   

     17************85*************
     ****24************31*********

      *******63************96*****
     ***********45*************50

    排序后:

    {17, 24, 63, 45, 85, 31, 96, 50}

   第二步:计算步长= 上次步长/2 = 5/2 = 2 ;即分割为2组
  {17, 24, 63, 45, 85, 31, 96, 50}
  17******63****85****96*****

  ****24*****45*****31*****50

  排序后:{17,24,63,31,85,45,96,50}

  第三步:计算步长= 上次步长/2 = 2/2 = 1 ;即分割为1组
  排序后:{17, 24, 31, 45, 50, 63, 85, 96}//结束

 具体代码实现如下:

var shellSort = function(list) {
        var gap = Math.floor( list.length / 2 );//第一次计算步长

        while( gap > 0 ) {//步长为0 不再执行

            for( i = gap; i < list.length; i++ ) {

                var temp = list[i];

                for( j = i; j >= gap && list[j - gap] > temp; j -= gap ) {

                    list[j] = list[j - gap];
                }

                list[j] = temp;

            }

            gap = Math.floor( gap / 2 );//向下取整 重新计算步长
        }


        return list;
    }