十大排序C++版本代码，带注释_c++代码大全及注解

冒泡排序（Bubble Sort）

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {  // 外层循环控制排序轮数
        bool flag = false;  // 标志变量，用于优化排序
        for (int j = 0; j < n - i - 1; ++j) {  // 内层循环控制每轮比较次数
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                flag = true;
            }
        }
        if (!flag) {  // 如果本轮没有交换任何元素，则数组已有序
            break;
        }
    }
}

选择排序（Selection Sort）

void selection_sort(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;
            }
        }
        std::swap(arr[i], arr[min_idx]);  // 将最小值交换到数组最前面
    }
}

插入排序（Insertion Sort）

void insertion_sort(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) {  // 内层循环寻找插入位置
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = temp;  // 将待插入元素插入到正确的位置
    }
}

希尔排序（Shell Sort）

void shell_sort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {  // 增量序列的选择方法是希尔排序的关键
        for (int i = gap; i < n; ++i) {  // 对每个子序列进行插入排序
            int temp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > temp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = temp;
        }
    }
}

归并排序（Merge Sort）

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1],
		int R[n2];
    for (int i = 0; i < n1; ++i) {
        L[i] = arr[left + i];
    }
    for (int i = 0; i < n2; ++i) {
        R[i] = arr[mid + 1 + i];
    }
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {  // 归并两个有序子序列
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            ++i;
        } else {
            arr[k] = R[j];
            ++j;
        }
        ++k;
    }
    while (i < n1) {  // 将剩余的元素插入到数组
        arr[k] = L[i];
        ++i;
        ++k;
    }
    while (j < n2) {
        arr[k] = R[j];
        ++j;
        ++k;
    }
}
 
void merge_sort(int arr[], int left, int right) {
    if (left < right) {  // 递归结束条件
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);  // 对左半边进行归并排序
        merge_sort(arr, mid + 1, right);  // 对右半边进行归并排序
        merge(arr, left, mid, right);  // 合并两个有序子序列
    }
}

快速排序（Quick Sort）

int partition(int arr[], int left, int right) {
    int pivot = arr[right];  // 选取基准元素
    int i = left - 1;  // i 指向小于等于基准元素的区域的右边界
    for (int j = left; j < right; ++j) {  // 遍历区域
        if (arr[j] <= pivot) {  // 小于等于基准元素的元素放到区域左侧
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[right]);  // 将基准元素放到区域中间
    return i + 1;  // 返回基准元素的下标
}
 
void quick_sort(int arr[], int left, int right) {
    if (left < right) {  // 递归结束条件
        int pivot_idx = partition(arr, left, right);  // 分区并返回基准元素的下标
        quick_sort(arr, left, pivot_idx - 1);  // 对左半边进行快速排序
        quick_sort(arr, pivot_idx + 1, right);  // 对右半边进行快速排序
    }
}

堆排序（Heap Sort）

void heapify(int arr[], int n, int i) {
    int largest = i;  // 假设最大值在根节点
    int left = 2 * i
		int right = 2 * i + 2;
    // 如果左子节点比根节点大，更新最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    // 如果右子节点比根节点大，更新最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {  // 如果最大值不在根节点
        std::swap(arr[i], arr[largest]);  // 将最大值交换到根节点
        heapify(arr, n, largest);  // 递归地维护堆
    }
}
 
void heap_sort(int arr[], int n) {
    // 建立初始堆，从最后一个非叶子节点开始
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapify(arr, n, i);
    }
    // 依次取出堆顶元素并维护堆
    for (int i = n - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);  // 将堆顶元素交换到数组末尾
        heapify(arr, i, 0);  // 维护堆
    }
}

计数排序（Counting Sort）

void counting_sort(int arr[], int n) {
    int max_val = *std::max_element(arr, arr + n);  // 找到最大值
    int count[max_val + 1] = {};  // 初始化计数数组
    for (int i = 0; i < n; ++i) {  // 统计每个元素的出现次数
        ++count[arr[i]];
    }
    for (int i = 1; i <= max_val; ++i) {  // 对计数数组进行前缀和处理
        count[i] += count[i - 1];
    }
    int output[n];  // 临时数组
    for (int i = n - 1; i >= 0; --i) {  // 从后往前遍历原始数组
        output[count[arr[i]] - 1] = arr[i];  // 将元素放到正确的位置上
        --count[arr[i]];  // 减少计数
    }
    std::copy(output, output + n, arr);  // 将临时数组复制回原始数组
}

桶排序（Bucket Sort）

void bucket_sort(float arr[], int n) {
    std::vector<float> buckets[n];  // 创建 n 个空桶
    for (int i = 0; i < n; ++i) {  // 将元素放入对应的桶中
        int idx = n * arr[i];
        buckets[idx].push_back(arr[i]);
    }
    for (int i = 0; i < n; ++i) {  // 对每个桶内部进行排序
        std::sort(buckets[i]..begin(), buckets[i].end());
		}
		int idx = 0;
		for (int i = 0; i < n; ++i) {  // 将所有桶中的元素依次合并
		    for (float num : buckets[i]) {
		        arr[idx++] = num;
				 }
		}
}

基数排序

void radix_sort(int arr[], int n) {
    int max_val = *std::max_element(arr, arr + n);  // 找到最大值
    int exp = 1;  // 当前位数
    std::vector<int> output(n);  // 临时数组
    while (max_val / exp > 0) {  // 从低位到高位依次处理每一位
        std::vector<int> count(10);  // 初始化计数数组
        for (int i = 0; i < n; ++i) {  // 统计当前位数的出现次数
            ++count[(arr[i] / exp) % 10];
        }
        for (int i = 1; i < 10; ++i) {  // 对计数数组进行前缀和处理
            count[i] += count[i - 1];
        }
        for (int i = n - 1; i >= 0; --i) {  // 从后往前遍历原始数组
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];  // 将元素放到正确的位置上
            --count[(arr[i] / exp) % 10];  // 减少计数
        }
        std::copy(output.begin(), output.begin() + n, arr);  // 将临时数组复制回原始数组
        exp *= 10;  // 处理下一位
    }
}