【C语言】常见的几种排序方式_c语言排序

C语言中常见的排序方式有：冒泡排序、选择排序、插入排序、快速排序、归并排序等。

1.冒泡排序

冒泡排序的核心思想是依次比较相邻的两个元素，如果它们的顺序不对就交换它们，直到没有元素需要交换为止。冒泡排序每次会把当前未排序部分的最大值交换到最后。

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {   // 外层循环控制轮数
        for (int j = 0; j < n - 1 - i; j++) {   // 内层循环控制比较次数
            if (arr[j] > arr[j + 1]) {   // 如果前一个元素比后一个元素大，则交换它们的位置
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13

2.选择排序

选择排序的核心思想是依次选择当前未排序部分的最小元素，放到已排序部分的末尾。在未排序部分中找到最小元素的操作可以通过直接遍历数组和记录最小值的方式实现。

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {   // 外层循环控制轮数
        int minIndex = i;   // 记录最小元素的下标
        for (int j = i + 1; j < n; j++) {   // 内层循环在未排序部分中找到最小元素
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {   // 如果最小元素不在已排序部分的末尾，则交换它们的位置
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.插入排序

插入排序的核心思想是把当前未排序部分的元素插入到已排序部分的合适位置。对于每个待插入的元素，从已排序部分的末尾往前找到第一个比它小的元素，然后把它插入到该元素后面。

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {   // 外层循环从第二个元素开始，依次将它插入到已排序部分的合适位置
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {   // 内层循环找到temp应该插入的位置
            arr[j + 1] = arr[j];   // 将大于temp的元素后移一位
            j--;
        }
        arr[j + 1] = temp;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13

4.快速排序

快速排序的核心思想是通过分治的思想将一个大问题分解成小问题来解决。它的具体实现是选定一个基准值，然后将小于等于基准值的元素放到左边，大于基准值的元素放到右边。然后对左右两个部分分别递归地进行快速排序。

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;   // 边界条件
    int i = left, j = right, pivot = arr[left];   // 将最左边的元素选为基准值
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;   // 从右往左找到第一个小于基准值的元素
        if (i < j) arr[i++] = arr[j];
        while (i < j && arr[i] < pivot) i++;   // 从左往右找到第一个大于等于基准值的元素
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);   // 递归地对左右两部分进行排序
    quickSort(arr, i + 1, right);
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.归并排序

归并排序的核心思想也是分治。将一个数组分为左右两个部分，先递归地对左右两部分分别进行排序，然后将排序好的两部分合并起来。在合并的过程中，记录左右两部分数组的起始位置和当前比较位置，将它们比较大小后放到一个辅助数组中，最后再将辅助数组复制回原数组中。归并排序需要辅助数组的支持。

void merge(int arr[], int left, int mid, int right) {
    int *temp = new int[right - left + 1];   // 定义一个辅助数组
    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 (i = 0; i < k; i++) {   // 将辅助数组中的元素复制回原数组
        arr[left + i] = temp[i];
    }
    delete[] temp;
}

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;   // 边界条件
    int mid = (left + right) / 2;   // 将数组分为左右两部分
    mergeSort(arr, left, mid);   // 递归地对左右两部分进行排序
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);   // 将已经排好序的左右两部分合并起来
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27