排序算法是计算机科学中的基础，无论是数据结构还是算法设计中，排序算法都是不可或缺的一部分。掌握排序技巧不仅可以帮助我们更高效地处理数据，还能在面试和实际工作中展现出你的算法能力。以下，我将通过10个实用的例题，帮助你轻松掌握排序技巧。
例题1：冒泡排序
题目描述： 对以下数组进行冒泡排序：[64, 34, 25, 12, 22, 11, 90]
解题思路： 冒泡排序的基本思想是通过相邻元素的比较和交换，将较大的元素逐步“冒泡”到数组的末尾。
代码实现：
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)
例题2：选择排序
题目描述： 对以下数组进行选择排序：[5, 2, 9, 1, 5, 6]
解题思路： 选择排序的基本思想是每次从剩余未排序的元素中找到最小（或最大）的元素，放到已排序序列的末尾。
代码实现：
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
arr = [5, 2, 9, 1, 5, 6]
selection_sort(arr)
print("Sorted array is:", arr)
例题3：插入排序
题目描述： 对以下数组进行插入排序：[8, 2, 7, 3, 9, 5, 4]
解题思路： 插入排序的基本思想是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增加1的有序表。
代码实现：
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >=0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
arr = [8, 2, 7, 3, 9, 5, 4]
insertion_sort(arr)
print("Sorted array is:", arr)
例题4：快速排序
题目描述： 对以下数组进行快速排序：[10, 7, 8, 9, 1, 5]
解题思路： 快速排序的基本思想是通过一个基准值将数组分为两个子数组，使得左边的元素都比基准值小，右边的元素都比基准值大，然后递归地对这两个子数组进行快速排序。
代码实现：
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr)-1)
print("Sorted array is:", arr)
例题5：归并排序
题目描述： 对以下数组进行归并排序：[12, 11, 13, 5, 6, 7]
解题思路： 归并排序的基本思想是将数组分成两个子数组，递归地对这两个子数组进行归并排序，然后将排序好的子数组合并成一个有序数组。
代码实现：
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Sorted array is:", arr)
例题6：堆排序
题目描述： 对以下数组进行堆排序：[4, 10, 3, 5, 1]
解题思路： 堆排序的基本思想是将数组构造成一个大顶堆，然后交换堆顶元素与数组末尾元素，然后调整剩余元素重新构造成大顶堆，重复此过程直到整个数组排序。
代码实现：
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print("Sorted array is:", arr)
例题7：希尔排序
题目描述： 对以下数组进行希尔排序：[25, 12, 22, 35, 15, 1, 74]
解题思路： 希尔排序是插入排序的一种更高效的改进版本。基本思想是先取一个小于n的整数d1作为第一个增量，把全部记录分成d1个组，每组中记录的下标相差d1。先在各组内进行直接插入排序；然后，取d1的平方作为增量d2，重复上述分组和排序工作；再取d2的平方作为增量d3，重复上述工作；以此类推，直到增量d为1，也就是所有的记录都相邻时为止。
代码实现：
def shell_sort(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
arr = [25, 12, 22, 35, 15, 1, 74]
shell_sort(arr)
print("Sorted array is:", arr)
例题8：计数排序
题目描述： 对以下数组进行计数排序：[4, 2, 2, 8, 3, 3, 1]
解题思路： 计数排序的基本思想是找出数组中最大和最小的元素，然后使用这两个元素初始化计数数组。计数数组中的每个计数代表原数组中该元素出现的次数。
代码实现：
def counting_sort(arr):
max_val = max(arr)
min_val = min(arr)
range_val = max_val - min_val + 1
count_arr = [0] * range_val
for num in arr:
count_arr[num - min_val] += 1
i = 0
for num in range(range_val):
while count_arr[num] > 0:
arr[i] = num + min_val
i += 1
count_arr[num] -= 1
arr = [4, 2, 2, 8, 3, 3, 1]
counting_sort(arr)
print("Sorted array is:", arr)
例题9：基数排序
题目描述： 对以下数组进行基数排序：[170, 45, 75, 90, 802, 24, 2, 66]
解题思路： 基数排序是一种非比较排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数进行比较排序。
代码实现：
def counting_sort_for_radix(arr, position):
n = len(arr)
output = [0] * n
count = [0] * 10
for num in arr:
index = (num // position) % 10
count[index] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = (arr[i] // position) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_val = max(arr)
position = 1
while max_val // position > 0:
counting_sort_for_radix(arr, position)
position *= 10
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array is:", arr)
例题10：桶排序
题目描述： 对以下数组进行桶排序：[0.42, 0.32, 0.59, 0.26, 0.77, 0.05, 0.61]
解题思路： 桶排序的基本思想是将数值划分到有限数量的桶中，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
代码实现：
def bucket_sort(arr):
if len(arr) == 0:
return []
min_val, max_val = min(arr), max(arr)
bucket_range = max_val - min_val + 1
buckets = [[] for _ in range(bucket_range)]
for num in arr:
buckets[int(num - min_val)].append(num)
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(sorted(bucket))
return sorted_arr
arr = [0.42, 0.32, 0.59, 0.26, 0.77, 0.05, 0.61]
sorted_arr = bucket_sort(arr)
print("Sorted array is:", sorted_arr)
通过以上10个例题，相信你已经对排序算法有了更深入的理解。排序算法的选择和运用对于数据处理和分析至关重要，希望这些例题能够帮助你更好地掌握排序技巧。