您现在的位置是：首页 >其他 >【C++】排序算法大全（详解）网站首页其他

C++中常见的排序算法有很多种，每种算法都有其独特的实现方式、时间复杂度和适用场景。以下是一些常见的排序算法及其C++代码示例：

1. 冒泡排序（Bubble Sort）

• ‌原理‌：通过重复遍历要排序的数列，比较相邻元素的大小并在必要时交换它们的位置，直到没有需要交换的元素为止。
• ‌时间复杂度‌：O(n2)。
• ‌示例代码‌：

void bubbleSort(int arr[], int len) {
    for(int i = 0; i < len - 1; i++) {
        for(int j = 0; j < len - 1 - i; j++) {
            if(arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. 选择排序（Selection Sort）

• ‌原理‌：从未排序序列中找到最小（或最大）的元素，放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小元素，依次类推。
• ‌时间复杂度‌：O(n2)。
• ‌示例代码‌：

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

3. 插入排序（Insertion Sort）

• ‌原理‌：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
• ‌时间复杂度‌：O(n2)（最坏情况），O(n)（最好情况）。
• ‌示例代码‌：

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

4. 归并排序（Merge Sort）

• ‌原理‌：采用分治法，将原始数组分割成较小的数组，递归地对每个子数组进行排序，然后将它们合并成一个完全排序的数组。
• ‌时间复杂度‌：O(n log n)。
• ‌示例代码‌：

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

5. 快速排序（Quick Sort）

• ‌原理‌：通过选取一个基准元素，将数组分为两部分，使得左边的元素都小于基准元素，右边的元素都大于基准元素，然后递归地对这两部分进行排序。
• ‌时间复杂度‌：O(n log n)（平均情况），O(n2)（最坏情况）。
• ‌示例代码‌：

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

6. 堆排序（Heap Sort）

• ‌原理‌：利用堆这种数据结构进行排序。首先将数组构建成一个最大堆，然后逐个取出堆顶元素，调整堆，直到数组完全有序。
• ‌时间复杂度‌：O(n log n)。
• ‌示例代码‌：

void heapSort(int arr[], int len) {
    for(int i = len / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, i, len - 1);
    }
    for(int i = len - 1; i > 0; i--) {
        swap(&arr, &arr[i]);
        maxHeapify(arr, 0, i - 1);
    }
}

7. 其他排序算法

除了上述几种常见的排序算法外，还有希尔排序、计数排序、基数排序、桶排序等非比较排序算法，它们各有其特点和适用场景。

请注意，每种排序算法都有其优缺点，在实际应用中应根据具体情况选择合适的排序算法。同时，对于金融、医疗、法律等高风险领域，使用排序算法时请务必进行充分的测试和验证，确保算法的正确性和稳定性。