快速排序的空间复杂度度

快速排序的空间复杂度取决于实现方式。就地快速排序使用的空间是O(1)的，也就是常数级别的空间。但是，递归调用会消耗一些空间，因为每次递归都需要保持一些数据。在最优情况下，每次都平分数组的情况下，快速排序的空间复杂度为O(logn)。而在最坏情况下，即退化为冒泡排序的情况下，快速排序的空间复杂度为O(n)。

相关问题

快速排序时间复杂度空间复杂度

### 快速排序的时间复杂度

对于快速排序而言，在理想状况下，每次分割操作都能将待排序序列几乎均等地分成两部分。此时，递归树的高度为 \( \log_2{n} \)，每一层涉及的比较次数大致相加等于 n ，所以总的比较次数大约是 \( n\log_2{n} \)[^1]。

然而，在最糟糕的情况下——比如当输入数组已经有序或逆序排列时，如果总是选取第一个或最后一个元素作为基准，则可能导致极不平衡的分区结果，使得一边为空而另一边包含除了基准外的所有其他元素。这种情形下，递归调用会形成一条长长的链表结构，从而导致时间复杂度退化到 O(n²) [^3]。

尽管如此，通过优化策略如三数取中法来挑选枢轴可以有效减少遇到最差情况的概率，使实际性能更贴近理论上的最优表现即 O(n log n) 的平均时间复杂度[^2]。

### 快速排序的空间复杂度

关于空间开销方面，主要是由递归过程中产生的临时存储需求决定。由于每一轮迭代都需要保存当前处理区间的边界指针以及用于交换数据项的工作单元，再加上函数调用本身所需的信息（返回地址等），这些都会占用一定的内存资源。不过只要不是极端不均衡的情况，随着递归层数的增长，额外消耗的空间量级通常不会超过 \( O(\log_2{n}) \)。

但是需要注意的是，在最坏的情形里，正如前面提到过的那样，可能会因为连续单边增长而导致栈帧累积至线性级别，进而造成高达 O(n) 的辅助空间使用率。

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)

        # Recursively sort elements before and after partition index
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)


def partition(array, start, end):
    pivot_index = choose_pivot(start, end)  # Choose a good pivot strategy to avoid worst case
    array[start], array[pivot_index] = array[pivot_index], array[start]

    pivot = array[start]
    i = j = start + 1
    
    while j <= end:
        if array[j] <= pivot:
            array[i], array[j] = array[j], array[i]
            i += 1
        
        j += 1
    
    array[start], array[i - 1] = array[i - 1], array[start]
    
    return i - 1


def choose_pivot(low, high): ...

c编程实现冒泡排序、选择排序、快速排序，列出排序过程中每一趟排序结果，并列出三种算法的时间复 杂度和空间复杂度。

好的,我来为您介绍C语言中三种常见的排序算法:冒泡排序、选择排序和快速排序。我会给出每种算法的实现代码,列出每一趟的排序结果,并分析它们的时间复杂度和空间复杂度。

1. 冒泡排序

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换 arr[j] 和 arr[j+1]
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        // 打印每一趟排序结果
        printf("第 %d 趟排序结果: ", i+1);
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("排序后的数组: ");
    for (int i=0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1)。

2. 选择排序

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        // 交换 arr[i] 和 arr[min_idx]
        temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
        // 打印每一趟排序结果
        printf("第 %d 趟排序结果: ", i+1);
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("排序后的数组: ");
    for (int i=0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

选择排序的时间复杂度为O(n^2),空间复杂度为O(1)。

3. 快速排序

#include <stdio.h>

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi 是分区点, arr[pi] 是正确的位置
        int pi = partition(arr, low, high);
        // 递归排序分区点左侧的元素
        quickSort(arr, low, pi - 1);
        // 递归排序分区点右侧的元素
        quickSort(arr, pi + 1, high);
        // 打印每一趟排序结果
        printf("排序结果: ");
        for (int i = 0; i <= high; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
}

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 小元素的索引
    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于 pivot
        if (arr[j] <= pivot) {
            i++; // 增加小元素索引
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 交换 arr[i + 1] 和 arr[high] (pivot)
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("排序后的数组: ");
    for (int i=0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

快速排序的平均时间复杂度为O(nlogn),最坏情况下为O(n^2)。空间复杂度为O(logn)。

总结:
- 冒泡排序和选择排序的时间复杂度都是O(n^2),适用于小规模数据。
- 快速排序的平均时间复杂度为O(nlogn),适用于大规模数据,但在最坏情况下可能退化为O(n^2)。
- 空间复杂度方面,冒泡排序和选择排序都是O(1),快速排序为O(logn)。