Python Data Structure 简明教程

Python - Sorting Algorithms

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

Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.

排序的重要性在于，如果数据以有序的方式存储，则可以将数据搜索优化到非常高的级别。排序还用于以更易读的格式表示数据。下面，我们看到在 python 中使用了五种这样的排序实现。

The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Below we see five such implementations of sorting in python.

  1. Bubble Sort

  2. Merge Sort

  3. Insertion Sort

  4. Shell Sort

  5. Selection Sort

Bubble Sort

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

It is a comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.

Example

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)

Output

执行上述代码后，将生成以下结果 −

When the above code is executed, it produces the following result −

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

Merge Sort

归并排序先将数组分成相等的两个部分，然后按顺序合并它们。

Merge sort first divides the array into equal halves and then combines them in a sorted manner.

Example

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))

Output

执行上述代码后，将生成以下结果 −

When the above code is executed, it produces the following result −

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

Insertion Sort

插入排序涉及在已排序列表中找到给定元素的正确位置。因此，在开始时，我们比较前两个元素并通过比较对它们进行排序。然后，我们挑选第三个元素，并在前两个已排序元素中找到其合适的位置。通过这种方式，我们将逐渐向已排序列表添加更多元素，方法是将它们放在正确的位置。

Insertion sort involves finding the right place for a given element in a sorted list. So in beginning we compare the first two elements and sort them by comparing them. Then we pick the third element and find its proper position among the previous two sorted elements. This way we gradually go on adding more elements to the already sorted list by putting them in their proper position.

Example

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)

Output

执行上述代码后，将生成以下结果 −

When the above code is executed, it produces the following result −

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

Shell Sort

希尔排序涉及对远离彼此的元素进行排序。我们对给定列表中的一个较大的子列表进行排序，并不断减小该列表的大小，直到所有元素都按顺序排列。下面的程序通过将其等于列表大小长度的一半来找到差距，然后开始对其中的所有元素进行排序。然后，我们不断重置差距，直到整个列表按顺序排列。

Shell Sort involves sorting elements which are away from each other. We sort a large sublist of a given list and go on reducing the size of the list until all elements are sorted. The below program finds the gap by equating it to half of the length of the list size and then starts sorting all elements in it. Then we keep resetting the gap until the entire list is sorted.

Example

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)

Output

执行上述代码后，将生成以下结果 −

When the above code is executed, it produces the following result −

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

Selection Sort

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

In selection sort we start by finding the minimum value in a given list and move it to a sorted list. Then we repeat the process for each of the remaining elements in the unsorted list. The next element entering the sorted list is compared with the existing elements and placed at its correct position.So, at the end all the elements from the unsorted list are sorted.

Example

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)

Output

执行上述代码后，将生成以下结果 −

When the above code is executed, it produces the following result −

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