C语言编程题冒泡排序

1、基本的冒泡排序

#include <stdio.h>

// 函数声明
void bubbleSort(int arr[], int n);
void swap(int *xp, int *yp);
void printArray(int arr[], int size);

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("排序前的数组: \n");
    printArray(arr, n);
    bubbleSort(arr, n);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

// 基本的冒泡排序函数
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
            }
        }
    }
}

// 交换两个数的函数
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// 打印数组的函数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

2、优化的冒泡排序

在每次外循环中，如果没有发生交换，说明数组已经排序完成，可以提前退出。

#include <stdio.h>

// 函数声明
void optimizedBubbleSort(int arr[], int n);
void swap(int *xp, int *yp);
void printArray(int arr[], int size);

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("排序前的数组: \n");
    printArray(arr, n);
    optimizedBubbleSort(arr, n);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

// 优化的冒泡排序函数
void optimizedBubbleSort(int arr[], int n) {
    int i, j;
    int swapped;
    for (i = 0; i < n-1; i++) {
        swapped = 0;
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
                swapped = 1;
            }
        }
        // 如果没有发生交换，则退出
        if (swapped == 0)
            break;
    }
}

// 交换两个数的函数
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// 打印数组的函数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

3、双向冒泡排序（鸡尾酒排序）

#include <stdio.h>

// 函数声明
void cocktailSort(int arr[], int n);
void swap(int *xp, int *yp);
void printArray(int arr[], int size);

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("排序前的数组: \n");
    printArray(arr, n);
    cocktailSort(arr, n);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

// 鸡尾酒排序函数
void cocktailSort(int arr[], int n) {
    int start = 0;
    int end = n - 1;
    int swapped = 1;

    while (swapped) {
        swapped = 0;

        // 从左向右排序
        for (int i = start; i < end; i++) {
            if (arr[i] > arr[i+1]) {
                swap(&arr[i], &arr[i+1]);
                swapped = 1;
            }
        }

        // 如果没有发生交换，则数组已经排序完成
        if (!swapped)
            break;

        swapped = 0;
        end--;

        // 从右向左排序
        for (int i = end - 1; i >= start; i--) {
            if (arr[i] > arr[i+1]) {
                swap(&arr[i], &arr[i+1]);
                swapped = 1;
            }
        }

        start++;
    }
}

// 交换两个数的函数
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// 打印数组的函数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

4、带有计数器的冒泡排序

记录总共进行了多少次交换和比较，以分析算法性能。

#include <stdio.h>

// 函数声明
void bubbleSortWithCounters(int arr[], int n);
void swap(int *xp, int *yp);
void printArray(int arr[], int size);

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("排序前的数组: \n");
    printArray(arr, n);
    bubbleSortWithCounters(arr, n);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

// 带有计数器的冒泡排序函数
void bubbleSortWithCounters(int arr[], int n) {
    int i, j;
    int swapCount = 0, compareCount = 0;

    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            compareCount++;
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
                swapCount++;
            }
        }
    }

    printf("总共比较次数: %d\n", compareCount);
    printf("总共交换次数: %d\n", swapCount);
}

// 交换两个数的函数
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// 打印数组的函数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}