其他常见的排序算法

简介: 其他常见的排序算法

除了插入排序和选择排序之外,还有许多其他常见的排序算法,每种算法都有其独特的特点和适用场景。下面介绍几种常见的排序算法及其基本原理:

 

快速排序(Quick Sort)

快速排序是一种分治算法,它的基本思想是选择一个基准元素,将序列分为两部分,使得左边的元素都小于基准元素,右边的元素都大于基准元素,然后递归地对左右两部分进行排序。具体步骤如下:

 

1. 选择一个基准元素(通常是第一个元素)。

2. 将序列分为两部分,左边部分所有元素小于基准元素,右边部分所有元素大于基准元素。

3. 对左右两部分分别递归地进行快速排序。

 

快速排序的 Python 实现如下:

```python
def quick_sort(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 quick_sort(left) + [pivot] + quick_sort(right)
 
# 示例
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)
```

归并排序(Merge Sort) 

归并排序是一种稳定的排序算法,它采用分治策略,将待排序序列分为若干个子序列,分别排序后再合并成一个有序序列。具体步骤如下:

1. 将序列分为两个子序列,分别进行归并排序。

2. 将两个排好序的子序列合并成一个有序序列。

 

归并排序的 Python 实现如下:

```python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(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.extend(left[i:])
    result.extend(right[j:])
    return result
 
# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("排序后的数组:", sorted_arr)
```

堆排序(Heap Sort)

堆排序利用堆这种数据结构来进行排序,堆可以看成一棵完全二叉树,具有以下性质:

- 大根堆(大顶堆):每个节点的值都大于或等于其左右孩子节点的值。

- 小根堆(小顶堆):每个节点的值都小于或等于其左右孩子节点的值。

 

堆排序的基本思想是先构建一个大根堆,然后将堆顶元素与堆的最后一个元素交换,然后调整堆,重复这个过程直到整个序列有序。


堆排序的 Python 实现如下:

```python
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)
 
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 = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("排序后的数组:", arr)
```

以上就是快速排序、归并排序和堆排序的基本原理和实现。这些排序算法在不同的场景下有着不同的性能表现,选择合适的排序算法可以提高算法效率。

相关文章
|
2月前
|
搜索推荐
简单的排序算法
简单的排序算法
28 1
|
2月前
|
搜索推荐 C++
7大排序算法C++实现
7大排序算法C++实现
50 0
|
2月前
|
搜索推荐 算法 C语言
c排序算法
c排序算法
22 0
|
24天前
|
搜索推荐 算法 Python
排序算法1
排序算法1
|
2月前
|
搜索推荐
直接选择排序算法
直接选择排序算法
20 0
|
9月前
|
搜索推荐 Java C++
简单介绍排序算法
简单介绍排序算法
24 0
|
算法 搜索推荐
排序算法的简单认识
在进行很多便捷算法之前总是要实现对象的有序化,而这就将使用到排序相关的算法,即使目前诸多高级语言已然完成对于排序算法的封装,用户只需导入对应库文件即可调用排序算法完成排序,无需手写排序算法,但具体的排序算法的选择就必须对于排序算法有所认识。本文就将介绍两个简单的排序算法:选择排序与冒泡排序。 选择排序 为什么称为选择排序? 该算法每次都是对于未排序的关键字进行比较,选择出最小或最大的关键字,再对其交换位置,实现一次排序,需进行多次比较。 选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元
59 0
|
搜索推荐
排序算法总结
经典排序算法总结
56 0
|
搜索推荐 算法
|
算法 搜索推荐 C++