成都网站建设设计

将想法与焦点和您一起共享

python快速排序实现

  1. import random

  2. num_list = []
  3. for x in range(30):
  4.     num_list.append(random.randint(1, 500))

  5. list_len = len(num_list)
  6. print(list_len)


  7. def quick_sort(array, begin, end):
  8.     # (1) 104, 17, 510,30,100   这是用来说明的例子,请按前面的序号阅读
  9.     #      i               j
  10.     if begin < end:
  11.         i, j = begin, end
  12.         # 设置临时基准
  13.         temp = array[i]
  14.         # --------------------------------------------
  15.         while i < j:
  16.             # 如果列表后边的数,比基准数大或相等,j则前移一位,直到出现第一个比基准数小的数
  17.             while (i < j) and (array[j] >= temp):
  18.                 j = j - 1
  19.             # 找到后把第j个元素赋值给第i个元素
  20.             array[i] = array[j] # (2)100,17,510,30,100 (4)100, 17, 30, 30, 510
  21.                                   #   i             j               i  j <-- j
  22.             # 若前边的数比基准数小或相等,i则后移一位,直到出现第一个比基准数大的数
  23.             while (i < j) and (array[i] <= temp):
  24.                 i = i + 1
  25.             array[j] = array[i] # (3)100,17,510, 30,510 (5) 00,17,30,  30, 510
  26.                                  #     i --> i       j             i-->ij
  27.         # ---------------------------------------------

  28.         # 做完第一轮while比较之后,list被分成了两个list,且i=j
  29.         array[i] = temp # (6)100,17,30,104,510 这是第一轮结束之后的情况.
  30.                                       # ij
  31.         # 此时,以第一轮选择的temp为分割点,分成两个list.左边list里的项都比temp小,右边list里的项都比temp大
  32.         # 递归前后半区
  33.         quick_sort(array, begin, i - 1)
  34.         quick_sort(array, j + 1, end)
  35.     return array

  36. print("The sorted result is : ")
  37. quick_sort(num_list, 0, len(num_list)-1)
  38. print(num_list)


本文标题:python快速排序实现
URL标题:http://chengdu.cdxwcx.cn/article/gcdohc.html