快速排序是对冒泡排序的一种改进，由C. A. R. Hoare在1960年提出_快速排序是对起泡排序的一种改进-CSDN博客

本文链接：https://blog.csdn.net/blog_programb/article/details/145379173

快速排序是对冒泡排序的一种改进，由C. A. R. Hoare在1960年提出。

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

从待排序的记录序列中选取一个记录（通常第一个）作为基准元素（称为key），然后设置两个指针，low指向数列的最左部，high指向数据的最右部。以这个元素为中心点，把所有小于等于中心点的元素移动到中心点左边，大于中心点的元素移动到右边。

def partition(arr, low, high):
    key = arr[low]
    while low < high:
        while low < high and arr[high] >= key:
            high -= 1
        arr[low], arr[high] = arr[high], arr[low]
        while low < high and arr[low] <= key:
            low += 1
        arr[low], arr[high] = arr[high], arr[low]
    return low

def quick_sort_partition(arr, left, right):
    if left < right:
        pos = partition(arr, left, right)
        quick_sort_partition(arr, left, pos - 1)
        quick_sort_partition(arr, pos + 1, right)

快速排序使用分治法策略来分解问题，通常选取数组最左边的数作为基准数，并从两边进行检索以划分成两个子串。

平均情况下快速排序的时间复杂度为 O(n log n)，其中 n 是待排序元素的数量。这是因为每次分区操作大致可以将列表分成均匀的两部分，导致递归树的高度为 log n 层，每一层涉及总共 n 次比较。
最坏的情况下时间复杂度达到 O(n²)。这种情形发生在每次选择的基准都是当前序列中的最小值或最大值时，例如对已经排好序的数据再次应用快速排序，这使得分割极不平衡，造成递归深度达到 n 层。

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = 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 quicksort(left) + middle + quicksort(right)

对于插入排序的时间复杂度，在不同情况下表现有所不同：

正常情况下的时间复杂度为 O(N^2)，这适用于大多数无序的数据集。
对于已经有序或接近有序的数据，插入排序能够显著优化其性能。在这种理想状况下，该算法可以达到线性的 O(N) 的效率。

因此，插入排序的具体时间复杂度依赖于输入数据的状态。

插入排序能够在特定条件下接近线性时间复杂度O(n)，主要与待排序数据的状态有关。

对于已经完全有序的数据，每次插入操作只需要比较一次即可确定位置，不需要移动其他元素。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        if key >= arr[j]:
            continue
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# 如果数组已经是升序排列，则几乎不会进入while循环内部

当数据几乎是有序的情况下（即只有少量元素不在正确的位置上），大多数插入操作同样只需很少次比较和可能的交换。这些特性使得插入排序对近乎有序的小规模数据集表现优异。

折半插入排序通过采用二分查找来确定待插入元素的位置，从而减少比较次数，这是对普通插入排序的主要改进点。

普通插入排序在寻找新元素应处位置时从数组前端或后端开始逐个对比直到找到正确位置。而折半插入排序利用已排好序部分的特点应用二分搜索快速定位应该放置的新成员所在之处。
虽然这种改变不能改善最坏情况下 (O(n^2)) 的时间复杂度因为仍然存在大量数据移位操作；但是可以显著加快每次查询速度尤其当序列较大时效果更明显。

// C++示例展示如何使用二分法决定新项目加入地点而不是线性扫描整个列表
int BinarySearch(int arr[], int item, int low, int high)
{
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
  
        // Check if x is present at mid
        if (arr[mid] == item)
            return mid;

        // If x greater, ignore left half 
        if (arr[mid] < item)
            low = mid + 1;

        // If x is smaller, ignore right half 
        else
            high = mid - 1;
    }
    
    // Return insertion point
    return low;
}

两种排序算法的主要区别体现在工作原理及其应用场景上：

插入排序基于逐步构建有序序列的原则，在每一步迭代过程中，会将当前考察的元素插入到已排好序的部分合适位置上去。
直接选择排序则是每次从未排序部分挑选出最小（或最大）的一个元素放到已排序区域末端，以此方式逐渐扩展已排序区直至全部数据完成排列。

对于不同特性的数据集来说：

对于几乎已经是有序的数据集合，插入排序能发挥较好性能；
若面对规模相对较小并且不要求稳定性的任务时，则可以选择使用简单易懂的选择排序。

衡量算法好坏的标准包括多个方面：

正确性
算法应能够解决问题并且得到正确的结果。如果一个算法不能保证在所有情况下都能得出正确答案，则此算法难以被认为是好的。
最优性
从理论上讲，若一算法的时间复杂度已达到所求解问题的最低界限，则意味着不存在更快速完成任务的方法；即使存在其他方式其速度也不会优于当前方案。因此，在最糟糕状况下仍能保持性能稳定性的算法通常被视为最佳选择之一。
健壮性和可靠性
即便遇到非法输入或其他意外情形时也能妥善应对而不引发灾难性后果。虽然绝对意义上的"完全正确"难以企及，但对于实际应用来说更为重要的是确保软件能够在各种环境下稳健运作，并对可能出现的问题作出恰当反应。
简明易懂程度（可读性）
一个好的算法应该具备良好的结构性以及清晰表达的思想流程，便于他人阅读学习的同时也有助于后期维护修改工作。尽管有时为了追求效率可能会牺牲一定的简易直观性，但在可能范围内尽可能简化仍是值得提倡的做法。

在这里插入图片描述