【排序算法】

发布于:2024-11-29 ⋅ 阅读:(23) ⋅ 点赞:(0)

冒泡排序算法

冒泡排序算法(Bubble Sort)是一种简单直观的排序算法,其基本思想是通过重复遍历待排序的数列,一次比较两个元素,如果它们的顺序错误就交换它们的位置,直到整个数列有序。以下是冒泡排序算法的详细解释:

一、算法步骤

‌比较相邻的元素‌:

从数列的第一个元素开始,依次比较相邻的两个元素。
如果前一个元素比后一个元素大,则交换它们的位置。

‌对每一对相邻元素进行比较和交换‌:

这一过程需要重复进行,直到没有任何一对元素需要交换为止。

‌重复上述过程‌:

对于长度为n的数列,需要进行n-1次遍历。
每次遍历后,最大的元素都会“冒泡”到数列的末尾。

‌优化(可选)‌:

为了减少不必要的比较,可以在每次遍历中设置一个标志位。
如果在某次遍历中没有发生任何交换,说明数列已经有序,可以提前结束算法。
二、算法示例

以数列[5, 1, 4, 2, 8]为例,进行冒泡排序的过程如下:

第一次遍历:

比较5和1,交换位置:[1, 5, 4, 2, 8]
比较5和4,交换位置:[1, 4, 5, 2, 8]
比较5和2,交换位置:[1, 4, 2, 5, 8]
比较5和8,不交换位置:[1, 4, 2, 5, 8]
最大的元素8“冒泡”到末尾。

第二次遍历:

比较1和4,不交换位置:[1, 4, 2, 5, 8]
比较4和2,交换位置:[1, 2, 4, 5, 8]
比较4和5,不交换位置:[1, 2, 4, 5, 8]
次大的元素5“冒泡”到倒数第二个位置。

第三次遍历:

比较1和2,不交换位置:[1, 2, 4, 5, 8]
比较2和4,不交换位置:[1, 2, 4, 5, 8]
数列已经有序,算法结束。
三、算法分析

‌时间复杂度‌:

最坏情况下,时间复杂度为O(n2),其中n是数列的长度。
这是因为需要进行n-1次遍历,每次遍历需要比较n-1-i次(i为当前遍历的轮数)。

‌空间复杂度‌:

冒泡排序是原地排序算法,空间复杂度为O(1)。

‌稳定性‌:

冒泡排序是稳定的排序算法,不会改变相等元素的相对顺序。
四、优缺点

‌优点‌:

算法简单易懂,实现方便。

‌缺点‌:

