<jupyter_start><jupyter_text>冒泡排序![application](http://img.foshanplus.com/algo/bubble_sort.gif)<jupyter_code>def bubble_sort(arr):
    """冒泡排序"""
    number = len(arr)   # 数组的长度
    has_changed = True  # 一趟遍历中是否发生过交换
    x = 0
    while has_changed:
        has_changed = False   # 每次循环复位
        for i in range(1, number-x):  # 每次循环减少一次，因为后面的数列已经是有序
            if arr[i-1] > arr[i]:
                arr[i-1], arr[i] = arr[i], arr[i-1] # 交换位置
                has_changed = True
        x += 1
    return arr
print(bubble_sort([4,5,7,6,3,2,1]))<jupyter_output>[1, 2, 3, 4, 5, 6, 7]<jupyter_text>三角形大比拼<jupyter_code>def largest_perimeter(arr):
        """
        寻找最大周长的三角形
        输入：一组边长数据:list
        """
        arr = bubble_sort(arr)  # 用冒泡排序
        res = 0
        for i in range(len(arr)-1, 1, -1):  # 从大到小遍历, 
            if arr[i-2] + arr[i-1] > arr[i]: # 满足三角形条件
                res = arr[i-2] + arr[i-1] + arr[i]
                print('三角形的周长是{}, 三条边长度分别是{},{},{}'.format(
                    res, arr[i], arr[i-1], arr[i-2]))
                break   # 已经找到结果不需要继续，跳出循环
        if res == 0:
            print("没有找能够组合三角形的棍子")
largest_perimeter([4,14,9,5,2])
largest_perimeter([20,10,1,2,7])
largest_perimeter([233,120,747,75,67,336,221,845,780,403])
 def largest_perimeter_2(arr):
        """寻找最大周长的三角形，优化排序过程，一边排序一边寻找答案"""
        if len(arr) < 3:
            print("数据不够，至少有三个元素！")
        else:
            max_index = len(arr) -1  # 数组最大下标
            res = 0                  # 三角形周长
            # 冒泡排序
            for i in range(max_index):
                for j in range(max_index-i):
                    if arr[j] > arr[j+1]:   # 相邻元素比较，交换位置
                        arr[j], arr[j+1] = arr[j+1], arr[j]
                if i >= 2: # 从大到小，找到三个有序元素后，开始尝试组合三角形
                    if arr[max_index - i] + arr[max_index-i + 1] > arr[max_index - i + 2]:
                        res = arr[max_index - i] + arr[max_index-i + 1] + arr[max_index - i + 2]
                        print('三角形的周长是{}, 三条边长度分别是{},{},{}'.format(
                            res, arr[max_index - i], arr[max_index-i + 1], arr[max_index - i + 2]))
                        return
            if arr[0] + arr[1] > arr[2] and res == 0: # 上面少比较了最后3个元素
                res = arr[0] + arr[1] + arr[2]
                print('三角形的周长是{}, 三条边长度分别是{},{},{}'.format(
                            res, arr[0], arr[1], arr[2]))
                return
            if res == 0:
                print("没有找能够组合三角形的棍子")
largest_perimeter_2([4,14,9,5,2])
largest_perimeter_2([20,10,1,2,7])
largest_perimeter_2([233,120,747,75,67,336,221,845,780,403])<jupyter_output>三角形的周长是11, 三条边长度分别是2,4,5
没有找能够组合三角形的棍子
三角形的周长是2372, 三条边长度分别是747,780,845<jupyter_text>选择排序![application](http://img.foshanplus.com/algo/selection_sort.gif)<jupyter_code>def selection_sort(arr):
    """选择排序"""
    for i in range(len(arr)):
        min_index = i   # 初始化下标，以无序序列的第一个元素为开始
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]: # 从待排序序列中找最小值
                min_index = j  # 把最小值下标记录下来
        arr[min_index], arr[i] = arr[i], arr[min_index] # 当前位置元素交换位置
    return arr
print(selection_sort([4,5,7,6,3,2,1]))<jupyter_output>[1, 2, 3, 4, 5, 6, 7]<jupyter_text>稳定性比较<jupyter_code>def name_bubble_sort(arr):
    """冒泡排序"""
    number = len(arr)   # 数组的长度
    has_changed = True  # 一趟遍历中是否发生过交换
    x = 0
    while has_changed:
        has_changed = False   # 每次循环复位
        for i in range(1, number-x):  # 每次循环减少一次，因为后面的数列已经是有序
            if arr[i-1][0] > arr[i][0]: # 只是比较首字母
                arr[i-1], arr[i] = arr[i], arr[i-1] # 交换位置
                has_changed = True
        x += 1
    return arr
def name_selection_sort(arr):
    """选择排序"""
    for i in range(len(arr)):
        min_index = i   # 初始化下标，以无序序列的第一个元素为开始
        for j in range(i + 1, len(arr)):
            if arr[j][0] < arr[min_index][0]: # 从待排序序列中找最小值，只比较首字母
                min_index = j  # 把最小值下标记录下来
        arr[min_index], arr[i] = arr[i], arr[min_index] # 当前位置元素交换位置
#         print(arr)
    return arr
data = ['zhaosi','lili','chenqiang','liming','zhangxiaofei']
print('冒泡排序',name_bubble_sort(data))
data = ['zhaosi','lili','chenqiang','liming','zhangxiaofei']
print('选择排序',name_selection_sort(data))

data2 = ['chenqiang','zhaosi','lili','zhangxiaofei','liming']
print('冒泡排序', name_bubble_sort(data2))
data2 = ['chenqiang','zhaosi','lili','zhangxiaofei','liming']
print('选择排序',name_selection_sort(data2))<jupyter_output>冒泡排序 ['chenqiang', 'lili', 'liming', 'zhaosi', 'zhangxiaofei']
选择排序 ['chenqiang', 'lili', 'liming', 'zhaosi', 'zhangxiaofei']
冒泡排序 ['chenqiang', 'lili', 'liming', 'zhaosi', 'zhangxiaofei']
选择排序 ['chenqiang', 'lili', 'liming', 'zhangxiaofei', 'zhaosi']<jupyter_text>插入排序![application](http://img.foshanplus.com/algo/insertion_sort.gif)<jupyter_code>def insertion_sort(arr):
    """直接插入排序"""
    for i in range(len(arr)): 
        key = arr[i]  # 暂存当前元素值
        position = i       # 记录位移位置
        while position > 0 and key < arr[position - 1] :
            arr[position] = arr[position - 1]
            position -= 1  # 位移多一次，下标值减一
        arr[position] = key # 把之前元素插入到这个位置
    return arr
print(insertion_sort([4,5,7,6,3,2,1]))
def binary_sertion_sort(arr):
    """折半插入排序"""
    for i in range(len(arr)):
        key = arr[i]         # 暂存当前元素值
        position_low = 0     # 有序序列第一位元素下标
        position_hight = i-1 # 有序序列末位元素下标
        while position_low <= position_hight:
            mid = (position_low + position_hight) // 2  # 中间元素下标
            if key > arr[mid]:
                position_low = mid + 1   # 看中间位置右半部分
            else:
                position_hight = mid - 1  # 看中间位置左半部分
        # 找到插入位置后，下标值为position_low(mid值也相同)
        for j in range(i, position_low, -1):
            arr[j] = arr[j - 1]   # 向右位移，腾出空间插入新元素
        arr[position_low] = key   # 插入新元素
    return arr
print(binary_sertion_sort([4,5,7,6,3,2,1]))<jupyter_output>[1, 2, 3, 4, 5, 6, 7]<jupyter_text>归并排序![application](http://img.foshanplus.com/algo/merge_sort.gif)<jupyter_code>def merge_sort(arr):
    """归并排序"""
    if len(arr) <= 1:    # 不多于一个元素，最小的子序列，不用继续拆分
        return arr
    mid = len(arr) // 2  # 找到序列中间位置的下标  
    # 中间分开左右两个子序列，子序列递归调用merge_sort()函数进行归并排序
    left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
    # 返回的结果是有序的子序列，然后把子序列通过merge()函数合并子序列
    return merge(left, right)

def merge(left, right):
    """左右子序列合并"""
    merged = left + right  # 创建一个和左右子序列相同大小的列表
    left_positon, right_positon = 0, 0
    while left_positon < len(left) and right_positon < len(right):
        # 对左右子序列每个元素进行比较排序，放到新的有序序列里面
        if left[left_positon] <= right[right_positon]:
            merged[left_positon+right_positon]=left[left_positon]
            left_positon += 1
        else:
            merged[left_positon + right_positon] = right[right_positon]
            right_positon += 1
    # 如果某一边子序列已经排序结束，那么把另外一边的子序列直接加到新的序列后面
    for left_positon in range(left_positon, len(left)):
        merged[left_positon + right_positon] = left[left_positon]
    for right_positon in range(right_positon, len(right)):
        merged[left_positon + right_positon] = right[right_positon]
    return merged
print(merge_sort([4,5,7,6,3,2,1]))<jupyter_output>[1, 2, 3, 4, 5, 6, 7]<jupyter_text>谁是大富翁<jupyter_code>def merge_sort_2(arr):
    """归并排序"""
    if len(arr) <= 1:    # 不多于一个元素，最小的子序列，不用继续拆分
        return arr
    mid = len(arr) // 2  # 找到序列中间位置的下标  
    # 中间分开左右两个子序列，子序列递归调用merge_sort()函数进行归并排序
    left, right = merge_sort_2(arr[:mid]), merge_sort_2(arr[mid:])
    # 返回的结果是有序的子序列，然后把子序列通过merge()函数合并子序列
    return merge_2(left, right)

def merge_2(left, right):
    """左右子序列合并"""
    merged = left + right  # 创建一个和左右子序列相同大小的列表
    left_positon, right_positon = 0, 0
    
    while left_positon < len(left) and right_positon < len(right):
        # 判断元素的位置
        if compare(left[left_positon],right[right_positon]): # 和上面算法区别就是这里，改变了规则
            merged[left_positon+right_positon]=left[left_positon]
            left_positon += 1
        else:
            merged[left_positon + right_positon] = right[right_positon]
            right_positon += 1
    # 如果某一边子序列已经排序结束，那么把另外一边的子序列直接加到新的序列后面
    for left_positon in range(left_positon, len(left)):
        merged[left_positon + right_positon] = left[left_positon]
    for right_positon in range(right_positon, len(right)):
        merged[left_positon + right_positon] = right[right_positon]
    return merged

def compare(a,b):
    """
    比较两个元素的最高位数字大小，最高位相同则比较次高位，
    若一边位数不足，可以继续使用最后一位的数字来比较
    返回结果：
    False代表a<=b,
    True代表a>b
    """
    if len(b) > len(a): # 找到比较长的字符串
        max_index = len(b) 
    else:
        max_index = len(a)
    
    # 字符串默认是可以通过下标来表示单个字符
    for position in range(max_index):
        if position >= len(a):  # -1表示倒数第一的元素
            position_a = -1
        else:
            position_a = position
        if position >= len(b):
            position_b = -1
        else:
            position_b = position
        # 比较数字
        if b[position_b] > a[position_a]:
            return False
        elif b[position_b] < a[position_a]:
            return True
    else:
        return False

def be_rich(input_arr):
    """主程序"""
    for i in range(len(input_arr)):
        input_arr[i] = str(input_arr[i])  # 把数值变成字符串
    result = merge_sort_2(input_arr)      # 用归并排序获取有序列表 
    print("最大数值为：", "".join(result))
be_rich([4,51,71,63,31,23,1,33,3])
be_rich([9,92,6,96211,111,33,3])
be_rich([0,0,0,0,0])
def be_rich_2(input_arr):
    """主程序"""
    all_zero = not any(input_arr) # 增加判断特殊值判断
    if all_zero:
        print("最大数值为0，欺骗人的！", )
        return
    for i in range(len(input_arr)):
        input_arr[i] = str(input_arr[i])  # 把数值变成字符串
    result = merge_sort_2(input_arr)      # 用归并排序获取有序列表 
    print("最大数值为：", "".join(result))<jupyter_output>最大数值为0，欺骗人的！
最大数值为： 10000<jupyter_text>快速排序<jupyter_code>def partition(arr, begin, end):
    base_index = begin  # 选择序列第一个元素作为基准值
    for i in range(begin+1, end+1):
        if arr[i] <= arr[begin]: # 如果元素大于基准值位置不变，若否则调换位置
            base_index += 1       # 记录基准值的新位置
            arr[i], arr[base_index] = arr[base_index], arr[i]
    arr[base_index], arr[begin] = arr[begin], arr[base_index] # 把基准值放到新位置
    return base_index

def quick_sort_recursion(arr, begin, end):
    if begin >= end: # 若开始下标和结束下标重合，就是最小的子序列不用继续拆解
        return
    base_index = partition(arr, begin, end) # 找出基准值的新下标
    quick_sort_recursion(arr, begin, base_index-1) # 小于基准值的子序列
    quick_sort_recursion(arr, base_index+1, end) # 大于基准值的子序列

def quick_sort(arr):
    """快速排序"""
    begin = 0          # 刚开始是整个列表
    end = len(arr) - 1 # 列表最末端下标
    quick_sort_recursion(arr, begin, end) # 递归求解
arr = [4,5,7,6,3,2,1]
quick_sort(arr)
print(arr)
from random import randint  # 使用randint产生随机整数
def partition_random(arr, begin, end):
    """优化选择基准值的方式"""
    base_index = randint(begin, end)  # 随机选择序列某个元素作为基准值
    arr[begin], arr[base_index] =  arr[base_index], arr[begin] # 把基准值调到最前面
    base_index = begin
    for i in range(begin+1, end+1):
        if arr[i] <= arr[begin]: # 如果元素大于基准值位置不变，若否则调换位置
            base_index += 1       # 记录基准值的新位置
            arr[i], arr[base_index] = arr[base_index], arr[i]
    arr[base_index], arr[begin] = arr[begin], arr[base_index] # 把基准值放到新位置
    return base_index

def quick_sort_recursion(arr, begin, end):
    if begin >= end: # 若开始下标和结束下标重合，就是最小的子序列不用继续拆解
        return
    base_index = partition_random(arr, begin, end) # 找出基准值的新下标
    quick_sort_recursion(arr, begin, base_index-1) # 小于基准值的子序列
    quick_sort_recursion(arr, base_index+1, end) # 大于基准值的子序列

def quick_sort(arr):
    """快速排序"""
    begin = 0          # 刚开始是整个列表
    end = len(arr) - 1 # 列表最末端下标
    quick_sort_recursion(arr, begin, end) # 递归求解
arr = [4,5,7,6,3,2,1]
quick_sort(arr)
print(arr)<jupyter_output>[1, 2, 3, 4, 5, 6, 7]<jupyter_text>挑战：荷兰国旗问题<jupyter_code>def color_sort(arr):
    """荷兰国旗问题"""
    red, white, blue = 0,0, len(arr) - 1 # 初始化指针位置 
    while white <= blue:     # 白色指针小于蓝色指针，移动白色指针
        if arr[white] == 0:  # 遇到红色球
            # 白色指针指向红色球，用红色指针交换并向前移动（+1）白色和红色指针
            arr[red], arr[white] = arr[white], arr[red]
            red += 1
            white += 1
        elif arr[white] == 1: # 遇到白色球
            # 白色指针指向白色球，则元素已经在正确的位置，因此只需向前移动白色指针
            white += 1
        else:                # 遇到蓝色球
            # 白色指针向蓝色球，用蓝色指针交换，也就是交换最新的未分类元素，蓝色指针向后移动
            arr[blue], arr[white] = arr[white], arr[blue]
            blue -= 1
input_data = [0,1,2,1,1,0,2,1,0]
color_sort(input_data)
print(input_data)<jupyter_output>[0, 0, 0, 1, 1, 1, 1, 2, 2]<jupyter_text>Python内置排序 列表中的函数sort()<jupyter_code># 列表中的函数sort
arr = [4,5,7,6,3,2,1]
arr.sort()
print("升序：", arr)
arr.sort(reverse=True)  # 降序排列
print("降序：", arr)
arr_2 = [3, -2, 1, 8, 0, -11, -2, 10]
arr_2.sort(key=abs)  # 按绝对值排列
print("按元素绝对值升序：", arr_2)
arr_3 = ['louis', 'Tom', 'Merry', 'Jack', 'Anthony']
arr_3.sort(key=len)  # 按字符长度排序
print("按元素字符长度升序", arr_3)<jupyter_output>升序： [1, 2, 3, 4, 5, 6, 7]
降序： [7, 6, 5, 4, 3, 2, 1]
按元素绝对值升序： [0, 1, -2, -2, 3, 8, 10, -11]
按元素字符长度升序 ['Tom', 'Jack', 'louis', 'Merry', 'Anthony']<jupyter_text>sorted()函数的使用<jupyter_code># sorted()函数的使用
arr = [4,5,7,6,3,2,1]
print("升序:", sorted(arr))  # 默认是升序
print("输入列表：", arr)  # 不改变原来列表
arr_2 = sorted(arr, reverse=True)  # 降序
print("降序:", arr_2)
arr_3 = [('b',2),('a',1),('c',3),('d',4)]
arr_4 = sorted(arr_3, key=lambda x:x[1])  # 选择用某个关键值来排序
print("通过第二个关键值来排序:", arr_4)
arr_5 = ['louis', 'Tom', 'Merry', 'Jack', 'Anthony']
arr_6 = sorted(arr_5, key=lambda x: len(x), reverse=True)  # 按字符长度排序, 用lambda可以更清晰表达
print("按元素字符长度降序1：", arr_6)
arr_7 = sorted(arr_5, key=len, reverse=True)  # 按字符长度排序，不同表达方式
print("按元素字符长度降序2：", arr_6)
# 选择用某个关键值来排序，不同表达方式
def value_len(value):
    return len(value)
arr_8 = sorted(arr_5, key=value_len, reverse=True)  
print("按元素字符长度降序3：", arr_8)
# 字典排序
dict_1 = {'b':2, 'a':1, 'c':3, 'd':4}
dict_2 = sorted(dict_1.items(), key=lambda x: x[1])
print("原字典：",dict_1)
print("字典的值排序", dict_2)
# 多个关键值排序
class cmp_list:
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c
    def __repr__(self):
        return repr((self.a, self.b, self.c))

multi_cmps = [cmp_list('X', 1, 6), cmp_list('A', 3, 2), cmp_list('X', 2, 5)]
# 首先根据a的位置来排序，然后根据b的位置来排序
res = sorted(multi_cmps, key=lambda x:(x.a, x.b))
print("多关键值排序：", res)<jupyter_output>原字典： {'b': 2, 'a': 1, 'c': 3, 'd': 4}
字典的值排序 [('a', 1), ('b', 2), ('c', 3), ('d', 4)]
多关键值排序： [('A', 3, 2), ('X', 1, 6), ('X', 2, 5)]
{'fraction_non_alphanumeric': 0.15605381165919283, 'fraction_numerical': 0.03256295274232494, 'mean_word_length': 2.9020188425302824, 'pattern_counts': {'":': 0, '<': 51, '<?xml version=': 0, '>': 50, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '363433', 'license': 'AFL-3.0', 'n_tokens_mistral': 7242, 'n_tokens_neox': 7432, 'n_words': 1062, 'path': 'chapter3-sort.ipynb', 'repo_name': 'liangxuCHEN/Algorithms_python', 'size': '14495'}