JS的排序算法实现

最近在准备找工作,疯狂学习。作为一个前端程序员,虽然日常工作中,一些东西不是很必要的,但是得知道,算作是程序员的基本修养吧。

其中之一当然就应该是算法了,从C语言开始,我们就知道 程序 = 代码 + 算法 无奈以前一直在琢磨着实现的问题,现在才来得及回来亡羊补牢一下。

说到算法,最最基础的就是排序算法。

而排序算法,最最基础的,就是三个算法。

  • 冒泡排序(Bubble Sort)
  • 插入排序(Insert Sort)
  • 快速排序(Quick Sort)

1. 冒泡排序

冒泡排序的基本思路是

取第一个待排元素,跟后一个待排元素相比。

(1) [当前待排元素, 待排元素, ……]

若当前待排元素比后一个待排元素大,那么它们两个交换位置。

(2) [待排元素, 当前待排元素, ……]

然后接着跟后面的待排元素重复(1)(2)步骤,第一轮过后,有一个所有待排元素中最大的元素,会被移动到最末尾。

就像这个最大的泡泡(最大待排元素)从水里冒出来了(移动到了最末尾),所以形象的成为冒泡排序。

然后后面就容易了,再取第一个待排元素为当前待排元素,一直跟后面一个待排元素比较,判断大小然后交换位置,比较到倒数第二个数(因为最后一个数已经是最大的了,就不用再跟它比了。)

这时候就取出了第二大的元素。

然后就是第三轮比较,比较到倒数第三个元素,然后第三大的元素会到列表的倒数第三的位置。

……

function bubbleSort(list){
        console.log(`
          目标数组 ${list}
          `);
        for (let i = 0, time = 0; i < list.length - 1; i++) {
          //第一轮排好最大的那一个数,第二轮排好第二大的数,以此类推
          for (let j = 0; j < list.length - 1 - i; j++) {
            time++;
            var before = list[j];
            var after = list[j+1]
            //i代表已经排好了的数,j就不用循环到底,比如i=1就是找到了最大的数,那最后一个就是最大的数,那就没必要去比较做后一个
            if (list[j] > list[j+1]) {
              //如果前面的数大于后面的,那就把它换个位置。以便下一个j选择到这个大的数继续往下找
              [list[j], list[j+1]] = [list[j+1], list[j]];
            }
            console.log(`
              第 ${time} 次:
              比较: ${before}${after}
              结果: ${list}`
            );
          }
        }
      }

bubble sort.png

2. 插入排序

插入排序是冒泡排序的一个改进,上面的冒泡排序在调换位置的时候,没有考虑到换到前面去的元素的排列。

插入排序在冒泡排序的调换位置的步骤里面,把调换到前面去的(也就是比较的时候较小的那一个数)元素,与前面的待排元素进行比较排序。与前面的待排元素进行比较排序。这样子确保了 插入排序的步骤中,当前元素之前的元素,都是排好的。

当前元素之前的元素排列好的好处是,只要调换位置过来的较小的那个元素,在往前比较的时候,遇到了比自己小的元素,就可以停下了。因为在那个比自己小的元素后面,都是比他小的元素。因为插入排序中当前元素前面的元素都是排好序的。

function insertSort(list) {
        console.log(`
          目标数组 ${list}
          `);
        for (let i = 1, time = 0; i < list.length; i++) {
          for (let j = i ; j > 0; j--) {
            time++;
            var before = list[j];
            var after = list[j-1]
            if (list[j] < list[j-1]) {
              [list[j-1], list[j]] = [list[j], list[j-1]];
              console.log(`
                第 ${time} 次:
                比较: ${before}${after}
                结果: ${list}`
              );
            }
            else {
              console.log(`
                第 ${time} 次:
                比较: ${before}${after}
                结果: ${list}`
              );
              break;
            }
          }
        }
      }

insert sort.png

3. 快速排序

快速排序的思想是,随机从待排元素中取出一个元素,所有比它大的元素,放到一个数组里面。所有比他小的元素,放到另一个数组里面。

再从这两个数组里面,各自取出一个元素,所有比它大的元素,放到一个数组里面。所有比它小的元素,放到一个数组里面。

不断的分下去。直到小数组里面只有一个元素或者没有元素。

然后就开始从最小的 存放小数组的数组开始 拼接在一起

带排序数组 分为 第三小数组 + 第三大数组

第三小数组 分为 第二小数组 + 第一小数组

第三大数组 分为 第二大数组 + 第一大数组

最小数组 + 第二小数组 + 第三小数组 + 第三大数组 + 第二大数组 + 第一大数组 = 排序好的数组

var quickTime = 0;
      function quickSort(list, info){
        quickTime++;
        console.log(`
          第 ${quickTime} 次
          处理 ${info} 数组
          数组为 ${list}
          `);
        if (list.length === 1 || list.length === 0) {
          console.log(`
            返回数组 ${list}
            数组长度 ${list.length}
            `);
          return list;
        }
        else {
          let middleIndex = Math.ceil(list.length / 2);
          let before = [];
          let after = [];
          for (let i = 0; i < list.length; i++) {
            if (list[i] < list[middleIndex]) {
              before.push(list[i]);
            }
            else if(list[i] > list[middleIndex]) {
              after.push(list[i]);
            }
          }
          console.log(`
            基准值: ${list[middleIndex]}
            小于基准值: ${before}
            大于基准值: ${after}
            `);
          return quickSort(before, "小于基准值").concat(list[middleIndex]).concat(quickSort(after, "大于基准值"));
        }
      }

quick sort1.png

quick sort2.png