在这篇文章中，我将向你展示常见的排序算法并提供它们在 Python 中的实现。如果你是一名程序员，或者如果你已经面试过工作，那么你肯定知道了解和掌握算法对于提高你的编码水平或有机会被录用的重要性。即使它们看起来很容易，但它们真的会变得棘手。

排序算法

在处理数据时，排序是基本任务之一。即使有很多方法可以对数据进行排序，但其中一些方法比其他方法更好，一些方法对于特定用途更有效。根据使用的方法（递归、迭代、比较）或数据结构，你可以有很多可能性。

我都会解释每种算法：概念、复杂性和用例。我还为每个用Python编写的算法提供了解决方案，但是，如果你想挑战自己，请在检查之前自己尝试一下

1. 冒泡算法

冒泡排序的基本思想是，如果相邻元素的顺序不符合要求，它会反复交换它们，就是这么简单

如果给定的数组元素必须按照升序排序，冒泡排序将从数组的第一个元素与第二个元素进行比较开始，如果结果大于第二个元素，则立即交换它们，然后继续比较第二个和第三个元素，依此类推。

def bubbleSort(data):
length = len(data)
for iIndex in range(length):
swapped = False
for jIndex in range(0, length - iIndex - 1):
if data[jIndex] > data[jIndex + 1]:
data[jIndex], data[jIndex + 1] = data[jIndex + 1], data[jIndex]
swapped = True
if swapped == False:
break
print(data)

• 冒泡排序的最坏和平均情况下的复杂度是 О(n2)，这意味着数据的顺序与我们想要排序的顺序相反，或者元素在列表中任意分布。
• 最佳情况复杂度为 O(n)。这是数据已经排序的情况。

冒泡排序用于以下情况：

• 代码简单者优先；
• 复杂性并不重要。

2. 选择排序

由于性能的原因，选择排序是冒泡排序的改进版本。即使它们具有相同的最坏情况性能，选择排序执行的交换也更少。选择排序以两种方式之一工作：它在列表中寻找最小的项目并将其放在列表的前面（确保该项目位于正确的位置）或寻找最大的项目并将其放在列表的前面列表的后面。

选择排序的动画。红色是当前最小值。黄色是一个排序列表。蓝色是当前项目。

 def selectionSort(data):
for scanIndex in range(0, len(data)):
minIndex = scanIndex
for compIndex in range(scanIndex + 1, len(data)):
if data[compIndex] < data[minIndex]:
minIndex = compIndex
if minIndex != scanIndex:
data[scanIndex], data[minIndex] = data[minIndex], data[scanIndex]
print(data)

选择排序与冒泡排序具有相同的复杂性。选择排序用于以下情况：

• 排序小数组
• 检查所有元素是强制性的
• 需要更少的交换

3. 插入排序

插入排序是一种蛮力排序算法，但它比选择排序进行更少的比较。插入排序通过选择一个项目并通过排序直接邻居来工作，无论它们是否大于/小于所选项目。随着已排序项目的数量增加，该算法会根据已排序项目检查新项目，并将新项目插入列表中的正确位置。

 def insertionSort(data):
for scanIndex in range(1, len(data)):
tmp = data[scanIndex]
minIndex = scanIndex
while minIndex > 0 and tmp < data[minIndex - 1]:
data[minIndex] = data[minIndex - 1]
minIndex -= 1
data[minIndex] = tmp
print(data)

• 插入排序的最坏平均复杂度为 O(n2)。当数组以相反顺序排序以及元素在数组中任意组织时，会分别发生这种情况。
• 最佳情况复杂度为 O(n)。它发生在数据已经按所需顺序排序时。

在以下情况下使用插入排序：

• 还有一些元素需要排序；
• 数组很小。

4.快速排序

快速排序是一种高效的排序算法。它使用分而治之的方法将数组拆分为递归调用的子数组来对元素进行排序。实现一个快速排序算法需要选择一个pivot，然后根据pivot将数组拆分成两个子数组，如果它们大于/小于pivot，则将它们排列在后面。然后我们对两个子数组进行排序并再次重复该过程。

def quickSort(data, left, right):
if right<= left:
return 
else:
pivot = partition(data, left, right)
quickSort(data, left, pivot - 1)
quickSort(data, pivot + 1, right)
return data
def partition(data, left, right):
pivot = data[left]
leftIndex = left + 1
rightIndex = right
while True:
while leftIndex <= rightIndex and data[leftIndex] <= pivot:
leftIndex += 1
while rightIndex >= leftIndex and data[rightIndex] >= pivot:
rightIndex -= 1
if rightIndex <= leftIndex:
break
data[leftIndex], data[rightIndex] = data[rightIndex], data [leftIndex]
print(data)
data[left], data[rightIndex] = data[rightIndex], data[left]
print(data)
return rightIndex

• 快速排序的最坏情况复杂度为 O(n2)。
• 最好情况和平均情况的复杂度是 O(n*log(n))。当枢轴元素始终位于中间元素或靠近中间元素时，就会发生这种情况。

快速排序 用于以下情况：

• 需要并支持递归；
• 数组很小；
• 还有一些元素需要排序。

5.归并排序

归并排序通过应用分而治之的方法来工作。排序首先将数据集分解成单独的部分并对这些部分进行排序。然后它以确保已对合并的片段进行排序的方式合并这些片段。排序和合并一直持续到整个数据集再次成为一个整体。

