排序

冒泡排序

冒泡排序是一种简单的排序算法, 它重复的走访过要排序的树立, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来
运算

  1. 比较相邻的元素, 如果第一个比第二个大, 就交换他们两个
  2. 对每一对相邻元素做同样的工作, 从开始第一对到结尾的最后一对, 这步做完后, 最后的元素会是最大的数
  3. 针对所有的元素重复以上的步骤, 除了最后一个

  4. 持续每次对越来袁绍的元素重复上面的步骤, 直到没有任何一对数字需要比较 示意图 ☞ Bubble_sort_animation.gif

    1. Array.prototype.bubble_sort = function() {
    2.  let i, j, temp;
    3. for(i = 0; i < this.length - 1; i ++) {
    4.    for(j = 0; j < this.length - 1 - i; j ++) {
    5.      if (this[j] > this[j + 1]) {
    6.        temp = this[j];
    7.      this[j] = this[j + 1];
    8.      this[j + 1] = temp;
    9.    }
    10.  }
    11. }
    13. return this;
    14. }

插入排序

通过构建有序薛烈, 对于末排序数据, 在已排序序列中从后向前扫描, 找到相应位置并插入, 插入排序在实现上, 通常采用 in-place 排序(即只需用到 O(1)的额外空间的排序), 因而在从后向前扫描过程中, 需要反复把已排序元素逐步向后挪位, 为最新元素提供插入空间

示意图 ☞** **Insertion_sort_animation.gif

  1. Array.prototype.insertion_sort = function() {
  2.     let i, j;
  3.   for (i = 1; i < this.length; i ++) {
  4.       for (j = 0; j < i; j ++) {
  5.         if (this[j] > this[i]) {
  6.           this.splice(j, 0, this[i]);
  7.         this.splice(i + 1, 1);
  8.         break;
  9.       }
  10.     }
  11.   }
  12.     return this;
  13. }
  14. // 用法
  15. [3,5,2,11,1,2,"abc","zfd","sad","eng"].insertion_sort();

选择排序

首先在末排序蓄力中找到最小(大) 元素, 存放在排序序列的起始位置, 然后, 再从剩余末排序元素中继续寻找最小(大)元素, 然后放在已排序序列的末尾, 以此来推, 直到所有元素均排序完毕

示意图 ☞ 常用算法 - 图3

  1. Array.prototype.selection_sort = function() {
  2.     let i, j, min;
  4.   for(i = 0; i < this.length - 1; i ++) {
  5.       min = i;
  6.     for(j = i + 1; j < this.length; j ++) {
  7.         if (this[min] > this[j]) {
  8.           min = j;
  9.       }
  10.     }
  11.     temp = this[min];
  12.     this[min] = this[i];
  13.     this[i] = temp;
  14.   }
  15.   return this;
  16. }

希尔排序

希尔排序, 也称递减增量排序算法, 是插入排序的一种更搞笑的改进版本, 希尔排序是非稳定排序算法, 由两点性质提出改进方法

  1. 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
  2. 但插入排序一般来说是低效的, 因为插入排序每次只能移动数据一位

示意图 ☞ Sorting_shellsort_anim.gif

  1. Array.prototype.shell_sort = function() {
  2.     let gap, i, j;
  3.   let temp;
  4.   for (gap = this.length >> 1; gap > 0; gap >>= 1) {
  5.       for (i = gap; i < this.length; i ++) {
  6.         temp = this[i];
  7.       for (j = i -gap; j >= 0 && this[j] > temp; j -= gap) {
  8.           this[j + gap] = this[j];
  9.         this[j + gap] = temp;
  10.       }
  11.     }
  12.   }
  13.   return this;
  14. }

归并排序

创建在归并操作上的一种有效的排序算法
示意图 ☞ Merge_sort_animation2.gif

  1. function merge(left, right) {
  2.     let result = [];
  3.   while(left.length > 0 && right.length > 0) {
  4.       if (left[0] < right[0]) {
  5.         result.push(left.shift());
  6.     } else {
  7.         result.push(right.shift());
  8.     }
  9.   }
  10.   return result.concat(left, right);
  11. }
  13. function mergeSort(arr) {
  14.     if (arr.length <= 1) return arr;
  15.   const middle = Math.floor(arr.length / 2);
  16.   const left arr.slice(0, middle);
  17.   const right = arr.slice(middle);
  18.   return merge(mergeSort(left), mergeSort(right));
  19. }

快速排序

Quicksort 又称划分交换排序(partition-exchange sort)简称快排, 分成两块分别进行排序, 最后合并至一个数组

示意图 ☞ Sorting_quicksort_anim.gif

  1. Array.prototype.quickSort = function() {
  2.     const l = this.length;
  3.   if (l < 2) return this;
  5.   const basic = this[0];
  6.   const left = [];
  7.   const right = [];
  8.   for (let i = 1; i < l; i ++) {
  9.       const iv = this[i];
  10.     iv >= basic && right.push(iv);
  11.     iv < basic && left.push(iv);
  12.   }
  13.   return left.quickSort().concat(basic, right.quickSort())
  14. }

堆排序

指利用堆这种数据结构所设计的一种排序算法, 堆是一个近似完全二叉树的结构

示意图 ☞ Sorting_heapsort_anim.gif

  1. Array.prototype.heap_sort = function() {
  2.     const arr = this.slice(0);
  3.   function swap(i, j) {
  4.       let tmp = arr[i];
  5.     arr[i] = arr[j];
  6.     arr[j] = tmp;
  7.   }
  9.   function max_heapify(start, end) {
  10.       let dad = start;
  11.     const son = dad * 2 + 1;
  12.     if (son >= end) {
  13.         return;
  14.     }
  16.     if (son + 1 < end && arr[son] < arr[son + 1]) {
  17.         son ++
  18.     }
  19.     if (arr[dad] <= arrp[son]) {
  20.         swap(dad, son);
  21.       max_heapify(son, end);
  22.     }
  23.   }
  24.   const len = arr.length;
  25.   for (let i = Math.floor(len / 2) - 1; i >= 0; i --) {
  26.       max_heapify(i, len);
  27.   }
  29.   for (let i = len - 1; i > 0; i --) {
  30.       swap(0, i);
  31.     max_heapify(0, i);
  32.   }
  33.   return arr;
  34. }

参考

Javascript-algorithms
可视化算法
算法可视化
动画学习算法
Python 算法
炫酷的排序演示
可视化数据结构
分享/查看/创建的学习平台
旧金山大学数据结构和算法的可视化学习工具
**

博客

十大经典排序算法
算法时间复杂度简介