位运算在排序算法中的运用-Toy模板网

这篇具有很好参考价值的文章主要介绍了位运算在排序算法中的运用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

常规选择排序

function selectSort(arr: Number[]) {
    //先排除一些不需要排序的情况
    if (!arr || arr.length < 2) {
        return arr
    }
    let a =arr
    //外层循环控制循环n-1次
    for (let i = 0; i < a.length-1; i++) {
        let index = i
        //内层循环获取该轮循环中最小值的下标
        for (let j = i + 1; j < a.length; j++) {
            if (a[j] < a[index]) {
                index = j
            }

        }
        if(i!==index){
            let temp = a[i]
            a[i]=a[index]
            a[index]=temp
        }
    }


    return a



}

使用位运算的选择排序

function selectSortUseByte(arr) {
    if (!arr || arr.length < 2) {
        return arr
    }

    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i; j < arr.length; j++) {
            if (arr[j] < arr[i]) {
                swap(arr, i, j)
            }
        }
    }
    //交换值时使用位运算
    function swap(arr, a, b) {
        arr[a] = arr[a] ^ arr[b]
        arr[b] = arr[a] ^ arr[b]
        arr[a] = arr[a] ^ arr[b]
    }
    return arr
}

异或是如何实现值交换的

异或的性质

满足交换律和结合律

即

a^b=ba

a^bc=a^(bc)

且

a^a=0

0^a=a

function swap(arr, a, b) {
        arr[a] = arr[a] ^ arr[b]
        //此时arr[a]=arr[a]^arr[b],执行下面的运算后，arr[b]=arr[a]^arr[b]^arr[b]=arr[a]^0=arr[a]
        arr[b] = arr[a] ^ arr[b]
        //执行下面的运算，arr[a]=(arr[a]^arr[b])^arr[a]=arr[b]
        arr[a] = arr[a] ^ arr[b]
        //这样就巧妙地将两个值进行了交换，且没有开辟新的存储空间
    }

拓展

找出唯一的出现奇数次的数

现有N个数，除了唯一的一个数出现的次数是奇数，其他的均是出现了偶数次的数，现在请编程找出这个出现奇数次的数

/**
* 
* @param arr 要处理的数组
* @returns 返回出现奇数次的数
*/

function getOddNubmer(arr){
   let r=0
   //挨个遍历数组里面的数进行异或操作，出现偶数次的数最终会被异或成0，最后剩下的就是出现偶数次的数
   for(let k of arr){
       r^=k
   }
   return r
}

找出数组中出现奇数次的两个数

N个数，其中除了两个数出现奇数次，其他数都出现了奇数次，现在找出这两个数文章来源地址https://www.toymoban.com/news/detail-458983.html

function getOddNumberTwo(arr) {
    let r = 0
    //假设这两个数是a和b,此处获取a^b
    for (let k of arr) {
        r ^= k
    }
    //获取a和b中为1的最低位
    let rightone = r & (~r + 1)
    let first = 0
    for (let k of arr) {
        //筛选出满足rightone的数据，其中将只包含a和b其中一个，进行异或操作后就可得到其中一个数
        if ((k & rightone) == 0) {
            first ^= k
        }
    }
    //将a和b异或的和再与第一个数进行异或运算，就得到了第二个数
    let second = r^first

    return [first,second]
}

到了这里，关于位运算在排序算法中的运用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！