排序算法是计算机科学中比较基础的一个领域，也是编程面试中常考的知识点。本文将介绍八大排序算法的Python实现，包括冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、堆排序和计数排序。
一、冒泡排序
冒泡排序是最简单的排序算法之一，它的基本思想是通过不断比较相邻元素，将较大的元素向后移动，最终将序列排好序。下面是冒泡排序的Python实现：
```python
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(n-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
```
二、选择排序
选择排序的基本思想是在未排序的元素中选择最小的元素放到已排序的末尾。下面是选择排序的Python实现：
```python
def selectionSort(arr):
n = len(arr)
for i in range(n-1):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
```
三、插入排序
插入排序的基本思想是将未排序的元素插入到已排序的合适位置。下面是插入排序的Python实现：
```python
def insertionSort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
```
四、快速排序
快速排序是一种高效的排序算法，它的基本思想是选择一个基准元素，将序列分成左右两部分，左边的元素都小于基准元素，右边的元素都大于基准元素，然后分别对左右两部分进行递归排序。下面是快速排序的Python实现：
```python
def quickSort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quickSort(left) + [pivot] + quickSort(right)
```
五、归并排序
归并排序的基本思想是将序列分成两部分，分别对两部分进行递归排序，然后将两部分合并。下面是归并排序的Python实现：
```python
def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
```
六、希尔排序
希尔排序是插入排序的改进版，它的基本思想是将序列分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的长度，最终将整个序列排序。下面是希尔排序的Python实现：
```python
def shellSort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap //= 2
return arr
```
七、堆排序
堆排序是一种利用堆的性质进行排序的算法，它的基本思想是将序列构建成一个大根堆或小根堆，然后依次将堆顶元素取出，直到堆为空。下面是堆排序的Python实现：
```python
def heapSort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
```
八、计数排序
计数排序是一种非比较排序算法，它的基本思想是对每个元素进行计数，然后根据计数结果将元素排好序。下面是计数排序的Python实现：
```python
def countingSort(arr):
max_val = max(arr)
counts = [0] * (max_val + 1)
for x in arr:
counts[x] += 1
result = []
for i in range(max_val + 1):
result += [i] * counts[i]
return result
```
结语
本文介绍了八大排序算法的Python实现，包括冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、堆排序和计数排序。这些排序算法各有优缺点，应根据实际情况选择合适的算法。需要注意的是，排序算法的时间复杂度和空间复杂度也是需要考虑的因素。
