ITPub博客

首页 > 应用开发 > IT综合 > 游戏陪玩系统源码中不同排序算法的实现方式

游戏陪玩系统源码中不同排序算法的实现方式

IT综合 作者:云豹科技程序员 时间:2021-10-26 16:34:43 0 删除 编辑

排序是游戏陪玩系统源码开发中经常会经历的事,为了实现方便,开发者往往会通过排序算法实现各个元素的排序,在游戏陪玩系统源码开发中,常见的排序算法有哪些呢?

1 内部排序

内部排序指待排序完全放在游戏陪玩系统源码内存中进行的排序过程,适合不太大的元素序列

  • 插入排序
  • 交换排序
  • 选择排序
  • 其他内部排序

1.1 插入排序

循环将待排序的一个元素插入到已排序的序列中

  • 直接插入排序
  • 折半插入排序
  • 希尔排序

1.1.1 直接插入排序

算法思想

  • 将原序列分为已排序与未排序的两部分
  • 外层循环遍历游戏陪玩系统源码整个序列,标记当前待插入元素
  • 内层循环遍历已排序序列,从有序表的尾部开始与当前值进行比较移动

算法实现

function insertSort(arr) {
    //遍历整个序列
    for (let i = 0; i < arr.length; i++) {
        //当前待插入值
        let temp = arr[i]
        //遍历已排序序列,待插入值小则与前值交换
        for (let j = i - 1; j >= 0 && arr[j] > temp; j--) {
            //解构赋值方式交换
            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        }
    }
    return arr
}

边找边移动

1.1.2 折半插入排序

算法思想

  • 与直接插入排序的思想基本一致,需要将游戏陪玩系统源码原序列分为已排序和未排序两部分
  • 不同的在于在比较时不从末尾以此比较,而是使用折半查找的方式查找排序位置

算法实现

function midInsertSort(arr) {
    //折半向下取整
    function absInt(a, b) {
        return Math.abs(parseInt((a + b) / 2))
    }
    for (let i = 1; i < arr.length; i++) {
        let temp = arr[i];
        let left = 0, right = i - 1, mid = absInt(left, right)
        let tag = 0
        //折半查找插入位置
        while (left < right) {
            if (temp > arr[mid]) {
                left = mid + 1
                mid = absInt(left, right)
            } else if (temp < arr[mid]) {
                right = mid - 1
                mid = absInt(left, right)
            } else break
        }
        //保证稳定性
        if (temp >= arr[mid]) tag = 1
        //移动
        for (let move = mid + tag; move <= i; move++) {
            [arr[move], temp] = [temp, arr[move]]
        }
    }
    return arr
}

其核心是折半查找(也称为二分查找),先通过查找算法找到插入位置再统一移动

1.1.3 希尔排序

算法思想

  • 对游戏陪玩系统源码原序列按照一个增量(间隔)进行分组
  • 对已分组的子序列使用直接插入排序
  • 减小增量再分组然后排序,以此类推
  • 当增量为1时,使用直接插入排序返回结果

算法实现

function shelltSort(arr) {
    //定义初始增量
    let gap = Math.floor(arr.length / 2)
    //增量减至1时执行最后一次直接插入排序
    while (gap >= 1) {
        //子序列的直接插入排序
        for (let i = gap; i < arr.length; i += gap) {
            let temp = arr[i]
            for (let j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                [arr[j], arr[j + gap]] = [arr[j + gap], arr[j]]
            }
        }
        //增量减半
        gap = Math.floor(gap / 2)
    }
    return arr
}

希尔排序的核心排序算法还是直接插入排序,先按照增量进行分组,组内使用直接插入排序,不断缩小增量重分组再排序,至到增量缩小为1进行最后一次直接插入排序
如果gap为1其排序的部分就是上面介绍的直接插入排序

1.2 交换排序

  • 冒泡排序
  • 快速排序

1.2.1 冒泡排序

算法思想

  • 相邻两两比较交换位置,先将最大或最小的值交换至顶端
  • 外层的一次循环可以确定一个最大或最小值
  • 根据已经确定的值不断缩小比较区间,最终返回结果

该算法是游戏陪玩系统源码开发中最简单最暴力性能最差的一种排序算法

算法实现

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

通过不断交换,每一趟确定一个值的位置 下一趟该值不再参与排序

1.2.2 快速排序

算法思想

  • 从序列中选取一个值作为基准
  • 通过不断的交换,将所有元素中比基准小或大的值放在其两侧
  • 这样就确定了一个值的位置,称为一趟换分
  • 再递归的将两侧的区间进行同样的划分,最终得到排序的序列

算法实现

function quickSort(arr, low, high) {
    //确定两侧指针
    low = typeof low != 'number' ? 0 : low
    high = typeof high != 'number' ? arr.length - 1 : high;
    //指针重合结束循环
    if (low < high) {
        //根据基准进行划分,返回基准坐标
        let pivotIndex = partition(arr, low, high)
        //基准左侧递归
        quickSort(arr, low, pivotIndex - 1)
        //基准右侧递归
        quickSort(arr, pivotIndex + 1, high)
    }
    return arr
}
function partition(arr, low, high) {
    //以子序列起点为基准
    let pivot = arr[low]
    //指针重合结束循环
    while (low < high) {
        //从右侧寻找小于等于基准的值
        while (low < high && arr[high] > pivot) --high
        //将小于等于基准的值前移
        arr[low] = arr[high]
        //从左侧找大于基准的值
        while (low < high && arr[low] <= pivot) ++low
        //将大于基准的值后移
        arr[high] = arr[low]
    }
    //将基准放入重合的指针左边
    arr[low] = pivot
    //返回基准坐标 - 左侧均小于基准,右侧均大于基准
    return low
}

