分别说明简单选择排序、直接插入排序、冒泡排序、快速排序、两路合并排序、堆排序的时间复杂度

1. 简单选择排序的时间复杂度是O(n^2)。它的基本思想是每次从待排序的元素中选择最小（或最大）的元素放到已排序序列的末尾，直到全部元素排序完成。

2. 直接插入排序的时间复杂度是O(n^2)。它的基本思想是将待排序的元素逐个插入到已排序序列中的合适位置，直到全部元素排序完成。

3. 冒泡排序的时间复杂度是O(n^2)。它的基本思想是通过相邻元素之间的比较和交换，将较大的元素逐渐向右移动到正确的位置，直到全部元素排序完成。

4. 快速排序的时间复杂度平均情况下是O(nlogn)，最坏情况下是O(n^2)。它的基本思想是通过一趟排序将待排序序列分割成独立的两部分，其中一部分的所有元素都比另一部分小，然后对这两部分分别进行快速排序。

5. 两路合并排序（归并排序）的时间复杂度是O(nlogn)。它的基本思想是将待排序序列不断地二分，直到每个子序列只有一个元素，然后将相邻的子序列进行合并，直到全部元素排序完成。

6. 堆排序的时间复杂度是O(nlogn)。它的基本思想是将待排序序列构建成一个大顶堆（或小顶堆），然后依次将堆顶元素与最后一个元素交换，并重新调整堆，直到全部元素排序完成。

相关问题

c++ 数据结构，直接插入排序、冒泡排序、快速排序、简单选择排序

好的，我来为您介绍一下这些经典的排序算法：

1. 直接插入排序

直接插入排序是将未排序的元素逐一插入到已排好的序列中，使之成为一个有序序列。具体操作是，将当前元素插入到前面已排好序的序列中的适当位置。时间复杂度为O(n^2)。

2. 冒泡排序

冒泡排序是通过相邻元素的比较和交换来进行排序的。具体操作是，从最左边开始，比较相邻的两个元素，如果左边的元素大于右边的元素，则交换这两个元素。一轮比较完后，最大的元素被交换到了最右边。时间复杂度为O(n^2)。

3. 快速排序

快速排序是一种分治算法，通过将一个序列分成两个子序列来进行排序。具体操作是，选取一个基准元素，将序列中小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边，然后对左右子序列分别递归进行快速排序。时间复杂度为O(nlogn)。

4. 简单选择排序

简单选择排序是通过比较和交换来进行排序的。具体操作是，从未排序的序列中选择最小的元素，将其放在已排好序的序列的最右边，然后继续从未排序的序列中选择最小的元素，直到所有元素都排好序。时间复杂度为O(n^2)。

以上是这几种经典的排序算法，每种算法都有其优缺点和适用场景，需要根据具体情况进行选择。

用c语言编写实现顺序表的简单排序、直接插入排序、冒泡排序 快速排序、两路合并排序以及堆排序

下面是C语言实现的顺序表简单排序、直接插入排序、冒泡排序、快速排序、两路合并排序以及堆排序的代码示例。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXSIZE 100  // 定义数组的最大长度

typedef struct {
    int data[MAXSIZE];  // 存储数据的数组
    int length;         // 数组的长度
} SqList;

/**
 * 交换两个元素的值
 */
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/**
 * 初始化顺序表，随机生成n个元素
 */
void initList(SqList *L, int n) {
    if (n > MAXSIZE) {
        printf("n is too large!\n");
        exit(EXIT_FAILURE);
    }
    srand(time(NULL));  // 用当前时间作为随机种子
    for (int i = 0; i < n; i++) {
        L->data[i] = rand() % 100;  // 随机生成0~99之间的整数
    }
    L->length = n;
}

/**
 * 输出顺序表元素
 */
void printList(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
}

/**
 * 简单排序
 */
