排序&异或

今天练习了各种排序，总结了可以用异或解决的题目特征

leetcode(排序）:

https://leetcode-cn.com/problems/sort-an-array/submissions/

桶排序

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if not nums or len(set(nums)) == 1 :
            return nums
        max_num = max(nums)
        min_num = min(nums)
        bucket_num = len(nums)
        # init bucket
        bucket_list = [[] for _ in range(bucket_num)]
        # select
        for num in nums:
            bucket_list[int((num-min_num)*(len(nums)-1)/(max_num-min_num))].append(num)
        # sort
        result = []
        for bucket in bucket_list:
            if bucket:
                bucket.sort()
        for bucket in  bucket_list:
            for num in bucket:
                result.append(num)
        return result

快速排序

双边循环法

class Solution:
    def quick_sort(self,nums,start,end):
        if start >= end:
            return
        mid = self.sort(nums,start,end)
        self.quick_sort(nums,start,mid-1)
        self.quick_sort(nums,mid+1,end)

    def sort(self,nums,start,end):
        if start >= end:
            return
        mark = start
        while start < end:
            while nums[end] > nums[mark] and start < end:
                end -= 1
            while nums[start] <= nums[mark] and start < end:
                start += 1
            if start < end:
                nums[end] ^= nums[start]
                nums[start] ^= nums[end]
                nums[end] ^= nums[start]
        if nums[mark] != nums[end]:
            nums[mark] ^= nums[end]
            nums[end] ^= nums[mark]
            nums[mark] ^= nums[end]
        return end

    def sortArray(self, nums: List[int]) -> List[int]:
        # 快排
        self.quick_sort(nums,0,len(nums)-1)
        return nums

单边循环法

class Solution:
    def sort(self,nums,start,end):
        if start >= end:
            return
        mark = start
        for cnt in range(start+1,end+1):
            if nums[cnt] < nums[start]:
                mark += 1
                if mark != cnt:
                    nums[mark] ^= nums[cnt]
                    nums[cnt] ^= nums[mark]
                    nums[mark] ^= nums[cnt] 
        if mark != start:
            nums[mark] ^= nums[start]
            nums[start] ^= nums[mark]
            nums[mark] ^= nums[start] 
        self.sort(nums,start,mark-1)
        self.sort(nums,mark+1,end)

    def sortArray(self, nums: List[int]) -> List[int]:
        # 快排
        self.sort(nums,0,len(nums)-1)
        return nums

非递归

class Solution:
    def sort(self,nums,start,end):
        mark = start
        for cnt in range(start+1,end+1):
            if nums[cnt] < nums[start]:
                mark += 1
                if mark != cnt:
                    nums[mark] ^= nums[cnt]
                    nums[cnt] ^= nums[mark]
                    nums[mark] ^= nums[cnt] 
        if mark != start:
            nums[mark] ^= nums[start]
            nums[start] ^= nums[mark]
            nums[mark] ^= nums[start] 
        return mark

    def sortArray(self, nums: List[int]) -> List[int]:
        # 快排
        stack = []
        stack.append(&#123;"start":0,"end":len(nums)-1&#125;)
        while(stack):
            dic = stack.pop()
            mark = self.sort(nums,dic["start"],dic["end"])
            if dic["start"] < mark-1:
                stack.append(&#123;"start":dic["start"],"end":mark-1&#125;)
            if dic["end"] > mark+1:
                stack.append(&#123;"start":mark+1,"end":dic["end"]&#125;)


        return nums

区间优化后的鸡尾酒排序

class Solution:

    def sortArray(self, nums: List[int]) -> List[int]:
        # 鸡尾酒排序
        right_border = len(nums)-1
        left_border = 0
        for i in range(len(nums)//2):
            not_sorted = True
            # 奇数轮
            last_change_index = right_border-1
            for j in range(left_border,right_border):
                if nums[j] > nums[j+1]:
                    nums[j] ^= nums[j+1]
                    nums[j+1] ^= nums[j]
                    nums[j] ^= nums[j+1]
                    not_sorted = False
                    last_change_index = j 
            right_border = last_change_index
            if not_sorted:
                break
            not_sorted = True
            # 偶数轮
            last_change_index = left_border+1
            for j in range(right_border,left_border,-1):
                if nums[j] < nums[j-1]:
                    nums[j] ^= nums[j-1]
                    nums[j-1] ^= nums[j]
                    nums[j] ^= nums[j-1]
                    not_sorted = False
                    last_change_index = j 
            left_border = last_change_index
            if not_sorted:
                break
        return nums

---

异或

知识点

1. 相同为0，不同为1（真值表）
2. 0异或任何一个数还是这个数本身
3. 一个数异或其本身为0

可以用异或解决的题目特征

存在并且只有一个数字会重复奇数次，要找出这个数字是什么

解释

1. 出现偶数次的数字异或结果为0（知识点3）
2. 异或满足交换律，将所有数字异或起来的值为出现奇数次的数字（知识点2）