当前位置：首页网站首页 > 正文

c++实现七种常见排序算法

作者：野牛程序员：2025-10-24 09:56:58网站首页阅读 2240
c++实现七种常见排序算法

🟢 一、冒泡排序（Bubble Sort）

#include <iostream>
using namespace std;

/*
【算法原理】
冒泡排序通过相邻元素的比较与交换，将较大的元素逐步“冒泡”到数组末尾。
每一轮都会将当前未排序部分中最大的元素放到正确位置。
*/
void bubbleSort(int arr[], int n) {
    bool swapped; // 标志变量，用于检测本轮是否发生交换
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        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;
                swapped = true;
            }
        }
        if (!swapped) // 若未发生交换说明已排序完成
            break;
    }
}

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

    cout << "排序前: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    bubbleSort(arr, n);

    cout << "排序后: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

🟡 二、选择排序（Selection Sort）

#include <iostream>
using namespace std;

/*
【算法原理】
选择排序每一轮从未排序部分中选择最小元素，放到已排序部分的末尾。
交换次数少，但整体效率与冒泡相近。
*/
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;
        }
    }
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    selectionSort(arr, n);

    cout << "排序后: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

🟠 三、插入排序（Insertion Sort）

#include <iostream>
using namespace std;

/*
【算法原理】
插入排序将数组分为已排序和未排序两部分。
每次从未排序部分取出一个元素，插入到前面合适的位置，使前半部分始终有序。
*/
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--;
        }
        arr[j + 1] = key;     // 插入到合适位置
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    insertionSort(arr, n);

    cout << "排序后: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

🔵 四、快速排序（Quick Sort）

#include <iostream>
using namespace std;

/*
【算法原理】
快速排序使用“分治”思想：
选择一个基准（pivot），将小于基准的放左侧，大于基准的放右侧，
然后递归地对左右部分继续排序。
*/
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 基准值
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {
            ++i;
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
        }
    }
    int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
    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);  // 排序右半部分
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    quickSort(arr, 0, n - 1);

    cout << "排序后: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

🔴 五、归并排序（Merge Sort）

#include <iostream>
using namespace std;

/*
【算法原理】
归并排序同样采用“分治”思想：
将数组不断二分成小段，分别排序后再合并成一个有序序列。
*/
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int *L = new int[n1];
    int *R = new int[n2];

    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }

    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];

    delete[] L;
    delete[] R;
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    mergeSort(arr, 0, n - 1);

    cout << "排序后: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

🟣 六、堆排序（Heap Sort）

#include <iostream>
using namespace std;

/*
【算法原理】
堆排序利用二叉堆结构，将数组视为完全二叉树。
通过构建最大堆，依次取出堆顶最大值放到数组末尾，完成排序。
*/
void heapify(int arr[], int n, int i) {
    int largest = i;        // 根节点
    int left = 2 * i + 1;   // 左子节点
    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) {
        int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
        heapify(arr, n, largest); // 递归调整
    }
}

void heapSort(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) {
        int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    heapSort(arr, n);

    cout << "排序后: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

⚫ 七、希尔排序（Shell Sort）

#include <iostream>
using namespace std;

/*
【算法原理】
希尔排序是插入排序的改进版：
通过“分组 + 插入排序”的方式，逐步缩小分组间隔，提高整体效率。
*/
void shellSort(int arr[], int n) {
    // 初始步长为 n/2，逐步减小到 1
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    shellSort(arr, n);

    cout << "排序后: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

✅ 总结对比表

算法名称思想类型稳定性平均时间复杂度最好最坏备注
冒泡排序比较交换✅ 稳定O(n²)O(n)O(n²)结构最简单
选择排序选择交换❌ 不稳定O(n²)O(n²)O(n²)交换少
插入排序插入法✅ 稳定O(n²)O(n)O(n²)小规模高效
快速排序分治法❌ 不稳定O(n log n)O(n log n)O(n²)实际最快
归并排序分治法✅ 稳定O(n log n)O(n log n)O(n log n)需要额外空间
堆排序选择法❌ 不稳定O(n log n)O(n log n)O(n log n)高效、无额外空间
希尔排序改进插入❌ 不稳定O(n^1.3)≈O(n log n)O(n²)简单高效的改进算法


野牛程序员教少儿编程与信息学奥赛-微信|电话：15892516892
野牛程序员教少儿编程与信息学竞赛-微信|电话：15892516892
  • c++实现七种常见排序算法
    • 相关推荐

    最新推荐

    热门点击