几种排序算法浅析--JavaScript

算法好难啊!写点简单的。然后用JavaScript实现。

排序算法(Sorting Algorithm)

概念

一种能将一串资料依照特定排序方式进行排列的一种算法

一般规则
  • 输出结果为递增(递减)序列
  • 输出结果是原输入的一种排列或是重组
分类方式
  1. 依据计算的 时间复杂度 分类
    • 概念:完成一个算法所用的时间
    • 表示:O(),变量为 n(表示输入的长度)
    • 最好:O(n log n)
    • 最坏:O(n²)
    • O(n): 无序数组的搜索
    • O(log n): 二分搜索
    • O(n log n):
      • 比较排序(最好的)
      • 快速排序(最好的)
      • 堆排序
    • O(n²):
      • 冒泡排序
      • 插入排序
      • 选择排序
  2. 依据 记忆体使用量(以及其他电脑资源的使用) 分类
  3. 依据 稳定性 分类
    • 例如对 (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)
      • 堆排序
  4. 依据 排序的方式 分类
    • 插入
      • 插入排序
      • 希尔排序
    • 选择
      • 选择排序
      • 堆排序
    • 交换
      • 冒泡排序
      • 快速排序
    • 归并
      • 归并排序
    • 分布
      • 基数排序
      • 计数排序
      • 桶排序
    • 并发
    • 混合
    • 其他

冒泡排序(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(){

}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,179评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,229评论 2 380
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,032评论 0 336
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,533评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,531评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,539评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,916评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,574评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,813评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,568评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,654评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,354评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,937评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,918评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,152评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,852评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,378评论 2 342

推荐阅读更多精彩内容