时间复杂度和简单排序

Posted on | In | | 阅读数

时间复杂度和简单排序

2022.8.26

b站 算法大神左神（左程云）带你一周刷爆LeetCode，数据结构算法-leetcode真题解析 P2

异或

异或性质：

  • 0 ^ N = N, N ^ N = 0
  • 满足交换律、结合律 a ^ b = b ^ a ， a ^ b ^ c = a ^ (b ^ c)
  • 同一批数异或起来，无论顺序，结果相同

swap交换

异或可以用来交换两个变量的值

1
2
3
a = a ^ b
b = a ^ b
a = a ^ b

（前提是 两个变量在内存里是两个独立区域）

快排

图解快速排序

runoob 快速排序

https://www.geeksforgeeks.org/quick-sort/

http://data.biancheng.net/view/117.html

https://www.cnblogs.com/MOBIN/p/4681369.html

挖空，填空，

从右到左，遇到比基准小的就往靠左的空位放，然后自己空出来；

再从左到右，遇到比御准大的就往靠右的空位放，然后自己空出来；

再一直执行上述两个步骤，直到不满足左指针<右指针；

感觉就是小的一直填在左边，大的也一直填在右边；

img