常见的排序算法有哪些？如何实现这些算法？

1.背景介绍

在计算机科学与数学中，一个排序算法是一种能将一串资料依照特定排序方式进行排列的一种算法。 最常用到的排序方式是数值顺序以及字典顺序。 排序算法用在处理文字资料以及产生人类可读的输出结果。 基本上，排序算法的输出必须遵守下列两个原则：

输出结果为递增序列（递增是针对所需的排序顺序而言）

输出结果是原输入的一种排列、或是重组

虽然排序算法是一个简单的问题，但是从计算机科学发展以来，在此问题上已经有大量的研究。 更多的新算法仍在不断的被发明。

2.知识剖析

查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。 所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。 一般在面试中最常考的是快速排序和归并排序，并且经常有面试官要求现场写出这两种排序的代码。 对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。

冒泡算法

选择排序

插入排序

快速排序

3.常见问题

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

4.解决方案

冒泡排序

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

冒泡排序演算法的运作如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序

var examplearr=[8,94,15,88,55,76,21,39];

function sortarr(arr){

for(i=0;i

for(j=0;j

if(arr[j]>arr[j+1]){

var temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

}

}

return arr;

}

sortarr(examplearr);

console.log(examplearr);

冒泡排序

基本思路：1.依次比较相邻的两个数，如果第一个比第二个小，不变。如果第一个比第二个大，调换顺序。一轮下来，最后一个是最大的数

2.对除了最后一个之外的数重复第一步，直到只剩一个数

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素， 然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同， 冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。

选择排序

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.依次类推，排出顺序

插入排序也是一个简单直观的排序算法。它的 工作原理是通过构建有序序列，对于未排序数据， 在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序 （即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位， 为最新元素提供插入空间。

从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果该元素（已排序）大于新元素，将该元素移到下一位置

将新元素插入到该位置后

重复步骤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.从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置

快速排序

步骤为：

从数列中挑出一个元素，称为"基准"（pivot），

重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。

递归地（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.不能再分后退出递归，并重新将数组合并

5.编码实战

6.扩展思考

如何评价算法的好坏

正确性

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

可读性

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

健壮性

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

时间复杂度与空间复杂度

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

7.参考文献

参考二：常见排序算法之JavaScript实现

参考一：JavaScript 排序算法汇总