【C++】整理了一些常见的排序算法

提示：1. 冒泡排序         2. 选择排序       3. 插入排序        4. 希尔排序        5. 快速排序        6. 归并排序        7. 堆排序      8. 计数排序        9. 桶排序        10. 基数排序

目录

1. 冒泡排序

2. 选择排序       

3. 插入排序

4. 希尔排序

5. 快速排序

6. 归并排序

7. 堆排序      

8. 计数排序

9. 桶排序

10. 基数排序

---

1. 冒泡排序

        冒泡排序是一种简单的排序算法，它重复地比较相邻的两个元素，并交换它们的位置，直到整个数组排序完成。冒泡排序的基本思想是将较大的元素不断往后移动，就像气泡在水中不断上浮一样，因此得名冒泡排序。

下面是冒泡排序的具体步骤：

1. 从数组的第一个元素开始，将相邻的两个元素进行比较。
2. 如果前一个元素大于后一个元素，则交换这两个元素的位置。
3. 继续进行相邻元素的比较和交换，直到最后一个元素。
4. 重复以上步骤，每次迭代将最大的元素移动到数组的最后。
5. 继续进行下一轮迭代，直到所有元素都排序完成。

        冒泡排序的时间复杂度为O(n^2)，其中n是数组的长度。尽管冒泡排序不是最高效的排序算法，但它简单易懂，并且在某些情况下是适用的。

