常用排序算法

1.冒泡排序

• 又称交换排序法，原理是：从第一个元素开始，比较相邻元素的大小，若大小顺序有误，则对调顺序后再进行下一个元素的对比。如此扫描过一次之后就可确保最后一个元素位于正确的顺序，接着再进行第二次扫描，直到所有元素的排序关系为止。这里看出是对一个序列进行移动交换操作，它的时间复杂度为O(n^2)。
  其示意图如下图所示：

冒泡排序

'''  冒泡排序  '''
def bubble_sort(list):
    n = len(list)
    count = 0
    for j in range(n-1):
        for i in range(n-1-j):
            if list[i] > list[i+1]:
                list[i],list[i+1] = list[i+1],list[i]
                count += 1
        if count == 0:
            return

  #list有n个数，需要进行n-1次排序
  #从左往右排序，第一次排序移动n-2次，第二次排序移动n-3次...

if __name__ == '__main__':
    list = [65,12,33,72,5,8,45,28]
    print(list)
    bubble_sort(list)
    print(list)

2.插入排序

• 从数据最左拿一个元素，然后与第二个元素比较进行排序，组成新的序列，再将新的序列与第三个元素比较进行排序，重复上述操作最后得到正序或者倒序的数据。这里可以看成是两个序列，将旧序列最左的元素添加到新序列中并进行排序。
  其示意图为：

插入排序

'''  插入排序  '''
def insert_sort(list):
  n = len(list)
  for j in range(1,n):
      i = j
      while i > 0:
          if list[i] < list[i-1]:
              list[i],list[i-1] = list[i-1],list[i]
              i -= 1
          else:
              break

# i代表能蹭循环起始值
# i=j 执行从右边的无序序列中取出第一个元素，即i位置，插入前面正确的位置

if __name__ == '__main__':
    list = [65, 12, 33, 72, 5, 8, 45, 28]
    print(list)
    insert_sort(list)
    print(list)

3.选择排序

• 从序列最左边拿出一个元素作为初始值，与右边序列的每个值进行对比，若右边的值小于初始值，交换元素，直到整个右边的元素对比完毕；然后取出右边序列最左边元素作为初始值，重复上述步骤，最后组成新的序列。
  其示意图为：

选择排序

'''  选择排序  '''
def select_sort(list):
    n = len(list)
    for j in range(0,n-1):
        min_index = j
        for i in range(j+1,n):
            if list[min_index] > list[i]:
                min_index = i
        list[j],list[min_index] = list[min_index],list[j]

#将最左边的的值作为初始值与右边的值进行对比，当右边的值小于初始值，交换元素，直到整个右边对比完
#将对比的结果作为最左边的值，从第二位开始，重复第一步的步骤

if __name__ == '__main__':
    list = [65, 12, 33, 72, 5, 8, 45, 28]
    print(list)
    select_sort(list)
    print(list)

4.希尔排序

• 选取一个步长，例如 1 2 3 4 5 6，步长为2的话，会把数组分成1 3 5，2 4 6，这样分开之后对每部分进行直接插入排序，下一步缩小步长继续上述步骤，直至步长为1。
  其示意图如下图所示：

希尔排序

'''  希尔排序  '''
def shell_sort(list):
    n = len(list)
    gap = n // 2
    while gap > 0:
        for j in range(gap,n):
            i = j
            while i > 0:
                if list[i] < list[i-gap]:
                    list[i],list[i-gap] = list[i-gap],list[i]
                    i -= gap
                else:
                    break

if __name__ == '__main__':
    list = [65, 12, 33, 72, 5, 8, 45, 28]
    print(list)
    shell_sort(list)
    print(list)

5.快速排序

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
其示意图如下图所示：

快速排序

# 快速排序-分而治之
def quickSort(list):
    # 基线条件：为空或只包含一个元素的数组是“有序”的
    if len(list) < 2:
        return list
    else:
        pivot = list[0]
        # 由所有小于基准值的元素组成的子数组
        low = [i for i in list[1:] if i <= pivot]
        # 由所有大于基准值的元素组成的子数组
        high = [i for i in list[1:] if i > pivot]

        return quickSort(low) + [pivot] + quickSort(high)


if __name__ == '__main__':
    list = [65, 12, 33, 72, 5, 8, 45, 28]
    print(list)
    list = quickSort(list)
    print(list)

6.归并排序

• 把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。
  其示意图如下图所示：

归并排序

 '''归并排序'''
  def merge_sort(list):
      n = len(list)
      if n <= 1:
          return
      mid = n//2          #拆分序列

      #left采取归并排序后形成的有序的新的列表
      left_list = merge_sort(list[:mid])

      #right采取归并排序后形成的有序的新的列表
      rigth_list = merge_sort(list[mid:])

      #将两个子序列合并成一个新的整体
      left_point,right_point = 0,0
      result = []
      while left_point < len(left_list) and right_point < len(rigth_list):
          if left_list[left_point] < rigth_list[right_point]:
              result.append(left_list[left_point])
              left_point += 1
          else:
              result.append(rigth_list[right_point])
              right_point += 1

      result += left_list[left_point]
      result += rigth_list[right_point]
      return result

if __name__ == '__main__':
      list = [65, 12, 33, 72, 5, 8, 45, 28]
      print(list)
      merge_sort(list)
      print(list)

7.二分法查找

'''  二分法查找  '''
def binary_search(list,item):   #二分法查找,递归
    n = len(list)
    if n > 0:
        mid = n // 2
        if list[mid] == item:
            return True
        elif item < list[mid]:
            return binary_search(list[:mid],item)
        else:
            return binary_search(list[mid+1:],item)
    return False

def binary_search_(list,item):  #二分查找,非递归
    n = len(list)
    first = 0
    last = n-1
    while first <= last:
        mid = (first+last)//2
        if list[mid] == item:
            return True
        elif item < list[mid]:
            last = mid-1
        else:
            first = mid+1
    return False


if __name__ == '__main__':
    list = [5,8,12,28,33,45,65,72]
    print(binary_search(list,33))
    print(binary_search(list,99))

    print(binary_search_(list,33))
    print(binary_search_(list,99))