排序算法在 Python 中的实现

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

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

我们将引导您完成不同的排序算法以及实施中的每一步。 实现部分将使用 Python。 获得算法后，您可以轻松地将其转换为任何语言。 那是语言语法的问题。

在本教程中，我们将看到从最差到最好的不同算法。 所以，别担心。 按照文章并实施它们。

让我们深入研究排序算法。

插入排序

插入排序是一种简单的排序算法。 它很容易实现。 而且对数组进行排序会花费你更多的时间。 在大多数情况下，它不会用于对较大的数组进行排序。

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

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

让我们通过示例逐步查看插入排序的可视化插图。

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

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

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

而已; 我们已经对给定的数组进行了排序。 让我们运行以下代码。 我希望你已经安装了 Python，如果没有，请查看安装指南。 或者，您可以使用在线 Python 编译器。

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

		## to store the index of the minimum element
		min_element_index = i
		for j in range(i + 1, n):
			## checking and replacing the minimum element index
			if arr[j] < arr[min_element_index]:
				min_element_index = j

		## swaping the current element with minimum element
		arr[i], arr[min_element_index] = arr[min_element_index], arr[i]

if __name__ == '__main__':
	## array initialization
	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
	selection_sort(arr, 9)

	## printing the array
	print(str(arr))

冒泡排序

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

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

插图帮助我们直观地理解冒泡排序。 让我们看看他们。

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

用虚拟数据（整数）初始化数组。

遍历给定的数组。

从 0 迭代到 ni-1。 最后 i 个元素已经排序。

检查当前元素是否大于下一个元素。

如果当前元素大于下一个元素，则交换两个元素。

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

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

def bubble_sort(arr, n):
	for i in range(n):
		## iterating from 0 to n-i-1 as last i elements are already sorted
		for j in range(n - i - 1):
			## checking the next element
			if arr[j] > arr[j + 1]:
				## swapping the adjucent elements
				arr[j], arr[j + 1] = arr[j + 1], arr[j]

if __name__ == '__main__':
	## array initialization
	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
	bubble_sort(arr, 9)

	## printing the array
	print(str(arr))

合并排序

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

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

由于它是一种递归算法，它会划分数组，直到数组成为最简单的（具有一个元素的数组）排序。

是时候说明了。 让我们来看看它。

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

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

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

这就是合并排序算法的实现。 检查下面的代码。

def merge(arr, left_index, mid_index, right_index):
	## left and right arrays
	left_array = arr[left_index:mid_index+1]
	right_array = arr[mid_index+1:right_index+1]

	## getting the left and right array lengths
	left_array_length = mid_index - left_index + 1
	right_array_length = right_index - mid_index

	## indexes for merging two arrays
	i = j = 0

	## index for array elements replacement
	k = left_index

	## iterating over the two sub-arrays
	while i < left_array_length and j < right_array_length:

		## comapring the elements from left and right arrays
		if left_array[i] < right_array[j]:
			arr[k] = left_array[i]
			i += 1
		else:
			arr[k] = right_array[j]
			j += 1
		k += 1

	## adding remaining elements from the left and right arrays
	while i < left_array_length:
		arr[k] = left_array[i]
		i += 1
		k += 1

	while j < right_array_length:
		j += 1
		k += 1

def merge_sort(arr, left_index, right_index):
	## base case for recursive function
	if left_index >= right_index:
		return

	## finding the middle index
	mid_index = (left_index + right_index) // 2

	## recursive calls
	merge_sort(arr, left_index, mid_index)
	merge_sort(arr, mid_index + 1, right_index)

	## merging the two sub-arrays
	merge(arr, left_index, mid_index, right_index)

if __name__ == '__main__':
	## array initialization
	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
	merge_sort(arr, 0, 8)

	## printing the array
	print(str(arr))

结论

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

接下来，了解搜索算法。

快乐编码🙂👨‍💻