冒泡排序1

preview
需积分: 0 0 下载量 23 浏览量 更新于2022-08-03 收藏 199KB PDF 举报
冒泡排序是一种简单的排序算法,它的基本思想是通过重复遍历待排序的序列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历序列的工作是重复地进行直到没有再需要交换,也就是说该序列已经排序完成。在这个过程中,每经过一次遍历,最大的元素就会"冒"到序列的末尾,因此称为"冒泡排序"。 在冒泡排序中,有三个主要的问题需要解决: 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),但它对于小规模或部分有序的数据,仍具有一定的实用性。