冒泡排序是一次比较两个元素，如果顺序是错误的就把它们交换过来。，直到不需要再交换
快速排序的基本思想是通过一趟排序，将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序
从数列中挑出一个元素，称为 “基准”（pivot）；然后重新排序数列，所有元素比基准值小的摆放在基准前面、比基准值大的摆在基准的后面；在这个区分搞定之后，该基准就处于数列的中间位置；然后把小于基准值元素的子数列（left）和大于基准值元素的子数列（right）递归地调用 quick 方法排序完成，这就是快排的思路
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，从而达到排序的效果
插入排序的思路是基于数组本身进行调整的，首先循环遍历从 i 等于 1 开始，拿到当前的 current 的值，去和前面的值比较，如果前面的大于当前的值，就把前面的值和当前的那个值进行交换，通过这样不断循环达到了排序的目的
将最小的元素存放在序列的起始位置，再从剩余未排序元素中继续寻找最小元素，然后放到已排序的序列后面……以此类推，直到所有元素均排序完毕
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质，即子结点的键值或索引总是小于（或者大于）它的父节点。堆的底层实际上就是一棵完全二叉树，可以用数组实现
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
通过 mid 可以把该数组分成左右两个数组，分别对这两个进行递归调用排序方法，最后将两个数组按照顺序归并起来
排序算法说明:
（1）对于评述算法优劣术语的说明
稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序 ：所有排序操作都在内存中完成；
外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度 : 一个算法执行所耗费的时间。
空间复杂度 : 运行完一个程序所需内存的大小。
(2)排序算法图片总结:
1.冒泡排序:
解析：1.比较相邻的两个元素，如果前一个比后一个大，则交换位置。
2.第一轮的时候最后一个元素应该是最大的一个。
3.按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。
2.快速排序:
解析：快速排序是对冒泡排序的一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小。然后递归调用，在两边都实行快速排序。
3.插入排序:
解析：
（1） 从第一个元素开始，该元素可以认为已经被排序
（2） 取出下一个元素，在已经排序的元素序列中从后向前扫描
（3） 如果该元素（已排序）大于新元素，将该元素移到下一位置
（4） 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
（5）将新元素插入到下一位置中
（6） 重复步骤2
2.二分查找:
解析：二分查找，也为折半查找。首先要找到一个中间值，通过与中间值比较，大的放又，小的放在左边。再在两边中寻找中间值，持续以上操作，直到找到所在位置为止。
（1）递归方法
（2）非递归方法
4.选择排序:
解析:首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
5.希尔排序:
解析:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
6.归并排序:
解析:归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
7.堆排序:
解析:堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是
小于（或者大于）它的父节点。
8.计数排序:
解析:计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
9.桶排序:
解析:假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排
10.基数排序:
解析:基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优
先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶 计数排序：每个桶只存储单一键值 桶排序：每个桶存储一定范围的数值
js常用排序实现，参考代码如下
<script>Array.prototype.swap = function(i, j)
{
var temp = this[i]
this[i] = this[j]
this[j] = temp
}
Array.prototype.bubbleSort = function()
{
for (var i = this.length - 1 i > 0 --i)
{
for (var j = 0 j < i ++j)
{
if (this[j] > this[j + 1]) this.swap(j, j + 1)
}
}
}
Array.prototype.selectionSort = function()
{
for (var i = 0 i < this.length ++i)
{
var index = i
for (var j = i + 1 j < this.length ++j)
{
if (this[j] < this[index]) index = j
}
this.swap(i, index)
}
}
Array.prototype.insertionSort = function()
{
for (var i = 1 i < this.length ++i)
{
var j = i, value = this[i]
while (j > 0 && this[j - 1] > value)
{
this[j] = this[j - 1]
--j
}
this[j] = value
}
}
Array.prototype.shellSort = function()
{
for (var step = this.length >> 1 step > 0 step >>= 1)
{
for (var i = 0 i < step ++i)
{
for (var j = i + step j < this.length j += step)
{
var k = j, value = this[j]
while (k >= step && this[k - step] > value)
{
this[k] = this[k - step]
k -= step
}
this[k] = value
}
}
}
}
Array.prototype.quickSort = function(s, e)
{
if (s == null) s = 0
if (e == null) e = this.length - 1
if (s >= e) return
this.swap((s + e) >> 1, e)
var index = s - 1
for (var i = s i <= e ++i)
{
if (this[i] <= this[e]) this.swap(i, ++index)
}
this.quickSort(s, index - 1)
this.quickSort(index + 1, e)
}
Array.prototype.stackQuickSort = function()
{
var stack = [0, this.length - 1]
while (stack.length > 0)
{
var e = stack.pop(), s = stack.pop()
if (s >= e) continue
this.swap((s + e) >> 1, e)
var index = s - 1
for (var i = s i <= e ++i)
{
if (this[i] <= this[e]) this.swap(i, ++index)
}
stack.push(s, index - 1, index + 1, e)
}
}
Array.prototype.mergeSort = function(s, e, b)
{
if (s == null) s = 0
if (e == null) e = this.length - 1
if (b == null) b = new Array(this.length)
if (s >= e) return
var m = (s + e) >> 1
this.mergeSort(s, m, b)
this.mergeSort(m + 1, e, b)
for (var i = s, j = s, k = m + 1 i <= e ++i)
{
b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++]
}
for (var i = s i <= e ++i) this[i] = b[i]
}
Array.prototype.heapSort = function()
{
for (var i = 1 i < this.length ++i)
{
for (var j = i, k = (j - 1) >> 1 k >= 0 j = k, k = (k - 1) >> 1)
{
if (this[k] >= this[j]) break
this.swap(j, k)
}
}
for (var i = this.length - 1 i > 0 --i)
{
this.swap(0, i)
for (var j = 0, k = (j + 1) << 1 k <= i j = k, k = (k + 1) << 1)
{
if (k == i || this[k] < this[k - 1]) --k
if (this[k] <= this[j]) break
this.swap(j, k)
}
}
}
function generate()
{
var max = parseInt(txtMax.value), count = parseInt(txtCount.value)
if (isNaN(max) || isNaN(count))
{
alert("个数和最大值必须是一个整数")
return
}
var array = []
for (var i = 0 i < count ++i) array.push(Math.round(Math.random() * max))
txtInput.value = array.join("\n")
txtOutput.value = ""
}
function demo(type)
{
var array = txtInput.value == "" ? [] : txtInput.value.replace().split("\n")
for (var i = 0 i < array.length ++i) array[i] = parseInt(array[i])
var t1 = new Date()
eval("array." + type + "Sort()")
var t2 = new Date()
lblTime.innerText = t2.valueOf() - t1.valueOf()
txtOutput.value = array.join("\n")
}
</script>
<body onload=generate()>
<table style="width:100%height:100%font-size:12pxfont-family:宋体">
<tr>
<td align=right>
<textarea id=txtInput readonly style="width:100pxheight:100%"></textarea>
</td>
<td width=150 align=center>
随机数个数<input id=txtCount value=500 style="width:50px"><br><br>
最大随机数<input id=txtMax value=1000 style="width:50px"><br><br>
<button onclick=generate()>重新生成</button><br><br><br><br>
耗时(毫秒)：<label id=lblTime></label><br><br><br><br>
<button onclick=demo("bubble")>冒泡排序</button><br><br>
<button onclick=demo("selection")>选择排序</button><br><br>
<button onclick=demo("insertion")>插入排序</button><br><br>
<button onclick=demo("shell")>谢尔排序</button><br><br>
<button onclick=demo("quick")>快速排序(递归)</button><br><br>
<button onclick=demo("stackQuick")>快速排序(堆栈)</button><br><br>
<button onclick=demo("merge")>归并排序</button><br><br>
<button onclick=demo("heap")>堆排序</button><br><br>
</td>
<td align=left>
<textarea id=txtOutput readonly style="width:100pxheight:100%"></textarea>
</td>
</tr>
</table>
</body>
