位运算在排序算法中的运用
常规选择排序
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]
}