数据结构(十六)之简单排序

如需转载, 请咨询作者, 并且注明出处.
有任何问题, 可以关注我的微博: coderwhy, 或者添加我的微信: 372623326

排序算法是笔试中经常出现的, 其实排序算法是很容易考察出一个人的思维水平的.

排序算法有很多: 冒泡排序/选择排序/插入排序/归并排序/计数排序(counting sort)/基数排序(radix sort)/希尔排序/堆排序/桶排序.

我们这里不一一列举它们的实现思想, 而是选择几个简单排序和高级排序.(后续有机会给大家视频讲解)

简单排序: 冒泡排序 - 选择排序 - 插入排序

高级排序: 希尔排序 - 快速排序

其他排序的理论和思想, 大家可以自行学习.

一. 排序介绍

我们先对排序有个简单的认识, 然后开始介绍几种简单排序.

排序介绍

• 一旦我们将数据放置在某个数据结构中存储起来后(比如数组), 就可能根据需求对数据进行不同方式的排序
  • 比如对姓名按字母排序
  • 对学生按年龄排序
  • 对商品按照价格排序
  • 对城市按照面积或者人口数量排序
  • 对恒星按照大小排序
  • 等等
• 由于排序非常重要而且可能非常耗时, 所以它已经成为一个计算机科学中广泛研究的课题, 而且人们已经研究出一套成熟的方案来实现排序.
  • 但是, 我们学习已有的排序方法是非常有必要的.

如何排序?

• 需求: 对一组身高不等的10个人进行排序
• 人来排序:
  • 如果是人来排序事情会非常简单, 因为人只要扫过去一眼就能看出来谁最高谁最低.
  • 然后让最低(或者最高)的站在前面, 其他人依次后移.
  • 按照这这样的方法. 依次类推就可以了.
• 计算机来排序:
  • 计算机有些笨拙, 它只能执行指令. 所以没办法一眼扫过去.
  • 计算机也很聪明, 只要你写出了正确的指令, 可以让它帮你做无数次类似的事情而不用担心出现错误.
  • 并且计算机排序也无需担心数据量的大小.(想象一样, 让人排序10000个, 甚至更大的数据项你还能一眼扫过去吗?)
  • 人在排序时不一定要固定特有的空间, 他们可以相互推推嚷嚷就腾出了位置, 还能互相前后站立.
  • 但是计算机必须有严密的逻辑和特定的指令.
• 计算机排序的特点:
  • 计算机不能像人一样, 一眼扫过去这样通览所有的数据.
  • 它只能根据计算机的比较操作原理, 在同一个时间对两个队员进行比较.
  • 在人类看来很简单的事情, 计算机的算法却不能看到全景, 因此它只能一步步解决具体问题和遵循一些简单的规则.
• 简单算法的主要操作:
  • 比较两个数据项.
  • 交换两个数据项, 或者复制其中一项.
  • 但是, 每种算法具体实现的细节有所不同.

创建列表

• 在开始排序前, 我们先来创建一个列表封装我们的数据项.

  // 封装ArrayList
  function ArrayList() {
      this.array = []
  
      ArrayList.prototype.insert = function (item) {
          this.array.push(item)
      }
  
      ArrayList.prototype.toString = function () {
          return this.array.join()
      }
  }
  

• 初始化数据项

  // 初始化数据项
  var list = new ArrayList()
  
  list.insert(3)
  list.insert(6)
  list.insert(4)
  list.insert(2)
  list.insert(11)
  list.insert(10)
  list.insert(5)
  
  alert(list)
  

二. 冒泡排序

冒泡排序算法相对其他排序运行效率较低, 但是在概念上它是排序算法中最简单的.

因此, 冒泡排序是在刚开始学习排序时, 最适合学习的一种排序方式.

冒泡排序的思路

