Just Do IT !

Python算法学习day3:快速排序(二)

Python算法
字数统计: 588阅读时长: 3 min
2020/01/16 Share

排序

(1) 取出一个数列中唯一一个奇数出现的数字

例如:
li = [1,2,1,3,2,1,1,2,2,3,3]
唯一一个奇数出现的数字为3

代码详细:

1
2
3
4
5
li = [1,2,1,3,2,1,1,2,2,3,3]
num = 0
for i in li:
	num = num ^ i #这里运用了一个异或符号的小技巧 当然只能在数列中只存在唯一一个数字才可使用
print(num)

(2) 快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quick_sort(li, left, right):
	if left < right:
		mid = partition(li, left, right)
		quick_sort(li, left, mid - 1)
		quick_sort(li, mid + 1, right)
def partition(li, left, right):
	tmp = li[left]
	while left < right:
		while left < right and li[right] >= tmp:
			right -= 1
		li[left] = li[right]
		while left < right and li[left] <= tmp:
			left += 1
		li[right] = li[left]
	li[left] = tmp
	return left

时间复杂度为O(nlogn)

如果出现最坏情况如[7,6,5,4,3,2,1]
优化代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def quick_sort(li, left, right):
	if left < right:
		mid = random_partition(li, left, right)
		quick_sort(li, left, mid - 1)
		quick_sort(li, mid + 1, right)
def partition(li, left, right):
	tmp = li[left]
	while left < right:
		while left < right and li[right] >= tmp:
			right -= 1
		li[left] = li[right]
		while left < right and li[left] <= tmp:
			left += 1
		li[right] = li[left]
	li[left] = tmp
	return left
def random_partition(li, left, right):
	i = random.randint(left, right)
	li[i], li[left] = li[left], li[i]
	partition(li, left, right)

(3) 快速排序 切片实现

1
2
3
4
5
6
7
8
9
def quick_sort(li):
	if len(li) < 2:
		return li
	tmp = li[0]
	left = [i for i in li[1:] if i <= tmp]
	right = [i for i in li[1:] if i > tmp]
	left = quick_sort(left)
	right = quick_sort(right)
	return left + [tmp] + right

(4) Leetcode912. 排序数组

给定一个整数数组 nums，将该数组升序排列。



示例 1：

输入：[5,2,3,1]
输出：[1,2,3,5]
示例 2：

输入：[5,1,1,2,0,0]
输出：[0,0,1,1,2,5]


提示：

1 <= A.length <= 10000
-50000 <= A[i] <= 50000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        #return self.quick_sort(nums, 0, len(nums) - 1)
        return self.quick_sort(nums)
    '''    
    def quick_sort(self, nums, left, right):
        if left > right:
            return 
    
        if left < right:
            mid = self.partition(nums, left, right)
            self.quick_sort(nums, left, mid-1)
            self.quick_sort(nums, mid+1, right)
        return nums

    def partition(self, nums, left, right):
        tmp = nums[left]
        while left < right:
            while left < right and nums[right] >= tmp:
                right -= 1
            nums[left] = nums[right]
            while left < right and nums[left] <= tmp:
                left += 1
            nums[right] = nums[left]
        nums[left] = tmp
        return left
    '''
    def quick_sort(self, nums):
        if len(nums) < 2:
            return nums
        tmp = nums[0]
        left = [i for i in nums[1:] if i <= tmp]
        right = [i for i in nums[1:] if i > tmp]
        left = self.quick_sort(left)
        right = self.quick_sort(right)
        
        return  left + [tmp] + right

原文作者：浩翰

原文链接：https://plutoacharon.github.io/2020/01/16/Python算法学习day3-快速排序-二/

发表日期：January 16th 2020, 8:48:05 pm

更新日期：January 17th 2020, 4:09:06 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 排序
    1. 1.1. (1) 取出一个数列中唯一一个奇数出现的数字
    2. 1.2. (2) 快速排序
    3. 1.3. (3) 快速排序 切片实现
    4. 1.4. (4) Leetcode912. 排序数组
Total : 190
2020
2019
CTF Liunx 高可用负载均衡 Java Hadoop Docker Esxi Dokcer Flume GitHub Kafka Golang Golang日志收集系统 Hbase Hive Git Kali Kubernetes Shell Python算法 Spark Sqoop Vmware 机器学习 Zookeeper PHP Hexo 安全 Python PySpark Maven 网络 数据采集 CDN AWD ZooKeeper
CTF Liunx Hadoop Docker GitHub Golang Golang日志收集系统 高可用负载均衡 Hive Java Kubernetes 其他 Python算法 Spark Vmware 机器学习 博客 Python 网络 CDN