Python - 排序算法

排序是指以特定格式排列数据。 排序算法指定按特定顺序排列数据的方式。 最常见的顺序是按数字或字典顺序排列。

排序的重要性在于，如果数据以排序的方式存储，则可以将数据搜索优化到一个非常高的水平。 排序还用于以更具可读性的格式表示数据。 下面我们看到 5 个这样的 python 排序实现。

• 冒泡排序

• 归并排序

• 插入排序

• Shell 希尔排序

• 选择排序

冒泡排序

这是一种基于比较的算法，其中比较每对相邻元素，如果元素顺序不对则交换元素。

示例

def bubblesort(list):

# Swap the elements to arrange in order
   for iter_num in range(len(list)-1,0,-1):
      for idx in range(iter_num):
         if list[idx]>list[idx+1]:
            temp = list[idx]
            list[idx] = list[idx+1]
            list[idx+1] = temp
list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)

输出

当上面的代码执行时，会产生如下结果 −

[2, 6, 11, 19, 27, 31, 45, 121]

归并排序

归并排序首先将数组分成相等的两半，然后将它们按排序方式组合。

示例

def merge_sort(unsorted_list):
   if len(unsorted_list) <= 1:
      return unsorted_list
# Find the middle point and devide it
   middle = len(unsorted_list) // 2
   left_list = unsorted_list[:middle]
   right_list = unsorted_list[middle:]

   left_list = merge_sort(left_list)
   right_list = merge_sort(right_list)
   return list(merge(left_list, right_list))

# Merge the sorted halves
def merge(left_half,right_half):
   res = []
   while len(left_half) != 0 and len(right_half) != 0:
      if left_half[0] < right_half[0]:
         res.append(left_half[0])
         left_half.remove(left_half[0])
      else:
         res.append(right_half[0])
         right_half.remove(right_half[0])
   if len(left_half) == 0:
      res = res + right_half
   else:
      res = res + left_half
   return res
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(unsorted_list))

输出

当上面的代码执行时，会产生如下结果 −

[11, 12, 22, 25, 34, 64, 90]

插入排序

插入排序涉及在排序列表中为给定元素找到正确的位置。 所以一开始我们比较前两个元素，并通过比较它们来排序。 然后我们选择第三个元素并在前两个排序元素中找到它的适当位置。 通过这种方式，我们逐渐将更多元素添加到已经排序的列表中，将它们放在适当的位置。

示例

def insertion_sort(InputList):
   for i in range(1, len(InputList)):
      j = i-1
      nxt_element = InputList[i]
# Compare the current element with next one
   while (InputList[j] > nxt_element) and (j >= 0):
      InputList[j+1] = InputList[j]
      j=j-1
   InputList[j+1] = nxt_element
list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)

输出

当上面的代码执行时，会产生如下结果 −

[19, 2, 31, 45, 30, 11, 27, 121]

Shell 希尔排序

Shell 希尔排序涉及对彼此远离的元素进行排序。 我们对给定列表的一个大子列表进行排序，然后继续减小列表的大小，直到所有元素都排序完毕。 下面的程序通过将它等同于列表大小的一半长度来找到间隙，然后开始对其中的所有元素进行排序。 然后我们不断地重新设置间隙，直到整个列表排序完毕。

示例

def shellSort(input_list):
   gap = len(input_list) // 2
   while gap > 0:
      for i in range(gap, len(input_list)):
         temp = input_list[i]
         j = i
# Sort the sub list for this gap
   while j >= gap and input_list[j - gap] > temp:
      input_list[j] = input_list[j - gap]
      j = j-gap
      input_list[j] = temp
# Reduce the gap for the next element
   gap = gap//2
list = [19,2,31,45,30,11,121,27]
shellSort(list)
print(list)

输出

当上面的代码执行时，会产生如下结果 −

[2, 11, 19, 27, 30, 31, 45, 121]

选择排序

在选择排序中，我们首先在给定列表中找到最小值并将其移至排序列表。 然后我们对未排序列表中的每个剩余元素重复该过程。 将进入已排序列表的下一个元素与现有元素进行比较，并将其放置在正确的位置。因此，最后未排序列表中的所有元素都已排序。

示例

def selection_sort(input_list):
   for idx in range(len(input_list)):
      min_idx = idx
      for j in range( idx +1, len(input_list)):
         if input_list[min_idx] > input_list[j]:
            min_idx = j
# Swap the minimum value with the compared value
   input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]
l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)

输出

当上面的代码执行时，会产生如下结果 −

[19, 2, 31, 45, 30, 11, 121, 27]