算法好难啊！写点简单的。然后用JavaScript实现。
排序算法（Sorting Algorithm）
概念
一种能将一串资料依照特定排序方式进行排列的一种算法
一般规则
- 输出结果为递增（递减）序列
- 输出结果是原输入的一种排列或是重组
分类方式
- 依据计算的 时间复杂度 分类
- 概念：完成一个算法所用的时间
- 表示：O()，变量为 n（表示输入的长度）
- 最好：O(n log n)
- 最坏：O(n²)
- O(n): 无序数组的搜索
- O(log n): 二分搜索
- O(n log n):
- 比较排序（最好的）
- 快速排序（最好的）
- 堆排序
- O(n²):
- 冒泡排序
- 插入排序
- 选择排序
- 依据 记忆体使用量（以及其他电脑资源的使用） 分类
- 依据 稳定性 分类
- 例如对 (1,2) (1,3) (2,1) 中的第一个数字排序，会有两种结果
- (1,2) (1,3) (2,1)
- (1,3) (1,2) (2,1)
- 这种现象就是不稳定性
- 不稳定排序算法可能会在相等的键值中改变纪录的相对次序
- 稳定的排序：
- 冒泡排序
- 插入排序
- 归并排序
- 计数排序 O(n + m)
- 基数排序 O(k*n)
- 桶排序
- 不稳定的排序：
- 快速排序
- 选择排序
- 希尔排序 O(n log² n)
- 堆排序
- 例如对 (1,2) (1,3) (2,1) 中的第一个数字排序，会有两种结果
- 依据 排序的方式 分类
- 插入
- 插入排序
- 希尔排序
- 选择
- 选择排序
- 堆排序
- 交换
- 冒泡排序
- 快速排序
- 归并
- 归并排序
- 分布
- 基数排序
- 计数排序
- 桶排序
- 并发
- 混合
- 其他
- 插入
冒泡排序（Bubble Sort）
原理：
- 比较相邻两个元素 a，b 的大小，如果 a < b ，b 就和 a 互换位置
（遍历一轮之后，最后一个元素最小，最后一个元素不参与下一轮比较） - 然后再次遍历
- 直到没有元素需要交换位置
举例说明：
有数组 arr = [a,b,c,d]，
- 那么 arr[0] 和 arr[1] 比较， arr[1] 和 arr[2] 比较， arr[2] 和 arr[3] 比较，
- 得到新的 arr1，那么 arr1[0] 和 arr1[1] 比较， arr1[1] 和 arr1[2] 比较，
- 得到新的 arr2，那么 ar2r[0] 和 arr2[1] 比较，
- 完成！
所以外层循环次数为 (arr.length - 1)
内层循环次数由 (arr.length - 1) 开始，每次减一
代码实现：
function BubbleSort(arr){
var n = arr.length
var temp
for(var i = 0; i < n - 1; i++){
for(var j = 0; j < n - 1 - i; j++){
if(arr[j] < arr[j + 1]){
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
var arr = [9,14,2,7,3]
SelectionSort(arr)
选择排序（Selection Sort）
原理：
- 从一堆元素中找出最大（小）的元素，放在第一位
- 从剩下的元素中继续找出最大（小）的元素，放在第二位
- 依次类推
- 直到完成
- 通过位置交换进行排序
举例说明：
有数组 arr = [a,b,c,d]，
- 假设 arr[0] 为最小值，然后和其他元素比较，如果遇到更小的，交换位置
- 遍历一轮后，交换位置后的 arr[0] 为最小值
- 然后将剩余的元素按这种方法继续排序
- 完成！
代码实现：
function SelectionSort(arr){
var n = arr.length
var temp
for(var i = 0; i < n -1; i++){
for(var j = 1 + i; j < n; j++){
if(arr[i] > arr[j]){
temp = arr[j]
arr[j] = min
arr[i] = temp
}
}
}
return arr
}
var arr = [9,14,2,7,3]
SelectionSort(arr)
插入排序（Insertion Sort）
原理：
- 以第一个元素为基准，开始排序
- 后面的元素依次从后往前与前面的元素比较，如果小，则插到该元素之前
举例说明：
有数组 arr = [a,b,c,d]
- 先将 arr[0] 排在第一位
- 然后排 arr[1] ，与 arr[0] 比较
- 然后排 arr[2] ，依次和 arr[1]，arr[0] 比较
- 然后排 arr[3] ，依次和 arr[2]，arr[1]，arr[0] 比较
- 完成！
动画示例：
插入排序（来自wiki）
代码实现：
function InsertionSort(arr){
for(var i = 1; i < arr.length; i++){
for(var j = 0; j < i; j++){
if(arr[i] < arr[j]){
arr.splice(j,0,arr[i])
arr.splice(i+1,1)
}
}
}
return arr
}
var arr = [9,14,2,7,3]
InsertionSort(arr)
希尔排序（递减增量排序算法）（Shell Sort）
原理：
举例说明：
代码实现：
function ShellSort(){
}
归并排序（Merge Sort）
原理：
举例说明：
代码实现：
function MergeSort(){
}
动画示例：
归并排序（来自wiki）
快速排序（Quick Sort）
原理：
举例说明：
代码实现：
function QuickSort(){
}
堆排序（Heap Sort）
原理：
举例说明：
代码实现：
function HeapSort(){
}
桶排序（Bucket Sort）
原理：
- 利用映射关系，准备一些桶，将需要排序的元素放到对应的桶里，最后去掉空的桶
举例说明：
有数组 arr = [1,9,2,4]，这里列举最理想的情况一个元素对应一个桶
- 准备九个桶（最大元素个数个桶），从1~9排好
- 将arr[0] 放到1号桶，arr[1] 放到9号桶，arr[2] ，放到2号筒，arr[3]，放到4号桶
- 去掉空的桶
- 完成！
代码实现：
function BucketSort(arr){
var newArr = [] //数组的每个位置可以看成是一个桶
var result = [] //用来存放结果
var len = [] //这里优化对浮点数的桶排序
var buckets = 0
for(var k = 0; k < arr.length; k++){
if(parseInt(arr[k]) !== arr[k]){
len.push(String(arr[k]).split('.')[1].length)
}
}
if(len.length !== 0){
buckets = Math.pow(10,Math.max.apply(null,len))
}
for(var i = 0; i < arr.length; i++){
newArr[arr[i]*buckets] = arr[i]
}
for(var j = 0; j < newArr.length; j++){
if(newArr[j] !== undefined){
result.push(newArr[j])
}
}
return result
}
var arr = [9,2.33,3.14,5.998,23,7]
BucketSort(arr)
计数排序（Counting Sort）
原理：
举例说明：
代码实现：
function CountingSort(){
}
基数排序（Radix Sort）
原理：
举例说明：
代码实现：
function RadixSort(){
}
网友评论