使用插入排序,冒泡排序,快速排序,来排序这个数组{4,2,6,3,2,7,9,3,5}。要求是从大到小进行排序。(上面的代码是从小到大排序)。
时间: 2025-01-05 13:41:24 浏览: 4
对于从大到小排序,我们需要对上述提到的排序算法稍作修改。下面是这三种排序算法在保持原有逻辑的基础上调整为降序排列:
1. **插入排序(Insertion Sort, 降序)**:
- 从第二个元素开始,遍历数组,将当前元素与前面已排序的部分比较,如果当前元素大于前面元素,则交换它们的位置。
- 持续这个过程,直到整个数组有序。
2. **冒泡排序(Bubble Sort, 降序)**:
- 重复地遍历数组,每次比较相邻的两个元素,如果前一个元素小于后一个元素则交换它们。
- 内循环结束后,最大的元素会被移动到数组末尾,然后外层循环再减少一次元素,直到数组完全排序。
3. **快速排序(Quick Sort, 降序)**:
- 选择数组中的最后一个元素作为“基准”。
- 将其他元素分为两部分,一部分比基准大,另一部分比基准小。
- 对这两部分分别递归地应用快速排序,然后将结果合并(通常情况下是倒序合并)。
请注意,插入排序、冒泡排序在处理大型数据集时效率较低,而快速排序通常是最快的,但对于大数据集,可以选择优化后的版本如三向切分的快速排序以提高性能。
以下是每种算法在Python中的示例,假设我们有一个名为`nums`的列表:
```python
# Insertion Sort (降序)
def insertion_sort_descending(nums):
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and key > nums[j]:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
# Bubble Sort (降序)
def bubble_sort_descending(nums):
n = len(nums)
for i in range(n-1):
for j in range(n-i-1):
if nums[j] < nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
# Quick Sort (降序)
def quicksort_descending(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
less = [x for x in arr[:-1] if x >= pivot]
greater = [x for x in arr[:-1] if x < pivot]
return quicksort_descending(greater) + [pivot] + quicksort_descending(less)
# 示例数组
nums = [4, 2, 6, 3, 2, 7, 9, 3, 5]
insertion_sort_descending(nums)
bubble_sort_descending(nums)
quicksort_descending(nums)
```
阅读全文