01.快排

1.1 快排-递归实现

**注：**快排代码实现（类似于二叉树 递归调用）----右手左手一个慢动作，左手右手一个慢动作重播

• 空间复杂度 O(1)

#!/usr/bin/env python
# -*- coding:utf-8 -*-
import random
import sys
sys.setrecursionlimit(10000000)             #设置系统最大递归深度

def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)    # mid返回的是上一个用来排序那个数的下标
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1,right)

# 每执行一次partition函数都可以实现将某个数左边都比这个数小右边都比这个数大
def partition(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:     # 从右向左找小于tmp的数放到左边空位置
            right -= 1
        data[left] = data[right]                       # 将右边小于tmp值得数放到左边空位置
        while left < right and data[left] <= tmp:      # 从左向右找到大于tmp的值放到右边空位置
            left += 1
        data[right] = data[left]                       # 将右边大于tmp值得数放到右边空位置
    data[left] = tmp
    return left

data = list(range(100))
random.shuffle(data)                                 #将有序列表打乱
quick_sort(data, 0, len(data) - 1)
print(data)

1.2 golang递归

package main
import (
	"fmt"
)

func main() {
	var arr = []int{9, 4, 7, 6, 8, 3, 2, 5, 1}
	fmt.Println("before", arr)      // before [9 4 7 6 8 3 2 5 1]
	quickSort(arr, 0, len(arr)-1)
	fmt.Println("after ", arr)      // after  [1 2 3 6 8 7 4 5 9]
}

func quickSort(data []int,left,right int)  {
	if left < right{
		mid := partition(data, left, right)
		quickSort(data, left, mid-1)
		quickSort(data, mid+1 ,right)
	}
}

func partition(data []int, left,right int) (int)  {
	tmp := data[left]
	for left < right {
		for left< right && data[right] >= tmp {
			right--
		}
		data[left] = data[right]
		for left< right && data[right] <= tmp {
			left++
		}
		data[right] = data[left]
	}
	data[left] = tmp
	return left
}

1.3 快排-简单实现

• 空间复杂度高（O(N)）：需要开辟新的列表存储

#! /usr/bin/env python
# -*- coding: utf-8 -*-
def quick(list):
    if len(list) < 2:
        return list

    tmp = list[0]  # 临时变量 可以取随机值
    left = [x for x in list[1:] if x <= tmp]  # 左列表
    right = [x for x in list[1:] if x > tmp]  # 右列表
    return quick(left) + [tmp] + quick(right)

li = [4,3,7,5,8,2]
print quick(li)  # [2, 3, 4, 5, 7, 8]

#### 对[4,3,7,5,8,2]排序
'''
[3, 2] + [4] + [7, 5, 8]                 # tmp = [4]
[2] + [3] + [4] + [7, 5, 8]              # tmp = [3] 此时对[3, 2]这个列表进行排序
[2] + [3] + [4] + [5] + [7] + [8]        # tmp = [7] 此时对[7, 5, 8]这个列表进行排序
'''