• 冒泡排序的思路:

  • 对未排序的各元素从头到尾依次比较相邻的两个元素大小关系
  • 如果左边的队员高, 则两队员交换位置
  • 向右移动一个位置, 比较下面两个队员
  • 当走到最右端时, 最高的队员一定被放在了最右边
  • 按照这个思路, 从最左端重新开始, 这次走到倒数第二个位置的队员即可.
  • 依次类推, 就可以将数据排序完成

• 冒泡排序的图解:

  img

• 思路再分析:

  • 第一次找出最高人放在最后, 我们需要两个两个数据项进行比较, 那么这个应该是一个循环操作.
  • 第二次将次高的人找到放在倒数第二个位置, 也是两个比较, 只是不要和最后一个比较(少了一次), 但是前面的两个两个比较也是一个循环操作.
  • 第三次...第四次...
  • 有发现规律吗? 这应该是一个循环中嵌套循环, 并且被嵌套的循环次数越来越少的.
  • 根据这个分析, 你能写出代码实现吗?

冒泡排序的实现

• 冒泡排序的实现:

  ArrayList.prototype.bubbleSort = function () {
      // 1.获取数组的长度
      var length = this.array.length
  
      // 2.反向循环, 因此次数越来越少
      for (var i = length - 1; i >= 0; i--) {
          // 3.根据i的次数, 比较循环到i位置
          for (var j = 0; j < i; j++) {
              // 4.如果j位置比j+1位置的数据大, 那么就交换
              if (this.array[j] > this.array[j+1]) {
                  // 交换
                  this.swap(j, j+1)
              }
          }
      }
  }
  
  ArrayList.prototype.swap = function (m, n) {
      var temp = this.array[m]
      this.array[m] = this.array[n]
      this.array[n] = temp
  }
  

• 代码解析:

  • 代码序号1: 获取数组的长度.
  • 代码序号2: 我们现在要写的外层循环, 外层循环应该让i依次减少, 因此我们这里使用了反向的遍历.
  • 代码需要3: 内层循环, 内层循环我们使用 j < i. 因为上面的i在不断减小, 这样就可以控制内层循环的次数.
  • 代码需要4: 比较两个数据项的大小, 如果前面的大, 那么就进行交换.

• 代码图解流程:

  img

• 测试代码:

  // 测试冒泡排序
  list.bubbleSort()
  alert(list) // 2,3,4,5,6,10,11
  

冒泡排序的效率

• 冒泡排序的比较次数:
  • 如果按照上面的例子来说, 一共有7个数字, 那么每次循环时进行了几次的比较呢?
  • 第一次循环6次比较, 第二次5次比较, 第三次4次比较....直到最后一趟进行了一次比较.
  • 对于7个数据项比较次数: 6 + 5 + 4 + 3 + 2 + 1
  • 对于N个数据项呢? (N - 1) + (N - 2) + (N - 3) + ... + 1 = N * (N - 1) / 2
• 大O表示法:
  • 大O表示法是描述性能和复杂度的一种表示方法.
  • 推导大O表示法通常我们会使用如下规则:
    • 用常量1取代运行时间中的所有加法常量
    • 在修改后的运行次数函数中, 只保留最高阶项
    • 如果最高阶项存在并且不是1, 则去除与这个项相乘的常数.
• 通过大O表示法推到过程, 我们来推到一下冒泡排序的大O形式.
  • N * (N - 1) / 2 = N²/2 - N/2,根据规则2, 只保留最高阶项, 编程N² / 2
  • N² / 2, 根据规则3, 去除常量, 编程N²
  • 因此冒泡排序的大O表示法为O(N²)
• 冒泡排序的交换次数:
  • 冒泡排序的交换次数是多少呢?
  • 如果有两次比较才需要交换一次(不可能每次比较都交换一次.), 那么交换次数为N² / 4
  • 由于常量不算在大O表示法中, 因此, 我们可以认为交换次数的大O表示也是O(N²)

三. 选择排序

