美文网首页
主流排序算法

主流排序算法

作者: sorry510 | 来源:发表于2020-02-29 14:52 被阅读0次

首先我们先定义一个交换2个变量的函数，这里使用 javascript 语言来写

交换遍历函数
function swap(arr, i, j) {
  const t = arr[i]
  arr[i] = arr[j]
  arr[j] = t
}

冒泡排序

后面的大数不断向前调整，就像水中的气泡不断往上冒

冒泡排序（简单版）

function bubbleSort(arr) {
    for(let i = 0; i < arr.length; i++) {
        for(let j = i + 1；j < arr.length; j++) {
            if(arr[i] > arr[j])
              swap(arr, i, j)
        }
    }
}

冒泡排序（正宗版）

function bubbleSort(arr) {
  for(let i = 0; i < arr.length; i++) {
    for(let j = arr.length - 1; j >= i; j--) { // j从后往前循环
      if(arr[j] > arr[j+1])
        awap(arr, j, j+1)
    }
  }
}

冒泡排序（优化：当前一次排序发现已经没有可交换的元素，之后就不用在遍历了），这里我们通过一个 flag 来控制开关

function bubbleSort(arr) {
  let flag = true
  for(let i = 0; i < arr.length && flag; i++) {
    flag = false // 如果flag一直未false说明没有发生交换
    for(let j = arr.length - 1; j >= i; j--) { // j从后往前循环
      if(arr[j] > arr[j+1]) {
        awap(arr, j, j+1)
        flag = true
      } 
    }
  }
}

时间复杂度\Sigma_{i=2}^n(i-1)=1+2+3+...+(n-1)=\frac{n(n-1)}{2},所以是O(n^2)

选择排序

简单选择排序（simple selection sort）

每次遍历都选出最小的值，放入到这次遍历的最前列

function selectSort(arr) {
  let min
  for(let i = 0; i < arr.length; i++) {
    min = i
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[min] > arr[j])
        min = j
    }
    if (i != min)
      swap(arr, i, min)
  }
}

时间复杂度\Sigma_{i=2}^n(i-1)=1+2+3+...+(n-1)=\frac{n(n-1)}{2},所以是O(n^2)

插入排序

直接插入排序（straight insertion sort）

假设数列第一个元素为已排序数列，剩余数列为未排序将待排序元素挨个插入到已排序数列中每次插入都必须保证数列是有序的，即通过比较和移动有序数列中的元素，将元素插入到合适的位置
思路：如同玩扑克牌一样，每次摸牌都将它与手中的牌比较，始终将牌放在比它大的牌前面，比它小的牌后面。这样当牌全部摸到手上后，就是一个有序的序列。从后往前找合适的位置。

function insertSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i-1]) {
//如果第i个数大于前一个数就不用判断了,因为前面都是有序数列,大于前一个数肯定比前面所有数都大,否则的话把这个数拿出来也就是赋值给temp,然后依次与前面的数比较,如果比前一个数小就让前一个数往后挪一位直到找到比temp小的位置放进去
      const temp = arr[i]
      let j = i;
      for(; j >= 1 && arr[j-1] > temp; j--) {
        arr[j] = arr[j-1]
      }
      arr[j] = temp
    }
  }
  return arr
}

希尔排序

希尔排序为一种缩减增量的插入排序,在每一组内采用直接插入排序方法，通过逐渐缩减增量直到为1，它是一种不稳定的排序算法，如何选取增量，目前还是一个数学难题，一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n^{3/2})

function shellSort(arr) {
  // 增量gap,逐步缩小增量，将列表分为gap组
  for(let gap = Math.floor(arr.length / 2); gap  > 0; gap = Math.floor(gap / 2)) {
    // 从第gap个元素，逐个对其所在分组进行直接插入排序操作
    for(let i = gap; i < arr.length; i++) {
        let j = i
        while(j - gap >= 0 && arr[j] < arr[j-gap]) {
          // j 和 j-gap为同一组
          swap(arr, j, j-gap)
          j -= gap
        }
    }
  }
  return arr
}

堆排序

将待排序序列构造为一个最大堆，将堆顶与堆尾进行交换，然后将原堆顶移除堆，加入到已排序序列，然后将交换后的堆更新为新的最大堆，一直重复操作。

