Python实现常见排序算法：冒泡、选择、插入及快速排序

"这份PDF文件涵盖了四种常见的排序算法在Python中的实现，包括冒泡排序、选择排序、插入排序以及快速排序。这些算法是计算机科学中最基础且重要的排序方法，对于理解和优化数据处理具有重要意义。" 在计算机科学中，排序算法是用于对一组数据进行排列的算法。这些算法在Python中的实现可以帮助我们更好地理解它们的工作原理，并在实际编程中灵活运用。以下是对四种排序算法的详细说明： 1. **冒泡排序**：冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。冒泡排序的时间复杂度为O(n^2)，在大数据量时效率较低。 ```python def bubbleSort(num): length = len(num) while length > 0: for i in range(length - 1): if num[i] > num[i + 1]: num[i], num[i + 1] = num[i + 1], num[i] length = length - 1 print(num) return num ``` 2. **选择排序**：选择排序的主要思想是在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的时间复杂度同样为O(n^2)。 ```python def selectSort(num): length = len(num) for i in range(length): tmpNum = i for j in range(i, length): if num[tmpNum] > num[j]: num[tmpNum], num[j] = num[j], num[tmpNum] print(num) return num ``` 3. **插入排序**：插入排序是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。它有两种实现方式，一种是直接插入，另一种是希尔排序（改进的插入排序）。这两种实现方法的时间复杂度在最坏情况下都是O(n^2)，但在最好情况下（即输入已经是排序好的）能达到O(n)。 ```python # 直接插入排序 def insertSort(num): length = len(num) for i in range(1, length): tmp = num[i] for j in range(i, -1, -1): if num[j] > tmp: num[j + 1], num[j] = num[j], num[j + 1] print(num) return num # 插入排序（希尔排序） def insertSort2(num): length = len(num) for i in range(1, length): tmp = num[i] tmpi = i - 1 while tmpi >= 0 and num[tmpi] > tmp: num[tmpi], num[tmpi + 1] = num[tmpi + 1], num[tmpi] tmpi = tmpi - 1 pass print(num) return num ``` 4. **快速排序**：快速排序是由C.A.R. Hoare提出的一种非常有效的排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序的平均时间复杂度为O(n log n)，但最坏情况下的时间复杂度为O(n^2)。 ```python # 快速排序的实现通常包含递归部分，这里省略了 ``` 以上四种排序算法各有优劣，适用于不同的场景。在实际应用中，我们往往会选择时间复杂度更低的排序算法，例如快速排序和归并排序等，以提高程序的运行效率。同时，了解这些基础排序算法也有助于理解更复杂的算法，如归并排序、堆排序等。在学习和实践中，我们需要根据具体的需求来选择合适的排序算法。