22-算法-位运算实现的快速排序算法

算法位运算快速排序异或

发布时间 : 2020-07-08 11:58

字数:502 阅读 :

评论:

排序算法用异或实现
1. 1.什么是异或

排序算法用异或实现

1.什么是异或

异或就是当两个数转换成二进制后，进行位运算，如果对应位相同就为0，不同就为1

举例如下

//1.a=1 b=2
//2.对应的a转换成二进制位0 1； b转换成二进制为 1 0
//3.如果将a^b的值用c二进制保存起来就是c --> 1 1
//4.我们将c异或其中任意一个数，得到的就是与之对应的另外一个数
//5 比如c^a  得到的是b的值，

//原理就是利用异或的特点：两数异或后的结果再异或其中一数，得到的是另外一个数字

//验证代码如下

var a = 1
var b= 2
console.log(“交换前的a:”+ a,”交换前的b:”+b)
//a存储的是a^b的中间值
a = a^b
//用a^b的中间值再来^ b，得到的是a,将a赋值给b
b = a^b
//b保存的是a的值，b^a，实际上是a^ 第一行的a保存的中间值，b^a————》得到b，再将b的值赋值给a
a = b^a
console.log(“交换后的a:”+ a,”交换后的b:”+b)

* 结果如下
![image.png](https://upload-images.jianshu.io/upload_images/22769532-c2bc2992b530574d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
## 2.下面就开始进入正题，快速排序位运算
```js
const arr = [1,2,5,7,2,3,5]
  let len = arr.length
  let i = 0
  var j = 0
  while(i < len){
    //外层循环遍历第一行
    j = i
    while(j < len){
      //内层循环遍历i后面的元素，查看是否有比当前元素小的，有的话就交换数据
      if(arr[j] < arr[i]){
        arr[i] = arr[i] ^ arr[j]
        arr[j] = arr[i] ^ arr[j]
        arr[i] = arr[j] ^ arr[i] 
      }
      j++
    }
    i++
  }
  console.log(arr.toString())

通过这个题，可以提高原有选择排序的一个效率，位运算是比创建一个新的中间值来保存变量效率要更高。这里也可以回忆一下快速排序的一个实现方式

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1371769065@qq.com