function heapSort(arr) {
  // 将序列改造为最大堆
  for(let i = Math.floor(arr.length / 2); i > 0; i--) {
    // 初始化情况下只有前[arr.length / 2]向下取整的节点是非叶子节点，所以只需遍历有孩子的子树节点
    heapAdjust(arr, i, arr.length)
  }
  for(let i = arr.length; i > 1; i--) {
    swap(arr, 0, i) // 将堆顶元素与最后一位互换
    heapAdjust(arr, 0, i-i) // 除去最后一位，将剩余列表重新改造为最大堆
  }
}

// arr为arr[s:m]中除了arr[s]之外均满足最大堆堆的定义
function heapAdjust(arr, s, m) {
  const temp = arr[s]
  for (let j = 2*s; j <= m; j*=2) {
    // 找s的孩子2*s和2*s+1，不断向下筛选找出最大元素
    if(j < m && arr[j] < arr[j+1]) // 左孩子小于右孩子
      ++j
    if(temp >= arr[j]) // 发现还是原s最大直接退出
      break
    arr[s] = arr[j] // 如果发现s<j,则交换2者位置，包含下面的2行代码共同完成此功能
    s = j
  }
  arr[s] = temp
}

时间复杂度：构建堆的时间复杂度为O(n),第i次取堆顶元素重建需要O(\log(i))时间,并且需要取n-1次堆顶操作，重建堆的时间复杂度为O(n\log(n)),所有总体也是O(n\log(n))，它也是一种不稳定的排序方法

归并排序

示意图


mergeSort.png

python3 递归版1（不改变原数组）

def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(mergeSort(arr[:mid]), mergeSort(arr[mid:]))
# 容易理解版，合并2个有序数组
def merge(left, right):
    i, k = 0, 0
    arr = []
    while i < len(left) and k < len(right):
        if left[i] < right[k]:
            arr.append(left[i])
            i += 1
        elif left[i] == right[k]:
            # 先左后右保证顺序
            arr.append(left[i])
            arr.append(right[k])
            i += 1
            k += 1
        else:
            arr.append(right[k])
            k += 1
    for n in left[i:]:
        arr.append(n)
    for n in right[k:]:
        arr.append(n)
    return arr
# 不好理解版merge
def merge(left, right):
    i, k = 0, 0
    arr = []
    while i + k < len(left) + len(right):
        if k >= len(right) or (i < len(left) and left[i] < right[k]):
            arr.append(left[i])
            i += 1
        else:
            arr.append(right[k])
            k += 1
    return arr
a = mergeSort([4, 2, 5, 2])
print(a)

python3 递归版2（改变原数组）

def mergeSort(arr):
    if len(arr) <= 1:
        return
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    mergeSort(left)
    mergeSort(right)
    merge(left, right, arr)
def merge(left, right, arr):
    i = j = 0
    # 2中情况，要不left插入，要不right插入
    while i + j < len(arr):
        # 如果right已经排序完或者当left和right都未完同时left小于right时,left往后插入
        if j == len(right) or (i < len(left) and left[i] <= right[j]):
            arr[i+j] = left[i]
            i += 1
        else:
            arr[i+j] = right[j]
            j += 1
arr = [4, 2, 5, 2, 1, 10, 7]
mergeSort(arr)
print(arr)

python 迭代版(改变原数组)

