冒泡排序1

冒泡排序是一种简单的排序算法，它的基本思想是通过重复遍历待排序的序列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历序列的工作是重复地进行直到没有再需要交换，也就是说该序列已经排序完成。在这个过程中，每经过一次遍历，最大的元素就会"冒"到序列的末尾，因此称为"冒泡排序"。 在冒泡排序中，有三个主要的问题需要解决： 1. **记录交换的位置**：在一趟排序过程中，如果有多个记录位于它们最终应该在的位置，我们需要知道最后一次交换的位置。这个问题可以通过设置一个变量`exchange`来解决。在每一轮比较中，如果发生了交换，就更新`exchange`为当前的交换位置。当一趟排序结束后，`exchange`所记录的位置之后的所有元素都已经排好序了。 2. **确定排序的范围**：每一轮起泡排序的范围应该逐渐减小，因为前面的元素已经排好序。我们可以通过设置一个变量`bound`来记录无序区的最后位置。在每一轮排序结束后，`bound`会被更新为`exchange`的值，这样下一轮排序只需处理`r[1]`到`r[bound]`之间的元素，因为`bound`之后的元素已经有序。 3. **判断排序的结束**：为了确定冒泡排序是否结束，我们可以初始化`exchange`为0。在每一轮比较中，如果发生交换，`exchange`的值会被设置为非零。一轮比较结束后，如果`exchange`仍为0，说明在整个过程中没有发生交换，这意味着序列已经是有序的，排序过程可以停止。 以下是一个简单的C++实现冒泡排序的代码示例： ```cpp #include <iostream> using namespace std; class BubbleSort { public: void sort(int nums[], int n) { int exchange = 1, bound = n; while (exchange) { exchange = 0; for (int i = 1; i < bound; i++) { if (nums[i] < nums[i - 1]) { swap(nums[i], nums[i - 1]); exchange = i; } } bound = exchange; } } }; int main() { BubbleSort sort; int nums[] = {3, 2, 0, -1, 5}; sort.sort(nums, 5); for (int i = 0; i < 5; i++) cout << nums[i] << " "; cout << endl; } ``` 这段代码中定义了一个名为`BubbleSort`的类，包含一个成员函数`sort`用于执行冒泡排序。在`main`函数中，创建了`BubbleSort`类的对象，并调用其`sort`方法对数组`nums`进行排序，最后打印出排序后的结果。 总结来说，冒泡排序的关键在于通过相邻元素的比较和交换逐步将最大（或最小）的元素移动到序列的末尾，同时通过`exchange`和`bound`变量来优化排序过程，减少不必要的比较和交换，提高效率。尽管冒泡排序的时间复杂度在最坏情况下为O(n^2)，但它对于小规模或部分有序的数据，仍具有一定的实用性。