选择排序改进了冒泡排序, 将交换的次数由O(N²)减少到O(N), 但是比较的次数依然是O(N²)

选择排序的思路

• 选择排序的思路:

  • 选定第一个索引位置，然后和后面元素依次比较
  • 如果后面的队员, 小于第一个索引位置的队员, 则交换位置
  • 经过一轮的比较后, 可以确定第一个位置是最小的
  • 然后使用同样的方法把剩下的元素逐个比较即可
  • 可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到最后

• 选择排序的图解

  img

• 思路再分析:

  • 选择排序第一次将第0位置的人取出, 和后面的人(1, 2, 3...)依次比较, 如果后面的人更小, 那么就交换.
  • 这样经过一轮之后, 第一个肯定是最小的人.
  • 第二次将第1位置的人取出, 和后面的人(2, 3, 4...)依次比较, 如果后面的人更小, 那么就交换.
  • 这样经过第二轮后, 第二个肯定是次小的人.
  • 第三轮...第四轮...直到最后就可以排好序了. 有发现规律吗?
  • 外层循环依次取出0-1-2...N-2位置的人作为index(N-1不需要取了, 因为只剩它一个了肯定是排好序的)
  • 内层循环从index+1开始比较, 直到最后一个.
  • 经过分析, 你能写出最终的算法吗?

选择排序的实现

• 选择排序的实现:

  ArrayList.prototype.selectionSort = function () {
      // 1.获取数组的长度
      var length = this.array.length
  
      // 2.外层循环: 从0位置开始取出数据, 直到length-2位置
      for (var i = 0; i < length - 1; i++) {
          // 3.内层循环: 从i+1位置开始, 和后面的内容比较
          var min = i
          for (var j = min + 1; j < length; j++) {
              // 4.如果i位置的数据大于j位置的数据, 那么记录最小的位置
              if (this.array[min] > this.array[j]) {
                  min = j
              }
          }
          // 5.交换min和i位置的数据
          this.swap(min, i)
      }
  }
  

• 代码解析:

  • 代码序号1: 依然获取数组的长度.
  • 代码序号2: 外层循环, 我们已经讲过, 需要从外层循环的第0个位置开始, 依次遍历到length - 2的位置.
  • 代码序号3: 先定义一个min, 用于记录最小的位置, 内层循环, 内层循环是从i+1位置开始的数据项, 和i位置的数据项依次比较, 直到length-1的数据项.
  • 代码序号4: 如果比较的位置i的数据项, 大于后面某一个数据项, 那么记录最小位置的数据.
  • 代码序号5: 将min位置的数据, 那么i位置的数据交换, 那么i位置就是正确的数据了.
  • 注意: 这里的交换是基于之前的交换方法, 这里直接调用即可.

• 代码图解流程:

  img

• 测试代码:

  // 测试选择排序
  list.selectionSort()
  alert(list) // 2,3,4,5,6,10,11
  

选择排序的效率

• 选择排序的比较次数:
  • 选择排序和冒泡排序的比较次数都是N*(N-1)/2, 也就是O(N²).
• 选择排序的交换次数:
  • 选择排序的交换次数只有N-1次, 用大O表示法就是O(N).
  • 所以选择排序通常认为在执行效率上是高于冒泡排序的.

四. 插入排序

插入排序是简单排序中效率最好的一种.

插入排序也是学习其他高级排序的基础, 比如希尔排序/快速排序, 所以也非常重要.

插入排序的思路

• 局部有序:

  • 插入排序思想的核心是局部有序. 什么是局部有序呢?
  • 比如在一个队列中的人, 我们选择其中一个作为标记的队员. 这个被标记的队员左边的所有队员已经是局部有序的.
  • 这意味着, 有一部门人是按顺序排列好的. 有一部分还没有顺序.

• 插入排序的思路:

  • 从第一个元素开始，该元素可以认为已经被排序
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置
  • 重复上一个步骤，直到找到已排序的元素小于或者等于新元素的位置
  • 将新元素插入到该位置后, 重复上面的步骤.