def mergeSort(arr):
    l = 2
    # 归并的最后一次要小于 长度*2 -1
    while l < len(arr) * 2 - 1:
        k = l
        while k < len(arr) + l:
            left = arr[k-l: k-l//2]
            right = arr[k-l//2: k]
            # 对arr[k-l:k]排序
            merge(left, right, arr, k-l)
            k += l
        # 每次迭代*2
        l *= 2
# 合并2个有序数组
def merge(left, right, arr, start):
    i = j = 0
    # 2中情况，要不left插入，要不right插入
    while i + j < len(left) + len(right):
        # 如果right已经排序完或者当left和right都未完同时left小于right时,left往后插入
        if j == len(right) or (i < len(left) and left[i] <= right[j]):
            arr[start+i+j] = left[i]
            i += 1
        else:
            arr[start+i+j] = right[j]
            j += 1
a = [4, 2, 10, 3, 1, 2, 9, 8, 5, 3, 4]
mergeSort(a)
print(a)

时间复杂度O(n\log n),空间复杂度O(n+\log n),是一种稳定的排序算法

快速排序

通过一趟排序将待排序记录分割成独立的2部分，其中一部分记录的数均比另一部分的数小，然后对着2部分继续不断排序

python 递归版

def quickSort(arr):
    qSort(arr, 0, len(arr)-1)

def qSort(arr, start, end):
    if start < end:
        # mid位置已经排好序
        mid = partition(arr, start, end)
        qSort(arr, 0, mid-1)
        qSort(arr, mid+1, end)

# 这个算法有些难理解
def partition(arr, start, end):
    pivot = arr[start]
    # 从2端向中间扫描
    while start < end:
        # 当pivot < 右边时，不断向左递推
        while start < end and arr[end] >= pivot:
            end -= 1
        # 当发生 pivot >= 右边时，将这个数值与 pivot交换位置
        arr[start], arr[end] = arr[end], arr[start]
        # 注意：此时pivot已经换到了end的位置
        # 当左边 < pivot时，不断向右推进
        while start < end and arr[start] <= pivot:
            start += 1
        # 当发生pivot < 左边时，因为此前pivot发生了位置交换，已经被换到了end的位置，所以此时真实的情况也是将这个数值与 pivot交换位置
        arr[start], arr[end] = arr[end], arr[start]
    return start

a = [3, 4, 1, 2, 5]
# 第一次经过partition的a结果[2, 1, 3, 4, 5]
quickSort(a)
print(a)

优化 pivot 的选取，三数取中法

def partition(arr, start, end):
    # 左端三数取中，调整到左边
    mid = start + (end - start) // 2
    if arr[start] > arr[end]:
        arr[start], arr[end] = arr[end], arr[start] # 左端较小
    if arr[mid] > arr[end]:
        arr[mid], arr[end] = arr[end], arr[mid] # 中间较小
    if arr[mid] > arr[start]:
        arr[start], arr[mid] = arr[mid], arr[start] # 中间较小
    # 此时arr[start]已经是3个数中的中间数了

    pivot = arr[start]
    # 从2端向中间扫描
    while start < end:
        # 当pivot < 右边时，不断向左递推
        while start < end and arr[end] >= pivot:
            end -= 1
        # 当发生 pivot >= 右边时，将这个数值与 pivot交换位置
        arr[start], arr[end] = arr[end], arr[start]
        # 注意：此时pivot已经换到了end的位置
        # 当左边 < pivot时，不断向右推进
        while start < end and arr[start] <= pivot:
            start += 1
        # 当发生pivot < 左边时，因为此前pivot发生了位置交换，已经被换到了end的位置，所以此时真实的情况也是将这个数值与 pivot交换位置
        arr[start], arr[end] = arr[end], arr[start]
    return start

优化不必要的交换

def partition(arr, start, end):
    # 左端三数取中，调整到左边
    mid = start + (end - start) // 2
    if arr[start] > arr[end]:
        arr[start], arr[end] = arr[end], arr[start] # 左端较小
    if arr[mid] > arr[end]:
        arr[mid], arr[end] = arr[end], arr[mid] # 中间较小
    if arr[mid] > arr[start]:
        arr[start], arr[mid] = arr[mid], arr[start] # 中间较小
    # 此时arr[start]已经是3个数中的中间数了

    pivot = arr[start]
    # 从2端向中间扫描
    while start < end:
        # 当pivot < 右边时，不断向左递推
        while start < end and arr[end] >= pivot:
            end -= 1
        arr[start] = arr[end] # 采用替换代替交换
        # 当左边 < pivot时，不断向右推进
        while start < end and arr[start] <= pivot:
            start += 1
        arr[end] = arr[start] # 采用替换代替交换
    arr[start] = pivot # 还原原来的值
    return start

优化小数组时的排序，当数组很小（7或50）时，直接插入排序性能最好

maxLength = 7
def qSort(arr, start, end):
  if end - start > maxLength :
    mid = partition(arr, start, end)
    qSort(arr, 0, mid-1)
    qSort(arr, mid+1, end)
  else:
    insertSort(arr, start, end)

尾递归优化

maxLength = 7
def qSort(arr, start, end):
  if end - start > maxLength :
    while start < end:
      mid = partition(arr, start, end)
      qSort(arr, 0, mid-1)
      start = mid + 1 # 尾递归
  else:
    insertSort(arr, start, end)

快速排序的时间复杂度取决于递归数的深度，因此取决选取的partition部分，如果每次划分都很均匀则最小，平均时间复杂度O(n\log n),空间复杂度O(\log n)，是一种不稳定的排序算法

排序算法总结

sortType.png
sortCompare.png

相关文章

网友评论

      本文标题：主流排序算法

      本文链接：https://www.haomeiwen.com/subject/uuulhhtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|主流排序算法|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！