AitSchool

排序

对一序列对象根据某个关键字进行排序

算法优劣术语的说明

  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
  • 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
  • 内排序：所有排序操作都在内存中完成；
  • 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
  • 时间复杂度: 一个算法执行所耗费的时间。
  • 空间复杂度: 运行完一个程序所需内存的大小。

冒泡排序

冒泡排序，它重复地走过要排序的数列，一次比较两个元素，如果它们的顺序所悟就把它们交换过来，直到没有需要交换。这个算法名字的由来是因为，越小的元素会经由交换慢慢浮到数列的顶端。

file

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两。
  2. 对每一对相邻元素作以上同样的工作，从开始第一对到结尾最后一对，这样最后的元素会是最大数。
  3. 针对所有元素重复以上步骤，除了最后一个。
  4. 重复以上，直到排序结束。
{
    let arr = [5,4,3,2,1];
    // console.log(arr)
    for(var i = arr.length - 1; i > 0; i -- ) {
        for( var j = 0; j < i; j++){
            if(arr[j] > arr[j+1]) {
                var tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp
            }
            // console.log(arr)
        }
    }

    // > [5, 4, 3, 2, 1]
    // > [4, 5, 3, 2, 1]
    // > [4, 3, 5, 2, 1]
    // > [4, 3, 2, 5, 1]
    // > [4, 3, 2, 1, 5]
    // > [3, 4, 2, 1, 5]
    // > [3, 2, 4, 1, 5]
    // > [3, 2, 1, 4, 5]
    // > [2, 3, 1, 4, 5]
    // > [2, 1, 3, 4, 5]
    // > [1, 2, 3, 4, 5]
}

插入排序

构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置插入。在后面向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

file

  1. 从第一位元素开始，默认该元素认为已经被排序。
  2. 取出下一个元素，在已排序的元素序列中从后面向前面扫描。
  3. 如果已排序大于新元素，该元素移到下一位置。一直重复找到已排序小于或等于新元素的位置为止，将新元素插入到该元素后。
  4. 重复以上。
{
    let arr = [5,4,3,2,1];
    console.log(arr,'arr')
    for(let i = 1; i < arr.length; i++ ){
        let tmp = arr[i];
        for(let j = i; j >=0 ; j-- ){
            if( arr[j-1] > tmp){
                arr[j] = arr[j-1]
                // console.log(arr,'move')
            }else{
                arr[j] = tmp;
                // console.log(arr,'set')
                break // 结束当前 j 的 for 循环
            }
        }
    }

    // [5, 4, 3, 2, 1] "arr"
    // [5, 5, 3, 2, 1] "move"
    // [4, 5, 3, 2, 1] "set"
    // [4, 5, 5, 2, 1] "move"
    // [4, 4, 5, 2, 1] "move"
    // [3, 4, 5, 2, 1] "set"
    // [3, 4, 5, 5, 1] "move"
    // [3, 4, 4, 5, 1] "move"
    // [3, 3, 4, 5, 1] "move"
    // [2, 3, 4, 5, 1] "set"
    // [2, 3, 4, 5, 5] "move"
    // [2, 3, 4, 4, 5] "move"
    // [2, 3, 3, 4, 5] "move"
    // [2, 2, 3, 4, 5] "move"
    // [1, 2, 3, 4, 5] "set"
}

选择排序

首先在末排序序列中找到最小的元素，存放在排序序列的起始位置，然后再从剩余末排序元素中国年继续寻找最小的元素，放在已排序的末尾(或者说是再次选择序列中的初始位置）。

file

  1. 选择序列中最小的值和和序列中的第一位交换
  2. 从第二位开始的新序列，选择新序列中最小值，和新序列的第一位（原序列的第二位交换)；
  3. 重复以上，直到排序结束。
{
    let arr = [5,4,2,1,3];
    console.log(arr)
    for (let i = 0; i < arr.length - 1; i++) {
        let index = i;
        let tmp = arr[i];

        for (let j = i + 1; j < arr.length; j ++) {
            if(arr[j] < tmp){
                index = j;
                tmp = arr[j];
            }
        }

        arr[index] = arr[i];
        arr[i] = tmp;
        console.log(arr)
    }
}

// [5, 4, 3, 2, 1]
// [1, 4, 3, 2, 5]
// [1, 2, 3, 4, 5]
// [1, 2, 3, 4, 5]
// [1, 2, 3, 4, 5]

← 构造函数/类 →