18.内部排序算法比较

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

#define SIZE 1005

// 生成伪随机数的函数
void generateRandomArray(int array[], int size) {
    srand(time(NULL));
    for (int i = 0; i < size; i++) {
        array[i] = rand() % 10000; // 生成介于 0 和 9999 之间的随机数
    }
}

// 交换函数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 冒泡排序
void bubbleSort(int array[], int size, int* compCount, int* moveCount) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            (*compCount)++;
            if (array[j] > array[j + 1]) {
                (*moveCount) += 3; // 交换需要三步
                swap(&array[j], &array[j + 1]);
            }
        }
    }
}

// 插入排序
void insertionSort(int array[], int size, int* compCount, int* moveCount) {
    for (int i = 1; i < size; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            (*compCount)++;
            array[j + 1] = array[j];
            (*moveCount)++;
            j--;
        }
        array[j + 1] = key;
        (*moveCount)++;
    }
}

// 选择排序
void selectionSort(int array[], int size, int* compCount, int* moveCount) {
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < size; j++) {
            (*compCount)++;
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            (*moveCount) += 3; // 交换需要三步
            swap(&array[i], &array[minIndex]);
        }
    }
}

// 快速排序
void quickSort(int array[], int low, int high, int* compCount, int* moveCount) {
    if (low < high) {
        int pivot = array[high];
        int i = low - 1;
        for (int j = low; j <= high - 1; j++) {
            (*compCount)++;
            if (array[j] < pivot) {
                i++;
                (*moveCount) += 3; // 交换需要三步
                swap(&array[i], &array[j]);
            }
        }
        (*moveCount) += 3; // 交换需要三步
        swap(&array[i + 1], &array[high]);
        int partitionIndex = i + 1;

        quickSort(array, low, partitionIndex - 1, compCount, moveCount);
        quickSort(array, partitionIndex + 1, high, compCount, moveCount);
    }
}

// 希尔排序
void shellSort(int array[], int size, int* compCount, int* moveCount) {
    for (int gap = size / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < size; i++) {
            int temp = array[i];
            int j;
            for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                (*compCount)++;
                array[j] = array[j - gap];
                (*moveCount)++;
            }
            array[j] = temp;
            (*moveCount)++;
        }
    }
}

// 堆植于索引 i 的子树
void heapify(int array[], int size, int i, int* compCount, int* moveCount) {
    int largest = i; // 以 root 身份初始化 largest
    int left = 2 * i + 1; // 左孩子
    int right = 2 * i + 2; // 右孩子

    // 如果左孩子大于根
    if (left < size && array[left] > array[largest]) {
        largest = left;
    }
    (*compCount)++;

    // 如果右孩子大于目前最大的孩子largest
    if (right < size && array[right] > array[largest]) {
        largest = right;
    }
    (*compCount)++;

    // 如果最大的不是根
    if (largest != i) {
        (*moveCount) += 3; // 交换需要三步
        swap(&array[i], &array[largest]);

        // 以递归方式堆受影响的子树
        heapify(array, size, largest, compCount, moveCount);
    }
}

// 堆排序
void heapSort(int array[], int size, int* compCount, int* moveCount) {
    // 构建堆（重新排列数组）
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(array, size, i, compCount, moveCount);
    }

    // 一个接一个地从堆中提取元素
    for (int i = size - 1; i >= 0; i--) {
        (*moveCount) += 3; // 交换需要三步
        swap(&array[0], &array[i]);

        // 在减少的堆上调用 最大堆
        heapify(array, i, 0, compCount, moveCount);
    }
}

int main() {
    int array[SIZE];

    for (int i = 0; i < 5; i++) {
        generateRandomArray(array, SIZE);

        int compCount = 0;
        int moveCount = 0;

        printf("输入数组 %d:\n", i + 1);

        // 冒泡排序
        int bubbleArray[SIZE];
        for (int j = 0; j < SIZE; j++) {
            bubbleArray[j] = array[j];
        }
        bubbleSort(bubbleArray, SIZE, &compCount, &moveCount);
        printf("冒泡排序 - 比较: %d, 移动: %d\n", compCount, moveCount);

        // 插入排序
        int insertionArray[SIZE];
        for (int j = 0; j < SIZE; j++) {
            insertionArray[j] = array[j];
        }
        compCount = 0;
        moveCount = 0;
        insertionSort(insertionArray, SIZE, &compCount, &moveCount);
        printf("插入排序 - 比较: %d, 移动: %d\n", compCount, moveCount);

        // 选择排序
        int selectionArray[SIZE];
        for (int j = 0; j < SIZE; j++) {
            selectionArray[j] = array[j];
        }
        compCount = 0;
        moveCount = 0;
        selectionSort(selectionArray, SIZE, &compCount, &moveCount);
        printf("选择排序 - 比较: %d, 移动: %d\n", compCount, moveCount);

        // 快速排序
        int quickArray[SIZE];
        for (int j = 0; j < SIZE; j++) {
            quickArray[j] = array[j];
        }
        compCount = 0;
        moveCount = 0;
        quickSort(quickArray, 0, SIZE - 1, &compCount, &moveCount);
        printf("快速排序 - 比较: %d, 移动: %d\n", compCount, moveCount);

        // 希尔排序
        int shellArray[SIZE];
        for (int j = 0; j < SIZE; j++) {
            shellArray[j] = array[j];
        }
        compCount = 0;
        moveCount = 0;
        shellSort(shellArray, SIZE, &compCount, &moveCount);
        printf("希尔排序 - 比较: %d, 移动: %d\n", compCount, moveCount);

        // 堆排序
        int heapArray[SIZE];
        for (int j = 0; j < SIZE; j++) {
            heapArray[j] = array[j];
        }
        compCount = 0;
        moveCount = 0;
        heapSort(heapArray, SIZE, &compCount, &moveCount);
        printf("堆排序 - 比较: %d, 移动: %d\n", compCount, moveCount);

        printf("\n");
    }

    return 0;
}