C/C++ 基础排序算法汇总

C/C++ 基础排序算法汇总

C 语言排序算法实现

冒泡排序

冒泡排序依次对相邻两个元素的值进行比较，若发现前一个数大于后一个数则交换，使得较大的元素一步一步移动到数组的末尾。

void sort(int arr[], int n) {
    // 外层循环：控制排序轮数，共需要 n-1 轮
    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;
            }
        }
    }
}

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

选择排序

选择排序每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}