冒泡排序的C++实现详解

资源摘要信息:"cpp代码-冒泡排序" 冒泡排序是计算机科学中最简单的排序算法之一，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序算法虽然简单，但效率不高，因为它需要对每个元素都进行比较，并且在最好的情况下（数组已经有序）也需要进行n-1次比较，其中n为数组长度。尽管如此，冒泡排序算法因其易于理解和实现，在教学中常被用作排序算法的入门。 以下是冒泡排序算法的C++实现： ```cpp #include <iostream> using namespace std; // 函数声明 void bubbleSort(int arr[], int n); void swap(int &a, int &b); void printArray(int arr[], int size); int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]); cout << "未排序的数组: "; printArray(arr, n); bubbleSort(arr, n); cout << "排序后的数组: "; printArray(arr, n); return 0; } // 冒泡排序函数 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]) swap(arr[j], arr[j+1]); } // 交换两个数的函数 void swap(int &a, int &b) { int temp = a; a = b; b = temp; } // 打印数组的函数 void printArray(int arr[], int size) { for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } ``` 在上述代码中，`bubbleSort` 函数通过双层循环实现排序，外层循环控制排序的轮数，内层循环负责进行相邻元素的比较和交换。`swap` 函数用于交换两个变量的值。`printArray` 函数用于输出数组的当前状态。 冒泡排序算法的复杂度分析： - 最坏情况时间复杂度：O(n^2)，当输入数组的逆序度越高，需要的比较和交换次数越多。 - 最好情况时间复杂度：O(n)，当输入数组已经是正序时，只需进行一轮比较，不需要交换。 - 平均情况时间复杂度：O(n^2)，因为每一轮排序都可能将一个元素排到正确的位置。 - 空间复杂度：O(1)，因为排序是原地进行，不需要额外的存储空间。 除了基本的冒泡排序外，还有各种改进的版本，如设置标志位减少不必要的比较、鸡尾酒排序（双向冒泡排序）等，以提高效率。 冒泡排序尽管不适用于大量数据的排序任务，但在处理小数据集或对排序性能要求不高的场合中，它的代码简洁易懂，仍然有着一定的应用价值。