快速排序：

  1. # 非递归版本
  2. def quick_sort(arr):
  3.     if len(arr) < 2:
  4.         return arr
  5.     position = [0, len(arr)-1]
  6.     stack = []
  7.     stack.append(position)
  8.     while stack:
  9.         l, r = stack.pop()
  10.         index = partition(arr, l, r)
  11.         if l < index - 1:
  12.             stack.append([l, index - 1])
  13.         if r > index + 1:
  14.             stack.append([index + 1, r])
  17. def partition(arr, start, end):
  18.     # 分区操作，返回基准线下标
  19.     pivot = arr[start]
  20.     # 从两边来，左边移动一个，就到右边移动一个，保持平衡
  21.     while start < end:
  22.         while start < end and arr[end] >= pivot:
  23.             end -= 1
  24.         arr[start] = arr[end]
  25.         while start < end and arr[start] <= pivot:
  26.             start += 1
  27.         arr[end] = arr[start]
  28.     # 此时start = end
  29.     arr[start] = pivot
  30.     return start
  32. f = quick_sort(p)
  33. print(p)
  35. ############################## 递归版本没啥用 ########################################
  36. # quick
  37. def q_sort(list):
  38.     less, mid, more = [], [], []
  39.     if len(list) <= 1:
  40.         return list
  41.     else:
  42.         m = list[0]
  43.         for i in list:
  44.             if i > m:
  45.                 more.append(i)
  46.             elif i < m:
  47.                 less.append(i)
  48.             else:
  49.                 mid.append(i)
  50.         less = q_sort(less)
  51.         more = q_sort(more)
  52.         return less + mid + more
  53. def q_sort_1(L):
  54.     if len(L) < 2:
  55.         return L
  56.     pivot_element = random.choice(L)
  57.     small = [i for i in L if i < pivot_element]
  58.     medium = [i for i in L if i == pivot_element]
  59.     large = [i for i in L if i > pivot_element]
  60.     return q_sort(small) + medium + q_sort(large)

并归排序：

  1. # 非递归实现
  2. def merge(seq,low,mid,height):
  3.     """合并两个已排序好的列表，产生一个新的已排序好的列表"""
  4.     # 通过low,mid height 将[low:mid) [mid:height)提取出来
  5.     left = seq[low:mid]
  6.     right = seq[mid:height]
  7.     print('left:%s'% left, 'right:%s' % right)
  9.     k = 0   #left的下标
  10.     j = 0   #right的下标
  11.     result = [] #保存本次排序好的内容
  12.     #将最小的元素依次添加到result数组中
  13.     while k < len(left) and j < len(right):
  14.         if left[k] <= right[j]:
  15.             result.append(left[k])
  16.             k += 1
  17.         else:
  18.             result.append(right[j])
  19.             j += 1
  20.     #将对比完后剩余的数组内容 添加到已排序好数组中
  21.     result += left[k:]
  22.     result += right[j:]
  23.     #将原始数组中[low:height)区间 替换为已经排序好的数组
  24.     seq[low:height] = result
  25.     print("seq:", seq)
  26. seq = [5, 4, 3, 0, 1, 2, 7, 5, 11,9]
  27. i = 1
  28. while i < len(seq):
  29.     print('子数组 长度 : ',i)
  30.     low = 0
  31.     while low < len(seq):
  32.         mid = low + i
  33.         height = min(low + 2 * i, len(seq))
  34.         if mid < height:
  35.             print('low ',low,'mid:',mid,'height:',height)
  36.             merge(seq,low,mid,height)
  37.         low += 2*i
  38.     i *= 2
  41. ########################## 递归实现 ##########################
  43. # merge
  44. def m_sort(list):
  45.     if len(list) <= 1:
  46.         return list
  47.     mid = len(list) // 2
  48.     left = m_sort(list[:mid])
  49.     right = m_sort(list[mid:])
  50.     return merge(left, right)
  51. def merge(left, right):
  52.     l, r = 0, 0
  53.     result = []
  54.     while l < len(left) and r < len(right):
  55.         if left[l] < right[r]:
  56.             result.append(left[l])
  57.             l += 1
  58.         else:
  59.             result.append(right[r])
  60.             r += 1
  61.     result += left[l:]
  62.     result += right[r:]
  63.     print(result)
  64.     return result

