重温三种排序算法

一、 快速排序

• 首先要打乱序列顺序，以防算法陷入最坏时间复杂度。快速排序使用“分而治之”的方法。

对于一串序列，首先从中选取一个数，凡是小于这个数的值就被放在左边一摞，凡是大于这个数的值就被放在右边一摞，然后，继续对左右两摞进行快速排序。
知道进行快速排序的序列长度小于2（即序列中只有一个值或者空值）

# quicksort
import random
def quicksort(seq):
    if len(seq)<2:
        return seq
    else:
        base=seq[0]
        left=[elem for elem in seq[1:] if elem<base]
        right=[elem for elem in seq[1:] if elem>base]
        return quicksort(left)+[base]+quicksort(right)
seq=[9,8,7,6,5,4,3,2]
random.shuffle(seq)
print(seq)
print(quicksort(seq))

[4, 7, 9, 5, 2, 3, 6, 8]
[2, 3, 4, 5, 6, 7, 8, 9]

---

二、冒泡排序

• 冒泡排序（顺序形式），从左向右，两两比较，如果左边元素大于右边元素，就交换两个元素的位置。

  其中，每一轮排序，序列中最大的元素浮动到最右边。也就是说，每一轮排序，至少确保有一个元素在正确的位置
  这样下来的循环，就不需要考虑已经排好序的元素了，每次内层循环次数都会减一。
  其中，如果有一轮循环之后次序没有交换，这时我们就可以停止循环，得到我们想要的序列了。

  # bouble_sort
  def bouble_sort(sequence):
      seq=sequence[:]
      length=len(sequence)-1
      i=j=0
      flag=1
      while i<length:
          j=0
          while j<length-1:
              if seq[j]>seq[j+1]:
                  seq[j],seq[j+1]=seq[j+1],seq[j]
                  flag=0
              j+=1
          if flag:break
          i+=1
      return seq
  seq=[9,5,7,4,2,8]
  res_seq=bouble_sort(seq)
  print(res_seq)
  
  [2, 4, 5, 7, 9, 8]

---

三、选择排序

• 选择排序，每次选择当前序列最小值，将其与当前序列的第一个值进行交换位置，
  每迭代一次，当前序列长度减一。迭代结束，即可得到有序序列。

# select_sort
def find_minimal_index(seq):
    min_elem=seq[0]
    count=0
    min_elem_index = count
    for elem in seq[1:]:
        count+=1
        if elem<min_elem:
            elem,min_elem=min_elem,elem
            min_elem_index = count
    return min_elem_index
def select_sort(sequence):
    #选择排序
    seq=sequence[:]
    length = len(seq)
    for i in range(length):
        index = find_minimal_index(seq[i:])
        seq[index+i],seq[i]=seq[i],seq[index+i]
    return seq
seq=[9,5,7,4,2,8]
res_seq=bouble_sort(seq)
print(res_seq)

[2, 4, 5, 7, 9, 8]

赏

谢谢你请我吃鸡

微信