//冒泡排序
void bubbleSort(int array[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // 交换相邻元素的位置
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

2. 选择排序       

        选择排序也是一种简单的排序算法，它每次从未排序部分选择最小（或最大）的元素，然后将其放置在已排序部分的末尾。选择排序的基本思想是找到未排序部分的最小元素并交换到已排序部分的末尾，逐步构建有序序列。

以下是选择排序的具体步骤：

1. 从数组的第一个元素开始，假设它是最小的元素。
2. 在未排序部分中，遍历查找最小的元素，并记录其索引。
3. 将找到的最小元素与未排序部分的第一个元素交换位置。
4. 重复以上步骤，每次迭代将未排序部分的最小元素放置在已排序部分的末尾。
5. 继续进行下一轮迭代，直到所有元素都排序完成。

        选择排序的时间复杂度为O(n^2)，其中n是数组的长度。与冒泡排序类似，选择排序也是一种简单但效率较低的排序算法。

//选择排序
void selectionSort(int array[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < size; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // 交换最小元素和当前位置的元素
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

3. 插入排序

        插入排序是一种简单直观的排序算法，它将数组划分为已排序和未排序两部分，逐个将未排序的元素插入到已排序部分的正确位置。插入排序的基本思想是将一个元素插入到已排序部分的正确位置，并不断扩大已排序部分的长度。

以下是插入排序的具体步骤：

1. 从数组的第二个元素开始，将其视为要插入的元素。
2. 将要插入的元素与已排序部分的元素进行比较，找到合适的位置。
3. 移动已排序部分中大于要插入元素的元素，为要插入元素腾出位置。
4. 将要插入的元素插入到已排序部分的正确位置。
5. 继续进行下一轮迭代，将下一个未排序元素插入到已排序部分。

        插入排序的时间复杂度为O(n^2)，其中n是数组的长度。尽管插入排序在最坏情况下的性能不如其他排序算法，但在某些情况下，它的性能可能更好。

//插入排序
void insertionSort(int array[], int size) {
    for (int i = 1; i < size; i++) {
        int key = array[i];
        int j = i - 1;

        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }

        array[j + 1] = key;
    }
}

4. 希尔排序

        希尔排序是一种高效的插入排序算法的改进版本，它通过将数组分成若干个子序列进行排序，然后逐渐减小子序列的长度，最终完成整个数组的排序。希尔排序的特点是可以在一开始就进行多次的插入排序，从而使得较小的元素可以快速移动到合适的位置。

以下是希尔排序的具体步骤：

1. 选择一个增量序列，通常为数组长度的一半，然后将数组按照增量序列分成若干个子序列。
2. 对每个子序列进行插入排序，即对每个子序列中的元素进行直接插入排序。
3. 逐渐缩小增量序列，重复第2步的操作，直到增量为1。
4. 最后进行一次增量为1的插入排序，完成整个数组的排序。

        希尔排序的时间复杂度取决于增量序列的选择，但在一般情况下为O(n^2)。尽管如此，希尔排序在实际应用中的性能通常优于简单的插入排序。

//希尔排序
void shellSort(int array[], int size) {
    for (int gap = size / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < size; i++) {
            int temp = array[i];
            int j;

            for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                array[j] = array[j - gap];
            }

            array[j] = temp;
        }
    }
}

5. 快速排序

        快速排序是一种高效的排序算法，采用了分治的思想。它通过选择一个基准元素，将数组划分为两个子数组，其中一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素，然后递归地对这两个子数组进行排序。

以下是快速排序的具体步骤：

1. 选择一个基准元素，可以是数组中的任意一个元素。
2. 将数组分割为两个子数组，一个子数组中的元素都小于基准元素，另一个子数组中的元素都大于基准元素。
3. 对这两个子数组分别进行递归调用快速排序，直到子数组的长度为1或0时停止递归。
4. 将子数组合并起来，即将基准元素和两个排序后的子数组合并在一起。

        快速排序的时间复杂度为O(nlogn)，其中n是数组的长度。它通常是实际应用中最快的排序算法之一，但在最坏情况下的性能可能较差。

//快速排序
int partition(int array[], int low, int high) {
    int pivot = array[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (array[j] < pivot) {
            i++;
            // 交换元素
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    // 将基准元素放置在正确的位置
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    return i + 1;
}

void quickSort(int array[], int low, int high) {
    if (low < high) {
        int pivot = partition(array, low, high);
        quickSort(array, low, pivot - 1);
        quickSort(array, pivot + 1, high);
    }
}

6. 归并排序

        归并排序是一种高效的排序算法，它采用了分治的思想。它将数组划分为较小的子数组，然后对这些子数组进行排序，并最后将它们合并成一个有序的数组。归并排序的关键在于合并操作，通过合并两个有序的子数组来得到一个有序的数组。

以下是归并排序的具体步骤：

1. 将数组不断划分为较小的子数组，直到子数组的长度为1。
2. 对每个子数组进行排序，可以使用递归调用归并排序。
3. 合并两个有序的子数组，得到一个更大的有序数组。
4. 重复合并操作，直到所有子数组合并为一个完整的有序数组。

        归并排序的时间复杂度为O(nlogn)，其中n是数组的长度。它是一种稳定的排序算法，并且在处理大规模数据时具有较好的性能。

//归并排序
void merge(int array[], int low, int mid, int high) {
    int n1 = mid - low + 1;
    int n2 = high - mid;

    int leftArray[n1];
    int rightArray[n2];

    for (int i = 0; i < n1; i++) {
        leftArray[i] = array[low + i];
    }

    for (int j = 0; j < n2; j++) {
        rightArray[j] = array[mid + 1 + j];
    }

    int i = 0;
    int j = 0;
    int k = low;

    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            array[k] = leftArray[i];
            i++;
        } else {
            array[k] = rightArray[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        array[k] = leftArray[i];
        i++;
        k++;
    }

    while (j < n2) {
        array[k] = rightArray[j];
        j++;
        k++;
    }
}

void mergeSort(int array[], int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        mergeSort(array, low, mid);
        mergeSort(array, mid + 1, high);
        merge(array, low, mid, high);
    }
}

7. 堆排序      

         堆排序利用堆这种数据结构进行排序，它将数组看作是一个完全二叉树，并通过构建最大堆或最小堆来实现排序。在堆中，最大堆保证每个节点的值都大于或等于其子节点的值，最小堆保证每个节点的值都小于或等于其子节点的值。

以下是堆排序的具体步骤：

1. 将数组构建成一个最大堆或最小堆。
2. 交换堆顶元素（最大或最小元素）和堆中的最后一个元素。
3. 将堆的大小减小1，并重新调整堆，使其满足堆的性质。
4. 重复步骤2和步骤3，直到堆的大小为1，排序完成。

        堆排序的时间复杂度为O(nlogn)，其中n是数组的长度。它是一种不稳定的排序算法，但具有较好的性能，并且在实际应用中被广泛使用。

//堆排序
void heapify(int array[], int size, int root) {
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

    if (left < size && array[left] > array[largest]) {
        largest = left;
    }

    if (right < size && array[right] > array[largest]) {
        largest = right;
    }

    if (largest != root) {
        // 交换元素
        int temp = array[root];
        array[root] = array[largest];
        array[largest] = temp;

        heapify(array, size, largest);
    }
}

void heapSort(int array[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(array, size, i);
    }

    for (int i = size - 1; i > 0; i--) {
        // 交换堆顶元素和当前位置元素
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;

        heapify(array, i, 0);
    }
}

8. 计数排序

        计数排序是一种非比较的排序算法，适用于一定范围内的整数排序。它的基本思想是通过统计每个元素出现的次数，然后根据元素的大小顺序重新排列数组。

以下是计数排序的具体步骤：

1. 找出待排序数组的最大值，并确定计数数组的大小。
2. 统计数组中每个元素出现的次数，并存储在计数数组中。
3. 计算计数数组中每个元素的累加值，得到每个元素在排序后数组中的位置。
4. 创建一个临时数组，将待排序数组中的元素按照计数数组中的位置依次放入临时数组中。
5. 将临时数组中的元素复制回原始数组。

        计数排序的时间复杂度为O(n+k)，其中n是数组的长度，k是待排序数组的最大值。计数排序的性能非常高效，但需要满足一定的条件。

//计数排序
void countingSort(int array[], int size) {
    int maxElement = array[0];
    for (int i = 1; i < size; i++) {
        if (array[i] > maxElement) {
            maxElement = array[i];
        }
    }

    int countArray[maxElement + 1] = {0};

    for (int i = 0; i < size; i++) {
        countArray[array[i]]++;
    }

    for (int i = 1; i <= maxElement; i++) {
        countArray[i] += countArray[i - 1];
    }

    int sortedArray[size];

    for (int i = size - 1; i >= 0; i--) {
        sortedArray[countArray[array[i]] - 1] = array[i];
        countArray[array[i]]--;
    }

    for (int i = 0; i < size; i++) {
        array[i] = sortedArray[i];
    }
}

9. 桶排序

        桶排序是一种非比较的排序算法，适用于在一定范围内的浮点数排序。它将待排序数组划分为若干个桶，并将每个元素分配到对应的桶中，然后对每个桶中的元素进行排序，最后将所有桶中的元素依次取出，即可得到有序的数组。

以下是桶排序的具体步骤：

1. 确定桶的个数，每个桶代表一个范围区间。
2. 遍历待排序数组，将每个元素放入对应的桶中。
3. 对每个桶中的元素进行排序，可以使用插入排序、快速排序等排序算法。
4. 按照桶的顺序依次取出桶中的元素，得到有序的数组。

        桶排序的时间复杂度取决于桶的个数和排序算法的性能。在某些情况下，桶排序可以达到线性时间复杂度。

//桶排序
#include <iostream>
#include <vector>
#include <algorithm>

void bucketSort(float array[], int size) {
    // 创建桶
    std::vector<float> buckets[size];

    // 将元素分配到对应的桶中
    for (int i = 0; i < size; i++) {
        int bucketIndex = size * array[i];
        buckets[bucketIndex].push_back(array[i]);
    }

    // 对每个桶中的元素进行排序
    for (int i = 0; i < size; i++) {
        std::sort(buckets[i].begin(), buckets[i].end());
    }

    // 合并所有的桶
    int index = 0;
    for (int i = 0; i < size; i++) {
        for (float element : buckets[i]) {
            array[index++] = element;
        }
    }
}

10. 基数排序

        基数排序是一种非比较的排序算法，它按照数字的每个位进行排序。基数排序的基本思想是从最低位（个位）到最高位（高位）依次对数字进行排序，每一轮按照当前位的值进行分桶，然后按照桶的顺序将数字重新排列。通过多轮排序，最终得到一个有序的数组。

以下是基数排序的具体步骤：

1. 确定排序的轮数，根据数字的最大位数来决定。
2. 对每一轮进行分桶操作，根据当前位的值将数字放入对应的桶中。
3. 按照桶的顺序将数字重新排列，得到新的数组。
4. 重复以上步骤，直到所有的位都被遍历完。

        基数排序的时间复杂度为O(d * (n + k))，其中n是数组的长度，d是数字的最大位数，k是进制数。基数排序通常用于处理整数类型的数据。

//基数排序
int getMax(int array[], int size) {
    int maxElement = array[0];
    for (int i = 1; i < size; i++) {
        if (array[i] > maxElement) {
            maxElement = array[i];
        }
    }
    return maxElement;
}

void countingSort(int array[], int size, int exp) {
    int output[size];
    int count[10] = {0};

    for (int i = 0; i < size; i++) {
        count[(array[i] / exp) % 10]++;
    }

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (int i = size - 1; i >= 0; i--) {
        output[count[(array[i] / exp) % 10] - 1] = array[i];
        count[(array[i] / exp) % 10]--;
    }

    for (int i = 0; i < size; i++) {
        array[i] = output[i];
    }
}

void radixSort(int array[], int size) {
    int maxElement = getMax(array, size);

    for (int exp = 1; maxElement / exp > 0; exp *= 10) {
        countingSort(array, size, exp);
    }
}