• 插入排序的图解

  img

• 思路再分析:

  • 插入排序应该从下标值1开始(因为0位置默认可以被认为是有序的)
  • 从1位置开始取出元素, 并且判断该元素的大小和0位置进行比较, 如果1位置元素小于0位置元素, 那么交换, 否则不交换.
  • 上面步骤执行完成后, 0 - 1位置已经排序好.
  • 取出2位置的元素, 和1位置进行比较:
    • 如果2位置元素大于1位置元素, 说明2位置不需要任何动作. 0 - 1 - 2已经排序好.
    • 如果2位置元素小于1位置元素, 那么将1移动到2的位置, 并且2继续和0进行比较.
    • 如果2位置元素大于0位置的元素, 那么将2位置放置在1的位置, 排序完成. 0 - 1 - 2搞定.
    • 如果2位置元素小于1位置的元素, 那么将0位置的元素移动到1位置, 并且将2位置的元素放在0位置, 0 - 1 - 2搞定.
  • 按照上面的步骤, 依次找到最后一个元素, 整个数组排序完成.
  • 经常上面的分析, 你能转化成对应的代码吗?

插入排序的实现

• 插入排序的实现:

  ArrayList.prototype.insertionSort = function () {
      // 1.获取数组的长度
      var length = this.array.length
  
      // 2.外层循环: 外层循环是从1位置开始, 依次遍历到最后
      for (var i = 1; i < length; i++) {
          // 3.记录选出的元素, 放在变量temp中
          var j = i
          var temp = this.array[i]
  
          // 4.内层循环: 内层循环不确定循环的次数, 最好使用while循环
          while (j > 0 && this.array[j-1] > temp) {
              this.array[j] = this.array[j-1]
              j--
          }
  
          // 5.将选出的j位置, 放入temp元素
          this.array[j] = temp
      }
  }
  

• 代码解析

  • 代码序号1: 获取数组的长度.
  • 代码序号2: 外层循环, 从1位置开始, 因为0位置可以默认看成是有序的了.
  • 代码序号3: 记录选出的i位置的元素, 保存在变量temp中. i默认等于j
  • 代码序号4: 内层循环
    • 内层循环的判断j - 1位置的元素和temp比较, 并且j > 0.
    • 那么就将j-1位置的元素放在j位置.
    • j位置向前移.
  • 代码序号5: 将目前选出的j位置放置temp元素.

• 代码的图解流程(来自维基百科):

  img

• 测试代码:

  // 测试插入排序
  list.insertionSort()
  alert(list) // 2,3,4,5,6,10,11
  

插入排序的效率

• 插入排序的比较次数:
  • 第一趟时, 需要的最多次数是1, 第二趟最多次数是2, 依次类推, 最后一趟是N-1次.
  • 因此是1 + 2 + 3 + ... + N - 1 = N * (N - 1) / 2.
  • 然而每趟发现插入点之前, 平均只有全体数据项的一半需要进行比较.
  • 我们可以除以2得到 N * (N - 1) / 4. 所以相对于选择排序, 其他比较次数是少了一半的.
• 插入排序的复制次数:
  • 第一趟时, 需要的最多复制次数是1, 第二趟最多次数是2, 依次类推, 最后一趟是N-1次.
  • 因此是1 + 2 + 3 + ... + N - 1 = N * (N - 1) / 2.
• 对于基本有序的情况
  • 对于已经有序或基本有序的数据来说, 插入排序要好很多.
  • 当数据有序的时候, while循环的条件总是为假, 所以它变成了外层循环中的一个简单语句, 执行N-1次.
  • 在这种情况下, 算法运行至需要N(N)的时间, 效率相对来说会更高.
  • 另外别忘了, 我们的比较次数是选择排序的一半, 所以这个算法的效率是高于选择排序的.