上述快速排序算法是游戏陪玩系统源码中经典的以子序列为基准来递归划分 也可以以中间值或尾部为基准进行划分,实现不太相同,思想基本一致

1.3 选择排序

  • 简单选择排序
  • 堆排序

1.3.1 简单选择排序

算法思想

  • 外层遍历确定位置
  • 内层遍历寻找子序列中最大或最小的值

也是游戏陪玩系统源码中一种简单的暴力的性能差的排序算法,时间复杂度始终是O(n2)

算法实现

function selectSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let index = i
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[index]) {
                index = j
            }
        }
        [arr[i], arr[index]] = [arr[index], arr[i]]
    }
    return arr
}

1.3.2 堆排序

算法思想

  • 根据原序列创建一个完全二叉树
  • 将完全二叉树重排为堆(父节点大于/小于子节点)
  • 将堆首和堆尾互换,堆首为最大/最小值,将其选出,堆尺寸缩小1
  • 将互换后的完全二叉树再重排位堆
  • 重复3 4 只到堆的尺寸为1

算法实现

function heapSort(arr) {
    let len = arr.length
    //创建一个大根堆 - 从最后一个非叶子节点开始,保证能比较交换出最大值
    for (let i = Math.floor(len / 2 - 1); i >= 0; i--) {
        heapify(arr, i, len)
    }
    //交换当前堆顶与堆尾,堆尺寸减1,调整堆
    for (let i = arr.length - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]]
        len--
        //从对顶调整即可,次大值就是其左右子节点中的一个
        heapify(arr, 0, len)
    }
    return arr
}
function heapify(arr, i, len) {
    //确定父节点的两个子节点下标
    let left = i * 2 + 1,
        right = i * 2 + 2,
        largest = i
    //找出父节点、左右子节点中的最大值,并标记下标
    if (left < len && arr[left] > arr[largest]) largest = left
    if (right < len && arr[right] > arr[largest]) largest = right
    //最大值不是父节点
    if (largest !== i) {
        //交换父节点与子节点的值
        [arr[largest], arr[i]] = [arr[i], arr[largest]]
        //子节点向下继续调整
        heapify(arr, largest, len)
    }
}

该算法的核心在堆的调整 创建堆时从最后一个非叶子节点开始比较交换 首尾互换后,从首节点开始向下比较交换一个方向即可

1.4 其他内部排序

  • 基数排序:根据键值的每位数据来分配桶
  • 桶排序:每个桶存储一定范围的数值
  • 计数排序:每个桶只存储单一键值

这三种排序算法都是基于桶,将数值进行分类后再排序 这里仅介绍基数排序的方式

1.4.1 基数排序

算法思想

  • 从个位开始按顺序入桶
  • 从桶号最小的开始,先进桶的先出桶
  • 再从十位开始入桶出桶的操作,以此类推

算法实现

function radixSort(arr, maxDigit) {
    //初始化容器,进制,被除数
    let counter = [],
        mod = 10,
        dev = 1
    //根据最大位数进行遍历进桶
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        //根据当前位按数据进桶
        for (let j = 0; j < arr.length; j++) {
            let bucket = parseInt((arr[j] % mod) / dev)
            if (counter[bucket] == null) {
                counter[bucket] = []
            }
            counter[bucket].push(arr[j])
        }
        let pos = 0
        //从小为桶号开始,先进桶的先出桶
        for (let z = 0; z < counter.length; z++) {
            let value = null
            if (counter[z] != null) {
                while ((value = counter[z].shift()) != null) {
                    arr[pos++] = value
                }
            }
        }
    }
    return arr
}

2 外部排序

  • 归并排序
  • 多路归并排序

2.1 归并排序

算法思想

  • 自上而下将游戏陪玩系统源码原序列递归的分成两部分,直至左右长度为1
  • 双指针法逐次比较两个序列的值,小值添加至合并空间并移动其指针
  • 将另一序列未添加到合并空间的剩余值与合并空间进行拼接
  • 自下而上的迭代2 3进行合并,最终完成顶层左右序列的合并

算法实现

function mergeSort(arr) {
    //递归分治 - 直到长度为1
    if (arr.length > 1) {
        let middle = Math.floor(arr.length / 2),
            left = mergeSort(arr.slice(0, middle)),
            right = mergeSort(arr.slice(middle))
        arr = merge(left, right)
    }
    return arr
}
function merge(left, right) {
    //定义两个指针,在左右序列中移动
    let i = 0,
        j = 0,
        result = []
    //双指针法依次比较两个序列的值,
    //选择小值添加到result中,并移动其指针
    //有一个移动结束循环结束
    while (i < left.length && j < right.length) {
        result.push(left[i] < right[j] ? left[i++] : right[j++])
    }
    //将另一个指针未移动结束序列的剩余值与result进行拼接
    return result.concat(i < left.length ? left.slice(i) : right.slice(j))
}

此算法使用的是自上而下的递归,递归的深度较深 也可以使用自下而上的迭代算法

2.2 多路归并排序

  • 循环遍历
  • 最小堆K路归并排序
  • 失败树K路归并排序

后续单独介绍

以上便是“游戏陪玩系统源码开发,常见的排序算法有哪些?”的全部内容,希望对大家有帮助。

本文转载自网络,转载仅为分享干货知识,如有侵权欢迎联系云豹科技进行删除处理
原文链接:https://segmentfault.com/a/1190000040854168


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69996194/viewspace-2839377/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2021-03-10

  • 博文量
    308
  • 访问量
    90193