C语言编程题使用指针和函数排序数组

1、冒泡排序

冒泡排序是一种简单的排序算法，通过不断交换相邻的元素，将较大的元素逐步移动到右侧。

#include <stdio.h>

void bubbleSort(int *arr, int n) { 
    for (int i = 0; i < n-1; i++) { 
        for (int j = 0; j < n-i-1; j++) { 
            if (*(arr+j) > *(arr+j+1)) { 
                int temp = *(arr+j); 
                *(arr+j) = *(arr+j+1); 
                *(arr+j+1) = temp; 
            } 
        } 
    } 
} 
 
int main() { 
    int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    bubbleSort(arr, n); 
    printf("Sorted array: \n"); 
    for (int i=0; i < n; i++) 
        printf("%d ", arr[i]); 
    return 0;
} 

2、选择排序

选择排序每次选择未排序部分的最小元素，并将其放到已排序部分的末尾。

#include <stdio.h>

void selectionSort(int *arr, int n) { 
    for (int i = 0; i < n-1; i++) { 
        int min_idx = i; 
        for (int j = i+1; j < n; j++) 
            if (*(arr+j) < *(arr+min_idx)) 
                min_idx = j; 
        int temp = *(arr+min_idx); 
        *(arr+min_idx) = *(arr+i); 
        *(arr+i) = temp; 
    } 
} 
 
int main() { 
    int arr[] = {64, 25, 12, 22, 11}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    selectionSort(arr, n); 
    printf("Sorted array: \n"); 
    for (int i=0; i < n; i++) 
        printf("%d ", arr[i]); 
    return 0; 
}

3、插入排序

插入排序逐步构建最终的排序序列，对未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

#include <stdio.h>

void insertionSort(int *arr, int n) { 
    for (int i = 1; i < n; i++) { 
        int key = *(arr+i); 
        int j = i - 1; 
        while (j >= 0 && *(arr+j) > key) { 
            *(arr+j+1) = *(arr+j); 
            j = j - 1; 
        } 
        *(arr+j+1) = key; 
    } 
} 
 
int main() { 
    int arr[] = {12, 11, 13, 5, 6}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    insertionSort(arr, n); 
    printf("Sorted array: \n"); 
    for (int i=0; i < n; i++) 
        printf("%d ", arr[i]); 
    return 0; 
} 

4、快速排序

快速排序通过选择一个基准值，将数组分为两部分，分别对左右两部分递归进行排序。

#include <stdio.h>
 
// 交换两个整数的值 
void swap(int* a, int* b) { 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 
 
// 分区函数 
int partition(int arr[], int low, int high) { 
    int pivot = arr[high]; // 选择最后一个元素作为轴值 
    int i = (low - 1); // 较小元素的索引 
 
    for (int j = low; j <= high - 1; j++) { 
        if (arr[j] < pivot) { 
            i++; 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
 
// 快速排序函数 
void quickSort(int arr[], int low, int high) { 
    if (low < high) { 
        int pi = partition(arr, low, high); 
 
        quickSort(arr, low, pi - 1); // 对左半部分排序 
        quickSort(arr, pi + 1, high); // 对右半部分排序 
    } 
} 
 
// 打印数组 
void printArray(int arr[], int size) { 
    for (int i = 0; i < size; i++) { 
        printf("%d ", arr[i]); 
    } 
    printf("\n"); 
} 
 
int main() { 
    int arr[] = {10, 7, 8, 9, 1, 5}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    quickSort(arr, 0, n - 1); 
    printf("Sorted array: \n"); 
    printArray(arr, n); 
    return 0; 
} 

5、归并排序

归并排序是一种分治算法，将数组分成两个子数组，分别排序，然后合并已排序的子数组。

#include <stdio.h> 
#include <stdlib.h> // for malloc and free 
 
// 合并两个已排序的子数组 
void merge(int arr[], int l, int m, int r) { 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 = r - m; 
 
    // 创建临时数组 
    int *L = (int *)malloc(n1 * sizeof(int)); 
    int *R = (int *)malloc(n2 * sizeof(int)); 
 
    // 复制数据到临时数组 L[] 和 R[] 
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1 + j]; 
 
    // 合并临时数组到 arr[l..r] 
    i = 0; // 初始化第一个子数组的索引 
    j = 0; // 初始化第二个子数组的索引 
    k = l; // 初始化合并子数组的索引 
    while (i < n1 && j < n2) { 
        if (L[i] <= R[j]) { 
            arr[k] = L[i]; 
            i++; 
        } else { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
 
    // 复制 L[] 的剩余元素 
    while (i < n1) { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
 
    // 复制 R[] 的剩余元素 
    while (j < n2) { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
 
    // 释放临时数组 
    free(L); 
    free(R); 
} 
 
// 递归的归并排序函数 
void mergeSort(int arr[], int l, int r) { 
    if (l < r) { 
        int m = l + (r - l) / 2; 
 
        // 递归排序左半部分和右半部分 
        mergeSort(arr, l, m); 
        mergeSort(arr, m + 1, r); 
 
        // 合并已排序的两部分 
        merge(arr, l, m, r); 
    } 
} 
 
// 测试代码 
int main() { 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int arr_size = sizeof(arr) / sizeof(arr[0]); 
 
    printf("Given array is \n"); 
    for (int i = 0; i < arr_size; i++) 
        printf("%d ", arr[i]); 
    printf("\n"); 
 
    mergeSort(arr, 0, arr_size - 1); 
 
    printf("\nSorted array is \n"); 
    for (int i = 0; i < arr_size; i++) 
        printf("%d ", arr[i]); 
    printf("\n"); 
    return 0; 
}