void simpleSort(SqList *L) {
    for (int i = 0; i < L->length; i++) {
        for (int j = i + 1; j < L->length; j++) {
            if (L->data[i] > L->data[j]) {
                swap(&L->data[i], &L->data[j]);
            }
        }
    }
}

/**
 * 直接插入排序
 */
void insertSort(SqList *L) {
    int i, j, temp;
    for (i = 1; i < L->length; i++) {
        if (L->data[i] < L->data[i - 1]) {
            temp = L->data[i];
            for (j = i - 1; j >= 0 && L->data[j] > temp; j--) {
                L->data[j + 1] = L->data[j];
            }
            L->data[j + 1] = temp;
        }
    }
}

/**
 * 冒泡排序
 */
void bubbleSort(SqList *L) {
    for (int i = 0; i < L->length; i++) {
        for (int j = 0; j < L->length - i - 1; j++) {
            if (L->data[j] > L->data[j + 1]) {
                swap(&L->data[j], &L->data[j + 1]);
            }
        }
    }
}

/**
 * 快速排序
 */
int partition(SqList *L, int low, int high) {
    int pivot = L->data[low];
    while (low < high) {
        while (low < high && L->data[high] >= pivot) {
            high--;
        }
        L->data[low] = L->data[high];
        while (low < high && L->data[low] <= pivot) {
            low++;
        }
        L->data[high] = L->data[low];
    }
    L->data[low] = pivot;
    return low;
}

void quickSort(SqList *L, int low, int high) {
    if (low < high) {
        int pivotpos = partition(L, low, high);
        quickSort(L, low, pivotpos - 1);
        quickSort(L, pivotpos + 1, high);
    }
}

/**
 * 两路合并排序
 */
void merge(int *arr, int left, int mid, int right) {
    int len = right - left + 1;  // 待合并数组的长度
    int *temp = (int *)malloc(len * sizeof(int));  // 临时数组，用于存储合并后的结果
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int m = 0; m < len; m++) {
        arr[left + m] = temp[m];
    }
    free(temp);
}

void mergeSort(int *arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

/**
 * 堆排序
 */
void adjustHeap(int *arr, int i, int len) {  // 将以i为根的子树调整为大根堆
    int temp = arr[i];
    for (int j = 2 * i + 1; j < len; j = 2 * j + 1) {
        if (j + 1 < len && arr[j] < arr[j + 1]) {
            j++;
        }
        if (arr[j] > temp) {
            arr[i] = arr[j];
            i = j;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

void heapSort(int *arr, int len) {
    // 构建大根堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    // 交换堆顶元素和末尾元素，并重新调整堆
    for (int i = len - 1; i >= 1; i--) {
        swap(&arr[0], &arr[i]);
        adjustHeap(arr, 0, i);
    }
}

int main() {
    SqList L;
    initList(&L, 10);
    printf("原始数据：");
    printList(L);

    simpleSort(&L);
    printf("简单排序后：");
    printList(L);

    initList(&L, 10);
    printf("原始数据：");
    printList(L);

    insertSort(&L);
    printf("直接插入排序后：");
    printList(L);

    initList(&L, 10);
    printf("原始数据：");
    printList(L);

    bubbleSort(&L);
    printf("冒泡排序后：");
    printList(L);

    initList(&L, 10);
    printf("原始数据：");
    printList(L);

    quickSort(&L, 0, L.length - 1);
    printf("快速排序后：");
    printList(L);

    int arr[10] = {4, 3, 6, 9, 1, 2, 8, 7, 5, 0};
    printf("原始数据：");
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    mergeSort(arr, 0, 9);
    printf("两路合并排序后：");
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    int arr1[10] = {4, 3, 6, 9, 1, 2, 8, 7, 5, 0};
    printf("原始数据：");
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr1[i]);
    }
    printf("\n");

    heapSort(arr1, 10);
    printf("堆排序后：");
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr1[i]);
    }
    printf("\n");

    return 0;
}