冒泡排序：

  1. # bubble
  2. def b_sort(list):
  3.     n = len(list)
  4.     for i in range(n):
  5.         changed = False
  6.         for j in range(1, n - i):
  7.             if list[j - 1] > list[j]:
  8.                 list[j - 1], list[j] = list[j], list[j - 1]
  9.                 changed = True
  10.         if not changed:
  11.             break
  12.     return list

插入排序：

  1. # insert
  2. def i_sort(list):
  3.     n = len(list)
  4.     for i in range(1, n):
  5.         key = list[i]
  6.         j = i - 1
  7.         while j >= 0:
  8.             if list[j] > key:
  9.                 list[j], list[j + 1] = key, list[j]
  10.             else:
  11.                 break
  12.             j -= 1
  13.     return list

选择排序：

  1. # select
  2. def s_sort(list):
  3.     n = len(list)
  4.     for i in range(n):
  5.         # min = i
  6.         for j in range(i + 1, n):
  7.             if list[j] < list[i]:
  8.                 # min = j
  9.                 list[i], list[j] = list[j], list[i]
  10.                 print(list)
  11.     return list
  12. def s_sort_1(list):
  13.     n = len(list)
  14.     for i in range(n):
  15.         min = i
  16.         for j in range(i + 1, n):
  17.             if list[j] < list[min]:
  18.                 min = j
  19.         list[i], list[min] = list[min], list[i]
  20.         print(list)
  21.     return list

桶排序：

  1. def t_sort(list):
  2.     n = len(list)
  3.     max, min = list[0], list[0]
  4.     for i in list:
  5.         if i > max:
  6.             max = i
  7.         elif i < min:
  8.             min = i
  9.     s = [0 for i in range(max - min + 1)]
  10.     for i in list:
  11.         s[i - min] += 1
  12.     list2 = []
  13.     # from ipdb import set_trace
  14.     # set_trace()
  15.     for j in range(len(s)):
  16.         key = s[j]
  17.         while key > 0:
  18.             list2.append(min + j)
  19.             key -= 1
  20.     return list2
  21. if __name__ == '__main__':
  22.     list = [6, 5, 3, 1, 8, 7, 2, 4, 4, 4, 5, 7, 89, 455, 765, 23, 1, 23, 435, 546, 567, 56, 8567, 10]
  23.     print(b_sort(list))
  24.     print(q_sort(list))
  25.     print(i_sort(list))
  26.     print(s_sort(list))
  27.     print(m_sort(list))
  28.     print(t_sort(list))

啥玩意啊

  1. def h(str1):
  2.     str1 = '#'.join(str1)
  3.     n = len(str1)
  4.     key = {}
  5.     max = 0
  6.     for i in range(n):
  7.         left = i + 1
  8.         right = n - i
  9.         list1 = [str1[i]]
  10.     # if left < right:
  11.     #   for j in range(1,left):
  12.     #       if str1[i-j] == str1[i+j]:
  13.     #           list1.append(str1[i+j])
  14.     #       else:
  15.     #           break
  16.     # else:
  17.     #   for j in range(1,right):
  18.     #       if str1[i-j] == str1[i+j]:
  19.     #           list1.append(str1[i+j])
  20.     #       else:
  21.     #           break
  22.     for j in range(1, min(left, right)):
  23.         if str1[i - j] == str1[i + j]:
  24.             list1.append(str1[i + j])
  25.         else:
  26.             break
  27.         if len(list1) > max:
  28.             max = len(list1)
  29.             key['max'] = list1
  30.     return key