在Python中实现的排序算法实现

排序是编程中最常用的功能之一。如果我们没有使用正确的算法，完成排序将需要一些时间。

在本文中，我们将讨论不同的排序算法。

我们将带您逐步了解每个实现步骤中的不同排序算法。实现部分将在Python中。一旦获得算法，您可以轻松将其转换为任何语言。这只是语言语法的问题。

在本教程中，我们将按从最差到最好的顺序查看不同的算法。所以，不用担心。按照文章中所说的实现它们。

让我们深入了解排序算法。

插入排序

插入排序是一种简单的排序算法之一。它易于实现。对于排序较大的数组，它将花费更多时间来排序。在大多数情况下，不会用于排序。

插入排序算法在给定数组中维护排序和未排序的子部分。

排序的子部分在排序过程的开始时只包含第一个元素。我们将从未排序数组中取出一个元素，并将其放置在排序子数组中的正确位置。

让我们逐步查看插入排序的视觉说明。

让我们看看实现插入排序的步骤。

• 使用虚拟数据（整数）初始化数组。
• 从第二个元素开始遍历给定的数组。
  • 将当前位置和元素存储在两个变量中。
  • 编写一个循环，直到数组的第一个元素或出现小于当前元素的元素为止。
    • 使用前一个元素更新当前元素。
    • 减小当前位置。
  • 在这里，循环必须达到数组的起始或找到小于当前元素的元素。用当前元素替换当前位置的元素。

  插入排序的时间复杂度是O(n^2)，空间复杂度是O(1)。

  我们已经对给定的数组进行了排序。让我们运行以下代码。希望您已经安装了Python，如果没有，请查看installation guide。或者，您可以使用online Python compiler。

  def insertion_sort(arr, n):
  	for i in range(1, n):
  
  		## current position and element
  		current_position = i
  		current_element = arr[i]
  
  		## iteratin until
  		### it reaches the first element or
  		### the current element is smaller than the previous element
  		while current_position > 0 and current_element <
  		 arr[current_position - 1]:
  			## updating the current element with previous element
  			arr[current_position] = arr[current_position - 1]
  
  			## moving to the previous position
  			current_position -= 1
  
  		## updating the current position element
  		arr[current_position] = current_element
  
  if __name__ == '__main__':
  	## array initialization
  	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
  	insertion_sort(arr, 9)
  
  	## printing the array
  	print(str(arr))

  选择排序

  选择排序与插入排序类似，只有一点不同。该算法也将数组分为排序和未排序的子部分。然后，在每次迭代中，我们将从未排序的子部分中取出最小的元素，并将其放置在排序的子部分的最后位置。

  让我们通过示例来了解选择排序的过程。

  

  让我们看看实现选择排序的步骤。

  • 用虚拟数据（整数）初始化数组。
  • 遍历给定的数组。
    • 保持最小元素的索引。
    • 编写一个循环，从当前元素迭代到最后一个元素。
      • 检查当前元素是否小于最小元素。
      • 如果当前元素小于最小元素，则替换索引。
    • 我们有最小元素的索引。使用索引将当前元素与最小元素交换。

    选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

    尝试将算法实现为与插入排序类似。您可以查看下面的代码。

    def selection_sort(arr, n):
    	for i in range(n):
    
    		## 保存最小元素的索引
    		min_element_index = i
    		for j in range(i + 1, n):
    			## 检查并替换最小元素的索引
    			if arr[j] < arr[min_element_index]:
    				min_element_index = j
    
    		## 交换当前元素和最小元素
    		arr[i], arr[min_element_index] = arr[min_element_index], arr[i]
    
    if __name__ == '__main__':
    	## 数组初始化
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	selection_sort(arr, 9)
    
    	## 打印数组
    	print(str(arr))

    冒泡排序

    冒泡排序是一个简单的算法。它重复地在每次迭代中交换相邻的元素，直到给定的数组排序完成。

    它遍历数组并将当前元素移动到下一个位置，直到它小于下一个元素。

    图示可以帮助我们直观地理解冒泡排序。让我们来看看它们。

    

    让我们看看实现冒泡排序的步骤。

    1. 用虚拟数据（整数）初始化数组。
    2. 遍历给定的数组。
       1. 从0到n-i-1进行迭代。最后的i个元素已经排序完成。
          1. 检查当前元素是否大于下一个元素。
          2. 如果当前元素大于下一个元素，则交换这两个元素。

          冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

          现在您可以轻松实现冒泡排序了。让我们看看代码。

          def bubble_sort(arr, n):
          	for i in range(n):
          		## 从0到n-i-1进行迭代，因为最后的i个元素已经排序完成
          		for j in range(n - i - 1):
          			## 检查下一个元素
          			if arr[j] > arr[j + 1]:
          				## 交换相邻的元素
          				arr[j], arr[j + 1] = arr[j + 1], arr[j]
          
          if __name__ == '__main__':
          	## 数组初始化
          	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
          	bubble_sort(arr, 9)
          
          	## 打印数组
          	print(str(arr))

          归并排序

          归并排序是一种递归算法，用于对给定的数组进行排序。在时间复杂度方面，它比前面讨论的算法更高效。它遵循分而治之的方法。

          归并排序算法将数组分为两半并分别对它们进行排序。在对数组的两个半部分排序后，它将它们合并为一个排序的数组。

          由于它是递归算法，它会将数组分割到最简单的程度（只包含一个元素的数组）以进行排序。

          现在是时候进行说明了。让我们来看看。

          

          让我们看看实现归并排序的步骤。

          • 用虚拟数据（整数）初始化数组。
          • 编写一个名为merge的函数，将子数组合并为一个排序后的数组。它接受数组、左索引、中间索引和右索引作为参数。
            • 使用给定的索引获取左子数组和右子数组的长度。
            • 将数组元素复制到相应的左子数组和右子数组中。
            • 遍历这两个子数组。
              • 比较这两个子数组的元素。
              • 用这两个子数组中较小的元素替换数组元素以进行排序。
            • 检查这两个子数组中是否还有剩余元素。
            • 将它们添加到数组中。
            • 编写一个名为merge_sort的函数，它接受数组、左索引和右索引作为参数。
              • 如果左索引大于或等于右索引，则返回。
              • 找到数组的中间点以将数组分成两半。
              • 使用左索引、右索引和中间索引递归调用merge_sort。
              • 在递归调用之后，使用merge函数合并数组。

              归并排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。

              以上就是归并排序算法的实现。请查看下面的代码。

              def merge(arr, left_index, mid_index, right_index):
              	## 左数组和右数组
              	left_array = arr[left_index:mid_index+1]
              	right_array = arr[mid_index+1:right_index+1]
              
              	## 获取左数组和右数组的长度
              	left_array_length = mid_index - left_index + 1
              	right_array_length = right_index - mid_index
              
              	## 合并两个数组的索引
              	i = j = 0
              
              	## 数组元素替换的索引
              	k = left_index
              
              	## 遍历这两个子数组
              	while i < left_array_length and j < right_array_length:
              
              		## 比较左数组和右数组的元素
              		if left_array[i] < right_array[j]:
              			arr[k] = left_array[i]
              			i += 1
              		else:
              			arr[k] = right_array[j]
              			j += 1
              		k += 1
              
              	## 将左数组和右数组中剩余的元素添加到数组中
              	while i < left_array_length:
              		arr[k] = left_array[i]
              		i += 1
              		k += 1
              
              	while j = right_index:
              		return
              
              	## 找到中间索引
              	mid_index = (left_index + right_index) // 2
              
              	## 递归调用
              	merge_sort(arr, left_index, mid_index)
              	merge_sort(arr, mid_index + 1, right_index)
              
              	## 合并这两个子数组
              	merge(arr, left_index, mid_index, right_index)
              
              if __name__ == '__main__':
              	## 初始化数组
              	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
              	merge_sort(arr, 0, 8)
              
              	## 打印数组
              	print(str(arr))

              结论

              还有许多其他排序算法，但以上是一些常用的。希望你喜欢学习排序算法。

              接下来，了解一下search algorithms。

              快乐编程 🙂 👨‍💻

              相关