位運算在排序演算法中的運用-有解無憂

常規選擇排序

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個數，其中除了兩個數出現奇數次，其他數都出現了奇數次，現在找出這兩個數

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/553442.html

標籤：其他

上一篇：選擇排序演算法之泛型優化

下一篇：返回列表