排序
1. 冒泡排序(Bubble Sort)
基本原理:
冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
应用场景:
适用于数据量较小且基本有序的数列排序。
优点:
- 实现简单。
- 对基本有序的数列排序效率较高。
缺点:
- 时间复杂度较高,最坏情况下是O(n^2)。
- 对于大数据集效率低下。
Python实现:
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]return arr# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
bubble_sort(arr)
print("排序后数组:", arr)
2. 选择排序(Selection Sort)
基本原理:
选择排序是一种简单直观的排序算法。它的工作原理是,首先在未排序序列中找到最小(或最大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
应用场景:
适用于数据量较小的情况,或用于解决特定问题,如查找第k小的元素。
优点:
- 实现简单。
- 交换次数少,数据移动少。
缺点:
- 时间复杂度较高,为O(n^2)。
- 对于大数据集排序效率低下。
Python实现:
def selection_sort(arr):for i in range(len(arr)):min_index = ifor j in range(i+1, len(arr)):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]return arr# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
selection_sort(arr)
print("排序后数组:", arr)
3. 插入排序(Insertion Sort)
基本原理:
插入排序的工作方式是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
应用场景:
适用于数据量较小,且数据基本有序的情况。也常用于将数据插入到已排序的数组中。
优点:
- 实现简单。
- 对基本有序的数据排序效率高。
- 稳定排序。
缺点:
- 对于大数据集或无序数据集效率较低,时间复杂度最坏为O(n^2)。
- 需要移动大量元素。
Python实现:
def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = keyreturn arr# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
insertion_sort(arr)
print("排序后数组:", arr)
4. 归并排序(Merge Sort)
基本原理:
归并排序是一种分治策略的排序算法。它将一个大数组分割成两个小数组,分别对这两个小数组进行排序,然后将这两个已排序的小数组合并成一个大的有序数组。
应用场景:
归并排序适用于对大量数据进行排序,尤其是外部排序(即数据太大,无法全部加载到内存中)。在数据库管理系统和文件系统中常用。
优点:
- 稳定排序算法。
- 时间复杂度为O(n log n),效率较高。
缺点:
- 需要额外的空间来存储中间结果。
Python实现:
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):merged = []left_index, right_index = 0, 0while left_index < len(left) and right_index < len(right):if left[left_index] <= right[right_index]:merged.append(left[left_index])left_index += 1else:merged.append(right[right_index])right_index += 1merged.extend(left[left_index:])merged.extend(right[right_index:])return merged# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
r = merge_sort(arr)
print("排序后数组:", r)
5. 快速排序(Quick Sort)
基本原理:
快速排序也是一种分治策略的排序算法。它通过选取一个“基准值”(pivot),将数组分为两个子数组,一个包含比基准值小的元素,另一个包含比基准值大的元素,然后递归地对这两个子数组进行快速排序。
应用场景:
快速排序在内存中对大数据集进行排序时非常高效,是许多编程语言和库中的默认排序算法。
优点:
- 平均时间复杂度为O(n log n),且常数因子较小。
- 内部循环可以在大多数实际系统上高效实现。
缺点:
- 在最坏情况下,时间复杂度会退化为O(n^2)。
- 不是稳定排序算法。
Python实现:
def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)# 示例
arr = [5, 3, 7, 6, 2, 9, 1, 4, 8]
sorted_arr = quick_sort(arr)
print(sorted_arr)
6. 堆排序(Heap Sort)
基本原理:
堆排序利用二叉堆(通常是大根堆)的性质来进行排序。首先构建一个最大堆,然后将堆顶元素(最大值)与最后一个元素交换,之后重新调整堆结构,使其仍然保持最大堆的性质。重复此过程,直到堆的大小变为1。
应用场景:
堆排序适用于需要快速找到一系列数中的最大(或最小)值,并对其进行排序的场景。它也被用于实现优先级队列。
优点:
- 时间复杂度为O(n log n),且最坏情况与平均情况相同。
- 可以在不完全有序的数据集上高效工作。
缺点:
- 不是稳定排序算法。
- 由于元素交换的不确定性,缓存不命中的可能性较高。
Python实现:
def heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[i] < arr[l]:largest = lif r < n and arr[largest] < arr[r]:largest = rif 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)return arr# 示例
arr = [5, 3, 7, 6, 2, 9, 1, 4, 8]
sorted_arr = heap_sort(arr)
print(sorted_arr)
7. 希尔排序(Shell Sort)
基本原理:
希尔排序是插入排序的一种优化版本。它首先将待排序的数组元素按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减少到1时,整个数组被分为一组,算法便终止。
应用场景:
适用于中等大小的数据集排序,特别是当数据部分有序时表现较好。
优点:
- 相对于直接插入排序,希尔排序通过分组减少了比较和移动的次数,提高了效率。
缺点:
- 算法性能受增量序列的选择影响较大。
- 不是稳定排序算法,即可能改变相等元素的相对顺序。
Python实现:
def shell_sort(arr):n = len(arr)gap = n // 2while gap > 0:for i in range(gap, n):temp = arr[i]j = iwhile j >= gap and arr[j - gap] > temp:arr[j] = arr[j - gap]j -= gaparr[j] = tempgap //= 2return arr# 示例
arr = [9, 8, 3, 7, 5, 6, 4, 1]
print(shell_sort(arr)) # 输出: [1, 3, 4, 5, 6, 7, 8, 9]
8. 计数排序(Counting Sort)
基本原理:
计数排序是一种非比较的排序算法,适用于一个特定范围内的整数排序。它使用一个额外的数组来统计每个整数出现的次数,然后根据计数的结果将输入的数组排序。
应用场景:
适用于一定范围内的整数排序,特别是当数据范围较小且数据量大时效率很高。
优点:
- 时间复杂度为O(n+k),其中k是整数的范围,当k不是很大时,算法效率很高。
- 是一种稳定排序算法。
缺点:
- 当整数的范围k很大时,需要较大的额外空间,造成空间浪费。
- 只能用于整数排序。
Python实现:
def counting_sort(arr):max_val = max(arr)count = [0] * (max_val + 1)for num in arr:count[num] += 1output = []for i in range(len(count)):output.extend([i] * count[i])return output# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr)) # 输出: [1, 2, 2, 3, 3, 4, 8]
9. 桶排序(Bucket Sort)
基本原理:
桶排序是将数组分到有限数量的桶中,每个桶再分别排序(通常使用其他排序算法或是以递归方式继续使用桶排序进行排序)。最后,将各个桶中的数据合并起来。
应用场景:
适用于数据均匀分布在一个范围较大的区间内,且数据量较大的情况。
优点:
- 当数据量很大且分布均匀时,桶排序的效率很高,时间复杂度可以接近O(n)。
- 可以并行处理多个桶,进一步提高效率。
缺点:
- 当数据分布不均匀时,可能会导致某些桶的数据过多,从而降低效率。
- 需要额外的空间来存储桶。
- 不是稳定排序算法。
Python实现:
def bucket_sort(arr):max_val = max(arr)bucket_range = 10 # 假设每个桶的范围是10,这个值可以根据实际情况调整num_buckets = (max_val // bucket_range) + 1buckets = [[] for _ in range(num_buckets)]for num in arr:index = num // bucket_rangebuckets[index].append(num)sorted_arr = []for bucket in buckets:# 这里为了简单起见,使用了内置的sorted函数,实际应用中可以替换为其他排序算法sorted_arr.extend(sorted(bucket))return sorted_arr# 示例
arr = [9, 2, 0, 17, 4, 31, 13, 8, 6]
print(bucket_sort(arr)) # 输出一个排序后的数组
10.基数排序(Radix Sort)
基本原理:
基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数进行排序。通常,基数排序会从最低位开始,对每一位进行排序,然后再按更高位排序,直到最高位。对于每一位,可以使用稳定的排序算法(如计数排序或桶排序)来确保相同位数的数字按原始顺序排列,从而保证整体排序的稳定性。
应用场景:
基数排序特别适用于对大量整数进行排序,尤其是当这些整数的位数相对固定且不太长时。例如,在处理大量的手机号、身份证号或其他具有固定格式的数字序列时,基数排序能表现出很高的效率。
优点:
- 稳定性好:基数排序是稳定的排序算法,即相同值的元素在排序后保持其原有的顺序。
- 效率较高:对于大量整数排序,尤其是位数不多的情况,基数排序的性能通常优于比较型排序算法。
缺点:
- 局限性大:基数排序主要用于整数排序,对于非整数类型的数据,如字符串或对象,需要额外的转换步骤。
- 空间消耗:基数排序需要额外的空间来存储临时排序结果,这可能会增加内存消耗。
Python实现:
def radix_sort(arr):# 找到最大数的位数max_val = max(arr)max_digit = len(str(max_val))# 从最低位到最高位依次排序for k in range(max_digit):# 使用计数排序作为子排序算法bucket = [[] for _ in range(10)]for i in arr:# 获取当前位的数字digit = (i // (10**k)) % 10bucket[digit].append(i)# 重新组合数组arr = [j for i in bucket for j in i]return arr# 示例
arr = [121, 432, 564, 23, 1, 45, 788]
print("原始数组:", arr)
sorted_arr = radix_sort(arr)
print("排序后数组:", sorted_arr)
在这个Python示例中,我们实现了基数排序算法,使用了计数排序作为子排序过程。算法首先确定最大数的位数,然后从最低位开始,对每一位进行排序。这个过程会重复进行,直到处理完最高位。注意,这里的实现是基于整数的排序,并且假设了所有数都是非负的。如果需要处理负数或浮点数,算法将需要额外的处理步骤。
注意:在实际应用中,为了提高效率,通常会对这些基本算法进行一些优化和改进。上面的Python实现主要是为了展示算法的基本原理,可能不是最优的实现方式。