最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

最新消息：位运算在排序算法中的运用

来源：博客园


(资料图片仅供参考)

常规选择排序

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}

异或是如何实现值交换的

异或的性质

  • 满足交换律和结合律

即

ab=ba

abc=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个数，其中除了两个数出现奇数次，其他数都出现了奇数次，现在找出这两个数

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]}

关键词：