用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;
}