时间复杂度较高,不适用于大规模数据排序。
五、代码实现(Python)
python
Copy Code
def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        swapped = False
        for j in range(n-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# 示例
arr = [5, 1, 4, 2, 8]
sorted_arr = bubble_sort(arr)
print(sorted_arr)  # 输出:[1, 2, 4, 5, 8]
冒泡排序算法虽然简单易懂,但由于其时间复杂度较高,通常不适用于大规模数据的排序。

插入排序算法

插入排序算法(Insertion Sort)是一种简单直观的排序算法,通常用于小规模数据的排序。以下是插入排序算法的详细解释:

一、算法思想

插入排序的基本思想是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。这个过程类似于我们打扑克牌时,手上已经有一些排好序的牌,然后再从剩下的牌中一张一张地取出来,插到已经排好序的牌中的适当位置。

二、算法步骤

‌初始状态‌:

将待排序的数列看作是一个从无序到有序的过程。
初始时,第一个元素被认为是有序的,而剩下的元素被认为是无序的。

‌扫描与插入‌:

从数列的第二个元素开始,依次扫描每个元素。
对于当前扫描的元素,将其与已排序部分的元素进行比较,找到其应该插入的位置。
将当前元素插入到已排序部分的适当位置,使得已排序部分依然有序。

‌重复过程‌:

重复上述扫描与插入的过程,直到所有无序部分的元素都被插入到已排序部分中。

‌完成排序‌:

当所有元素都被插入到已排序部分中时,整个数列就变得有序了。
三、算法示例

以数列[5, 2, 9, 1, 5, 6]为例,进行插入排序的过程如下:

初始状态:(已排序),[2, 9, 1, 5, 6](未排序)
扫描到2,将2插入到5之前:[2, 5](已排序),[9, 1, 5, 6](未排序)
扫描到9,9比5大,直接放在5后面:[2, 5, 9](已排序),[1, 5, 6](未排序)
扫描到1,将1插入到2之前:[1, 2, 5, 9](已排序),[5, 6](未排序)
扫描到5,5比9小但比5大(与已排序部分的最后一个5相等,但不影响排序),直接放在最后一个5后面(或保持原位置):[1, 2, 5, 5, 9](已排序),(未排序)
扫描到6,6比9小,直接放在9前面:[1, 2, 5, 5, 6, 9](已排序),无未排序部分
四、算法分析

‌时间复杂度‌:

最好情况下,时间复杂度为O(n),即数列已经有序的情况。
最坏情况下,时间复杂度为O(n2),即数列是逆序的情况。
平均情况下,时间复杂度也为O(n2)。

‌空间复杂度‌:

插入排序是原地排序算法,空间复杂度为O(1)。

‌稳定性‌:

插入排序是稳定的排序算法,不会改变相等元素的相对顺序。
五、优缺点

‌优点‌:

算法简单易懂,实现方便。
对于小规模数据或基本有序的数据,排序效率较高。

‌缺点‌:

对于大规模数据或无序数据,排序效率较低。
六、代码实现(Python)
python
Copy Code
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
    return arr

# 示例
arr = [5, 2, 9, 1, 5, 6]
sorted_arr = insertion_sort(arr)
print(sorted_arr)  # 输出:[1, 2, 5, 5, 6, 9]


插入排序算法适用于小规模数据或基本有序的数据的排序。

快速排序算法

快速排序算法(Quick Sort)是一种高效的排序算法,由C. A. R. Hoare在1960年提出。它以其高效性和广泛应用性成为了最常用的排序算法之一。以下是快速排序算法的详细解释:

一、算法思想

快速排序的基本思想是分治法(Divide and Conquer)。它通过选定一个基准元素(Pivot),将待排序的数列分成两个子数列:一个子数列中的元素都比基准元素小,另一个子数列中的元素都比基准元素大。然后,再对这两个子数列分别进行快速排序,直到整个数列有序。

二、算法步骤

‌选择基准元素‌:

从数列中选择一个元素作为基准元素。选择基准元素的方式有多种,常见的是选择第一个元素、最后一个元素、中间元素或随机选择一个元素。

‌分区‌:

根据基准元素,将数列分成两个子数列:左子数列(元素小于基准元素)和右子数列(元素大于基准元素)。
在分区过程中,通常使用两个指针(low和high)来遍历数列,并交换元素以确保左子数列和右子数列的正确性。

‌递归排序‌:

对左子数列和右子数列分别进行快速排序。这是通过递归调用快速排序函数来实现的。

‌合并‌:

由于快速排序是原地排序算法,所以不需要像归并排序那样合并子数列。在递归排序过程中,左子数列和右子数列已经分别有序,且基准元素位于它们之间,所以整个数列在递归结束后就变得有序了。
三、算法示例

以数列[3, 6, 8, 10, 1, 2, 1]为例,进行快速排序的过程如下:

选择基准元素:选择第一个元素3作为基准元素。
分区:将数列分成[1, 2, 1](左子数列)和[6, 8, 10](右子数列),基准元素3位于它们之间。
递归排序:对左子数列[1, 2, 1]和右子数列[6, 8, 10]分别进行快速排序。
对左子数列[1, 2, 1]进行快速排序:选择1作为基准元素,分成[](左子数列)和[2, 1](右子数列),再对右子数列进行快速排序,最终得到[1, 1, 2]。
对右子数列[6, 8, 10]进行快速排序:选择6作为基准元素,分成[](左子数列)和[8, 10](右子数列),由于右子数列已经有序,所以不需要再排序,最终得到[6, 8, 10]。
合并:由于快速排序是原地排序算法,所以不需要合并步骤。在递归排序过程中,数列已经变得有序了。
四、算法分析

‌时间复杂度‌:

最好情况下,时间复杂度为O(n log n),即每次分区都能将数列均匀地分成两部分。
最坏情况下,时间复杂度为O(n2),即每次分区都只能将数列分成一个元素和其余元素两部分(例如,数列已经有序或逆序)。
平均情况下,时间复杂度为O(n log n)。

‌空间复杂度‌:

快速排序的空间复杂度主要取决于递归调用的栈空间。最好情况下,空间复杂度为O(log n);最坏情况下,空间复杂度为O(n)。
由于快速排序是原地排序算法,所以不需要额外的数组空间来存储排序结果。

‌稳定性‌:

快速排序不是稳定的排序算法,因为它可能会改变相等元素的相对顺序。在分区过程中,当遇到相等元素时,它们的相对位置可能会发生变化。
五、优缺点

‌优点‌:

高效性:在平均情况下,快速排序的时间复杂度为O(n log n),比许多其他排序算法都要快。
原地排序:不需要额外的数组空间来存储排序结果,节省了内存。

‌缺点‌:

不稳定性:快速排序可能会改变相等元素的相对顺序。
对初始状态敏感:如果数列已经有序或逆序,快速排序的效率会降低到O(n2)。可以通过随机选择基准元素或采用其他优化方法来改善这种情况。
六、代码实现(Python)
python
Copy Code
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr  # 选择第一个元素作为基准元素
    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 = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 输出:[1, 1, 2, 3, 6, 8, 10]


注意:上述代码实现虽然简洁易懂,但不是原地排序的版本。在实际应用中,为了节省内存和提高效率,通常会采用原地排序的版本,并使用两个指针来进行分区操作。