博客

C++中常用的排序算法有多种，其中包括冒泡排序、选择排序、插入排序、快速排序等等。下面我们将逐一进行讲解，包括算法思路和代码实现。

冒泡排序

冒泡排序是一种基础的排序算法，思路比较简单，就是不断地相邻比较并交换位置。其时间复杂度为O(N^2)，效率比较低。下面是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+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

选择排序

选择排序的思路是，每一次从待排序的数据中选出最小的元素，放到已排序的数组的末尾。其时间复杂度为O(N^2)，与冒泡排序相同。下面是C++代码实现示例：

void selectionSort(int arr[], int n) {
    int minIndex;
    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;
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

插入排序

插入排序的思路是，将待排序的数据不断地插入已排序的数组中，形成一个有序的数组。其时间复杂度也是O(N^2)，但是对于小规模的数据可以得到比较好的效率。下面是C++代码实现示例：

void insertionSort(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;
    }
}

快速排序

快速排序的思路是，选取一个基准值，将待排序数组中小于基准值的数放在其左边，大于基准值的数放在其右边。然后分别对左右两个子数组再进行快速排序，重复上述过程，直到整个数组有序。其时间复杂度为O(NlogN)，最坏情况下也只是O(N^2)。下面是C++代码实现示例：

void quickSort(int arr[], int left, int right) {
    int i=left, j=right, pivot=arr[left];
    while(i<j) {
        while(i<j && arr[j]>pivot) j--;
        while(i<j && arr[i]<=pivot) i++;
        if(i<j) swap(arr[i], arr[j]);
    }
    arr[left] = arr[i];
    arr[i] = pivot;
    if(left < i-1) quickSort(arr, left, i-1);
    if(i+1 < right) quickSort(arr, i+1, right);
}

以上是C++中几种重要的排序算法的简要讲解和代码实现示例。在实际应用中，需要结合具体的情况选择合适的算法。