掌握C++中的常用排序算法- 技术经验 -卓越飞翔博客

掌握C++中的常用排序算法

C++ 是一门广泛应用于计算机程序设计中的编程语言，而排序算法则是程序设计中常用的算法之一。掌握排序算法，能够提高编写高效程序的能力，提升编程技能。本文将介绍 C++ 中的常用排序算法。

冒泡排序

冒泡排序是一种基础的排序算法，它通过依次比较相邻的元素，将较大的元素交换到序列的末尾，从而实现排序。具体来说，冒泡排序每一轮比较相邻元素的大小，并将较大的元素向后交换，直到最后一个元素排好序为止。

C++ 代码如下：

void bubbleSort(int arr[], int n)
{
    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;
            }
        }
    }
}

选择排序

选择排序是一种简单的排序算法，它每次选出未排序部分中最小的元素，并将其放到已排序部分的末尾，从而实现排序。具体来说，选择排序每一轮选出最小的元素，并与当前位置的元素交换。

C++代码如下：

void selectionSort(int arr[], int n)
{
    int minIndex, temp;
    for (int i = 0; i < n - 1; i++) {
        minIndex = i; // 记录最小元素的位置
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                // 更新最小元素的位置
                minIndex = j;
            }
        }
        // 交换元素
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

插入排序

插入排序是一种简单直观的排序算法，它通过将一个元素插入到已经排好序的序列中，从而得到一个更长的排好序的序列。具体来说，插入排序每一轮将一个元素插入到已排好序的子数组中，并将其余元素向后移动。

C++ 代码如下：

void insertionSort(int arr[], int n)
{
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i]; // 待插入的元素
        j = i - 1;
        // 将大于待插入元素的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        // 将待插入元素插入到正确的位置
        arr[j+1] = key;
    }
}

快速排序

快速排序是一种高效的排序算法，它通过选择一个枢纽元素，将序列拆分成两个部分，一部分小于枢纽元素，一部分大于枢纽元素，并对两个子序列递归进行排序。具体来说，快速排序每一轮选择一个枢纽元素，并将小于枢纽元素的元素放在枢纽元素左边，大于枢纽元素的元素放在右边。然后以相同的方式对左右两个子序列递归进行排序。

C++ 代码如下：

void quickSort(int arr[], int left, int right)
{
    int i = left, j = right;
    int pivot = arr[(left + right) / 2]; // 选择枢纽元素
    while (i <= j) {
        // 找到左侧大于枢纽元素的元素
        while (arr[i] < pivot) {
            i++;
        }
        // 找到右侧小于枢纽元素的元素
        while (arr[j] > pivot) {
            j--;
        }
        // 交换左右元素
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    // 递归排序左侧和右侧的子序列
    if (left < j) {
        quickSort(arr, left, j);
    }
    if (i < right) {
        quickSort(arr, i, right);
    }
}

归并排序

归并排序是一种经典的分治思想的排序算法，它将序列分成两个子序列，对每个子序列分别进行排序，最后合并两个有序子序列。具体来说，归并排序先将序列拆分成两个子序列，对两个子序列分别递归进行排序，然后将两个有序子序列合并成一个有序序列。

C++代码如下：

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    // 将数据拷贝到两个临时数组中
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    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 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);
    }
}

相关推荐