1.背景介绍

2.知识剖析

• 冒泡算法
• 选择排序
• 插入排序
• 快速排序

3.常见问题

问题:如何用JavaScript 如何实现?

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素， 如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有元素再需要交换， 也就是说该数列已经排序完成。

冒泡排序

              
var examplearr=[8,94,15,88,55,76,21,39];
function sortarr(arr){
    for(i=0;iarr[j+1]){
                var temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    return arr;
}
sortarr(examplearr);
console.log(examplearr);
          

选择排序

  Array.prototype.selectionSort = function() {
      var i, j, min;
      var temp;
      for (i = 0; i < this.length - 1; i++) {
          min = i;
          for (j = i + 1; j < this.length; j++)
              if (this[min] > this[j])
                  min = j;
          temp = this[min];
          this[min] = this[i];
          this[i] = temp;
      }
      return this;
  };
  var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定义一个数组

  num.selectionSort(); //数组定义选择排序算法
          

选择排序

1.找出最小的数，和第一个交换位置

2.在剩下的数中，找出最二小的数，放在第二个

3.依次类推，排出顺序

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 将新元素插入到该位置后
5. 重复步骤2~5

插入排序

            Array.prototype.insertionSort = function () {
               for (var i = 1; i < this.length; i++) {
                   var temp = this[i];
                   var j = i - 1;
                   //如果将赋值放到下一行的for循环内, 会导致在第13行出现j未声明的错误
                   for (; j >= 0 && this[j] > temp; j--) {
                       this[j + 1] = this[j];
                   }
                   this[j + 1] = temp;
               }
               return this;
            }
            var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定义一个数组

            num.insertionSort(); //数组调用插入排序算法
        

插入排序

基本思路：1.把数组分为[已排序]和[未排序]两部分,第一个数为[已排序]，其余为[未排序] 2.从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置

快速排序

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个演算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

  Array.prototype.quickSort = function() {
	var len = this.length;
	if (len <= 1)
		return this.slice(0);
	var left = [];
	var right = [];
	var mid = [this[0]];
	for (var i = 1; i < len; i++)
		if (this[i] < mid[0])
			left.push(this[i]);
		else
			right.push(this[i]);
	return left.quickSort().concat(mid.concat(right.quickSort()));
};

var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quickSort();
          

快速排序

1.以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边

2.再按此方法对这两部分数据分别进行快速排序（递归进行

3.不能再分后退出递归，并重新将数组合并

6.扩展思考

如何评价算法的好坏

正确性

算法能满足具体问题的需求，即对任何合法的输入算法都会得出正确的结果。

可读性

算法创建后由人来阅读、理解、使用以及修改。所以可读性的好坏直接影响到算法的好坏。如果一个算法涉及的想法很多，就会给阅读的人造成困难，那么这个算法就不能得到更好的交流和推广，更不便于对算法进行修改、扩展和维护。所以要提高算法的可读性，就要做到简明易懂。

健壮性

一个程序完成后，运行该程序的用户对程序的理解各有不同，并不能保证每一个人都能按照要求进行输入，健壮性就是指对非法输入的抵抗能力，当输入的数据非法时，算法能识别并做出处理，而不会因为输入的错误产生错误动作或造成瘫痪

时间复杂度与空间复杂度

时间复杂度简单地说就是算法运行所需要的时间。不同的算法具有不同的时间复杂度，当一个程序较小时感觉不到时间复杂度的重要性，当一个程序特别大时便会察觉到时间复杂度的重要性。所以如何写出更高速的算法一直是算法不断改进的目标。空间复杂度是指算法运行所需的存储空间，随着计算机硬件的发展，空间复杂度已经显得不再那么重要