算法好难啊!写点简单的。然后用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] 比较
- 完成!
动画示例:
代码实现:
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(){
}
动画示例:
快速排序(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(){
}