归并排序的一个例子。首先将列表划分为最小单元（1个元素），然后将每个元素与相邻的列表进行比较，对相邻的两个列表进行排序合并。最后，对所有元素进行排序和合并。

def mergeSort(data):
if len(data) < 2:
return data
middle = len(data)//2
left = mergeSort(data[:middle])
right = mergeSort(data[middle:])
print("The left side is: ", left)
print("The right side is: ", right)
merged = merge(left, right)
print("Merged ", merged)
return merged
def merge(left, right):
if not len(left):
return left
if not len(right):
return right
result = []
leftIndex = 0
rightIndex = 0
totalLen = len(left) + len(right)
while (len(result) < totalLen):
if left[leftIndex] < right[rightIndex]:
result.append(left[leftIndex])
leftIndex += 1
else:
result.append(right[rightIndex])
rightIndex += 1
if leftIndex == len(left) or rightIndex == len(right):
result.extend(left[leftIndex:] or right[rightIndex:])
break
return result

• 归并排序具有 O(n*log(n)) 的最坏情况和平均情况复杂度，这使得它比其他一些排序算法最快。

6.桶排序

桶排序算法通过将数组划分为桶来工作。然后使用任何排序算法或通过递归调用桶排序算法对每个桶中的元素进行排序。桶排序的过程可以看作是一种分散-聚集方法。首先将元素分散到桶中，然后对桶中的元素进行排序。最后，按顺序收集元素。

def bucketSort(array):
bucket = []
for i in range(len(array)):
bucket.append([])
for j in array:
index_b = int(10 * j) # 浮动数转化为整数插入不同的桶，如果是整数应该是用除以10。
bucket[index_b].append(j)
for i in range(len(array)):
bucket[i] = sorted(bucket[i])
k = 0
for i in range(len(array)):
for j in range(len(bucket[i])):
array[k] = bucket[i][j]
k += 1
return array
array = [0.12, 0.44, 0.56, 0.52, 0.37, 0.47, 0.51]
print("Sorted Array in descending order is")
print(bucketSort(array))

• 桶排序算法的最坏情况复杂度为 O(n2)。当相同范围内的元素被放入同一个桶时，会发生这种情况，导致某些桶中的元素多于其他桶。此外，如果使用不适当的排序算法对存储桶中的元素进行排序，情况可能会更糟。
• 最佳情况复杂度为 O(n+k)。当元素均匀分布在桶中且每个桶中的元素数量几乎相等时，就会发生这种情况。如果数组已经排序，它甚至会更好。
• 平均情况复杂度为 O(n)。它发生在元素随机分布在数组中时。

桶排序用于以下情况：

• 带有浮动数字；
• 输入在一个范围内均匀分布。

7. 希尔排序

希尔排序是插入排序的一种变体。使用此算法，数组将根据所选序列以特定间隔排序。元素之间的间隔根据使用的顺序逐渐减小。希尔排序的性能取决于用于给定输入数组的序列类型。

 def shellSort(data, length):
gap = length//2
while gap > 0:
for iIndex in range(gap, length):
temp = data[iIndex]
jIndex = iIndex
while jIndex >= gap and data[jIndex - gap] > temp:
data[jIndex] = data[jIndex - gap]
jIndex -= gap
data[jIndex] = temp
gap //= 2
print(data)

• 希尔排序的最坏情况复杂度小于或等于 O(n2)。
• 希尔排序的平均情况和最佳情况复杂度为O(n*log(n)).
• 希尔排序用于以下情况：

• • 递归超出限制。
  • 当靠近的元素很远时，插入效果不佳。

堆排序

堆排序是最好的就地排序方法之一，没有二次最坏情况的复杂性。堆排序使用堆数据结构。堆是一棵完全二叉树。它还验证以下规则：

• 孩子比父母小；
• 最大/最小元素位于堆的根部，具体取决于你对它进行排序的方式。

要进行堆排序算法，我们必须首先创建数组的堆。完成后，我们现在可以编写堆排序算法。堆排序的优点是根的值总是大于所有的值，所以我们可以把它放在排序后的数组的末尾，从堆中移除，然后再次堆化二叉树以获得更大的值再次在顶部。

def createHeap(data, length, index):
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < length and data[index] < data[left]:
largest = left
if right < length and data[largest] < data[right]:
largest = right
if largest != index:
data[index], data[largest] = data[largest], data[index]
createHeap(data, length, largest)
def heapSort(data):
length = len(data)
for index in range(length, 0, -1):
createHeap(data, length, index)
for index in range(length -1, 0, -1):
data[index], data[0] = data[0], data[index]
createHeap(data, index, 0)
print(data)

堆排序在所有情况下（最佳情况、平均情况和最坏情况）都具有 O(n*log(n)) 时间复杂度，使其成为最常用的排序算法之一。当你只需要知道项目集合的“最小”（或“最大”）项时，Heapsort 非常有用，而无需将剩余项目按排序顺序保持开销。例如，优先队列。

结论

在本文中，我向你展示了算法及其在 Python 中的实现。文章可以做得更好，因此欢迎在评论部分提出你的建议或问题。

如果你也认为我遗漏了一些重要的排序算法，请告诉我。