算法基础 - 排序

# 排序？

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

# 术语说明

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

# 排序算法总结

【说明】

• n: 数据的规模
• k: "桶"的个数
• in-place: 占用常数内存，不占用额外内存
• out-place: 占用额外内存
   

# 排序算法分类

 

# 测试用例

  为了检验算法的正确性，算法的测试用例就显得非常重要，这里要求测试用例提供的测试数据范围必须要广，如果需要压力测试，数据量必须要大。因此，采用硬编码形式编写测试用例并不理想，最好能采用程序的方式实现数据的生成，同时也要考虑到边缘数据的测试用例。

---

 

# 选择排序

  时间复杂度：O(n*n)
  稳定性：不稳定
  升序思路：在未排序序列中找到最小（大）元素，与未排序的第一个元素交换位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，再与未排序的第一个元素交换位置。以此类推，直到所有元素均排序完毕。

function selectionSort (arr, n) {
    for(var i = 0; i < n; i ++ ) {
        var minIndex = i
        for (var j = i + 1; j < n; j ++ ) {
              if ( arr[i] > arr[j] ) { // 查找最小数
                  minIndex = j     //将最小数的索引保存
              }
        }
        var tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
    return arr
}

测试用例 （此处为了方便，采用硬编码形式）

function main () {
    var a = ['a', 'b', 'd', 'c']
    selectionSort (a, a.length);
    document.write(a)
    // 不稳定案例
    var b = [6, 4, 6, 2, 8];
}

 

# 冒泡排序

  时间复杂度： O(n*n)
  稳定性：稳定
  排序思路：从第一项开始比较相邻的两项，如果后者比前者小，则交换位置，否则不动，以此类推，此轮结束后最大的元素被交换到末尾，且将不需要再参与比较。继续下一轮比较。

function bubbleSort (arr) {
    var len = arr.length
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - i; j++) {
            if (arr[j] < arr[j + 1]) {
                var tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    return arr;
}

 

# 插入排序

  时间复杂度：O(n*n); 最有效的O(n*n)排序算法，在近有序的序列中，比O(nlogn)效率还要高
  稳定性：稳定
  排序思路： 通过从前往后构建有序序列，取后面未排序序列中的第一个，与前面已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

function insertSort (arr) {
    var len = arr.length;
    for ( var i = 1; i < len; i++ ) {
        var curent = arr[i]
        for ( var j = i - 1; j == 0; j--) {
            if ( arr[j] > curent ) {   // 循环元素比当前当前大，则当前元素往后挪
                arr[j+1] = arr[j];
            } else {                       //循环元素比当前待插小，则将tmp插入当前之后
                arr[j+1] = current;
            }
        }
    }
    return arr
}

或者如下写法

function insertSort2 (arr) {
    for ( var i = 1; i < len; i++ ) {
        for ( var j = i; j > 1 && arr[j] > arr[i]; j++ ) {
            swap(arr[j], arr[i]);
        }
    }
    return arr;
}
function swap(a, b) {
  var tmp = a;
  a = b;
  b = tmp;
}

 

# 希尔排序

  希尔排序是插入排序的改进版，与其不同的是，优先比较的不是相邻的两个元素，而是相距较远的的元素。希尔排序又叫缩小增量排序，其核心在于如何设定间隔序列。
  时间复杂度：平均O(nlogn)
  稳定性： 不稳定
  排序思路：将整个待排序序列分割成若干个序列分别进行直接插入排序
（1）选择一个增量序列，如t1,t2,...tk；其中，ti>tj; tk = 1;
（2）按增量序列个数k，对序进行k次排序，
（3）每次排序，更具对应的增量ti，将待排序列分割成若干个长度为m的子序列，分别对各子表进行插入排序，直到增量为1，排序结束。

【疑点】或许你会疑惑，为什么希尔排序中需要经过好几轮的插入排序，并且最终在k=1情况下还要做一次完整的插入排序，也就是说做了多次的插入排序，为什么还说是插入排序的改进版呢？
 答： 或许你没有真正理解插入排序的强势之处。插入排序的时间复杂度在最好和最坏的情况下相差特别之大，一个是O(n); 另一个是O(n*n)；而插入排序在 （1）排序数据量小 （2）待排序列几乎有序 的时候最容易达到O(n)的时间复杂度。希尔排序正是利用了插入排序的这两个特点，在最开始的时候将长序列分割成短序列，慢慢合并起来的序列的有序化程度也会越来越高，因此虽然最后做了一个全序列排序，但其实已经是非常接近有序序列的顺序了，所以排序的速度会很快。
 

# 归并排序

  时间复杂度： O(nlogn)
  稳定性：稳定
  排序思路： 分两步：分和治。分即将整个待排队列不断的分成两部分，直至每部分只剩单一元素。治的思想需要借助一个辅助队列，其长度为两个子队列长度的和。前提有两个子队列已完成排序（单个元素自身已排好序）。在其合并时，对比两个子队列第一个元素，取小的值放入辅助队列，并将该子队列下标加一继续与另一个子队列对比，依旧取小的放入辅助队列，依次类推结束，辅助数组就是已排好序的下次递归的一个子序列。

image.png

function __merge( arr, l, mid, r ) {
  var aux = new Array(r - l +1);
  for ( var i = l; i <= r; i ++ ) {
    aux[i-l] = arr[i]
  }
  
  var i = l, j = mid + 1;
  for ( var k = 0; k <= r; k ++ ) {
    if ( i > mid ) {
      arr[k] = aux[j-l];
      j ++;
    } else if ( j > r ) {
      arr[k] = aux[i-l];
      j ++;
    } else if ( aux[i-l] > aux[j-l]) {
      arr[k] = aux[j-l];
      j++;
    } else {
      arr[k] = aux[i-l]
      i++;
    }
  }
  
}

function __mergeSort(arr, l, r) { 
  if ( l >= r ) {
    return; 
  }
  var mid = parseInt((l + r)/2);
  __mergeSort(arr, l, mid);
  __mergeSort(arr, mid + 1, r);
  __merge(arr, l, mid, r);
}

function mergeSort( arr ) {
  var len = arr.length - 1;
  
  __mergeSort( arr, 0, len )
}

 

# 快速排序

  快速排序是几种排序算法中最为重要的一种。他有几个关键元素：
（1）基准数，
（2）左哨兵，
（3）右哨兵

  时间复杂度：O(nlogn)
  稳定性：不稳定
  排序思路：利用两个哨兵不断的检查队列中数据与基准数的大小关系，将其放置在队列的”前半部分“和“后半部分“。升序中，右哨兵负责检查比基准数小的元素，该元素会被丢至前半部分，左哨兵负责检查比基准数大的元素，该元素会被交换至后半部分。
（1）将数组的第一个元素当做基准数
（2）设置i和j两个哨兵，分别从排序数组的左边界和右边界开始检查数据
（3）必须右哨兵先出发检查，找到第一个比基准数小的数字，暂停检查并记录位置，左哨兵开始检查，找到第一个比基准数大的数字。然后左右哨兵的值交换位置。以此类推，直到左右哨兵相遇，此次检查结束。一次排序检查之后，就形成了大致升序的趋势。
（4）此时数组的状态是以左右哨兵相遇位置，前半部分包括哨兵位置都是比基准数小的，后半部分都是比基准数大的。此时交换哨兵与基准数，基准数便落入了最终排序应该出现的位置。
（5）以基准书将数组分成两部分去递归以上步骤，即可。
 实现代码如下

/**
 * @func 快速排序算法
 * @param arr-待排序队列，left-排序左边界，right-排序右边界
 * @method i-左哨兵，j-右哨兵, base-基准数，temp-交换变量
 * @tips:
 *   右哨兵任务即找到比基准数小的丢到左边，左哨兵找大的丢到右边。
 *   哨兵查找顺序很重要，必须右哨兵先找，这样能先定位到一个比
 *   基准数小的值，便于最后与基准数交换保证逻辑正确
 **/
var arr = [5, 1, 7, 8, 3, 2, 9, 4, 6];
quickSort(0, arr.length - 1);
console.log(arr);

function quickSort(left, right) {
 var i, j, base, temp;
 // 递归只剩一个元素，或参数问题，结束排序
 if (left >= right) return

 i = left;  // 左哨兵站位左边界
 j = right;   // 左哨兵站位右边界
 base = arr[left];  // 基准数规则取左边界值

 while (i != j) {  // 哨兵未碰面，本轮检查继续。
   // 必须右哨兵优先开始检查，比基准数大，继续往左检查。比基准数小，暂停。
   // 等号是为了让队列只有一个值的时候正常运行
   while (arr[j] >= base && i < j) {
     j --
   }
   // 左哨兵开始检查，比基准数小，继续往右检查
   while (arr[i] <= base && i < j) {
     i ++
   }
   // 左哨兵检找到比基准数大，右哨兵找到比基准数小，交换数据
   if (i < j) {  // i==j，不需要交换
     temp = arr[i];
     arr[i] = arr[j];
     arr[j] = temp;
   }
 }
 /**
  * while循环结束，左右哨兵碰面，本次检查结束
  * 此时队列状态是哨兵及哨兵左边均比基准数小，哨兵右边均比基准数大
  * 接下来，将交换基准数与哨兵位置，基准数便归位最终正确位置
  **/
 arr[left] = arr[i];  // 左哨兵(与右哨兵重合)，
 arr[i] = base;  // 基准数归位

 // 以基准数为分隔位置切分队列，递归调用执行子序列
 quickSort(left, i-1);
 quickSort(i+1, right);
}