5.1 排序¶

5.1.1 选择排序¶

当我们谈论选择排序（Selection Sort）时，这是一种简单的排序算法。它的基本思想是在未排序的部分中选择最小（或最大）的元素，然后将其与未排序部分的第一个元素交换。这个过程不断重复，直到整个数组排序完成。

下面是一个使用C语言实现选择排序的简单例子：

C
#include <stdio.h>

// 选择排序函数
void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;

    for (i = 0; i < n - 1; i++) {
        // 假设当前位置的元素是最小的
        minIndex = i;

        // 在未排序的部分中找到最小的元素的索引
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // 将最小的元素与当前位置的元素交换
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: \n");
    printArray(arr, n);

    // 应用选择排序
    selectionSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

在这个例子中，selectionSort 函数实现了选择排序算法，而 printArray 函数用于打印数组元素。在 main 函数中，我们定义了一个数组，对其进行选择排序，并输出排序后的结果。

请注意，选择排序的时间复杂度为O(n^2)，因此对于大型数据集可能不是最优选择。

5.1.2 冒泡排序¶

冒泡排序（Bubble Sort）是另一种简单的排序算法。它的基本思想是通过多次遍历数组，比较相邻的两个元素，如果它们的顺序不正确就交换它们，直到整个数组排序完成。

以下是使用C语言实现冒泡排序的简单例子：

C
#include <stdio.h>

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            // 如果相邻元素的顺序不正确，交换它们
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: \n");
    printArray(arr, n);

    // 应用冒泡排序
    bubbleSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

在这个例子中，bubbleSort 函数实现了冒泡排序算法，而 printArray 函数用于打印数组元素。在 main 函数中，我们定义了一个数组，对其进行冒泡排序，并输出排序后的结果。

冒泡排序的时间复杂度也为O(n^2)，因此对于大型数据集同样不是最优选择。然而，由于其简单性，冒泡排序在某些特定情况下可能是有用的。

5.1.3 希尔排序¶

希尔排序（Shell Sort）是插入排序的一种改进版本，也称为缩小增量排序。它通过将整个数组分割成若干个子序列，然后对每个子序列分别进行插入排序，最终合并这些子序列。

以下是使用C语言实现希尔排序的简单例子：

C
#include <stdio.h>

// 希尔排序函数
void shellSort(int arr[], int n) {
    int i, j, temp;
    // 选择增量序列，这里使用希尔建议的序列
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            temp = arr[i];
            // 对子序列进行插入排序
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: \n");
    printArray(arr, n);

    // 应用希尔排序
    shellSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

在这个例子中，shellSort 函数实现了希尔排序算法，而 printArray 函数用于打印数组元素。在 main 函数中，我们定义了一个数组，对其进行希尔排序，并输出排序后的结果。

希尔排序的时间复杂度取决于所选择的增量序列，但通常它在平均情况下的性能要优于插入排序和冒泡排序。希尔排序是一种不稳定的排序算法。

5.1.4 快速排序¶

快速排序（Quick Sort）是一种分治算法，它通过选择一个基准元素将数组分成两个子数组，然后递归地对子数组进行排序。快速排序的基本思想是在数组中选择一个元素作为基准，将小于基准的元素移动到基准的左边，将大于基准的元素移动到基准的右边，然后对左右两个子数组重复这个过程。

以下是使用C语言实现快速排序的简单例子：

C
#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++;
            // 交换arr[i]和arr[j]
            swap(&arr[i], &arr[j]);
        }
    }
    // 交换arr[i+1]和arr[high]，将基准元素放在正确的位置
    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) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: \n");
    printArray(arr, n);

    // 应用快速排序
    quickSort(arr, 0, n - 1);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

在这个例子中，quickSort 函数实现了快速排序算法，而 partition 函数用于在数组中选择基准元素并将数组分区。在 main 函数中，我们定义了一个数组，对其进行快速排序，并输出排序后的结果。

快速排序的平均时间复杂度为O(n log n)，它是一种高效的排序算法。

5.2 二维数组¶

在初始化二维数组时可省略第一维大小，但是不能省略第二维大小。

5.3 字符数组¶

char str[6] = {"Hello"} ;

字符串两端的大括号可以省略。

![[Pasted image 20231229193611.png]] 本质：数组等于数组

C
char a[10];
scanf("%c",&a[i]);
scanf("%s",a);

scanf遇到制表符、空格、换行符、EOF停止读入。 gets和puts遇到换行符、EOF停止。

本章总结¶

C
char sp[] = "\t\b\0123\n"
printf("%d",strlen(sp));

答案是5。 \t \b \012 3 \n