冒泡排序

用图说话

冒牌排序

放码过来

void BubbleSortClass::bubbleSort(vector<int> testData)
{
    /*
     冒泡算法思路：相邻的两个数两两交换，交换完整个数组后，就算一趟，然后再继续交换，一共交换数组长度-1次
     那这里，我脑中的思路就是有个for循环
     for() { // 控制走多少趟 -> 数组长度-1 趟
         for() { // 走的每一趟做的操作都是一样的，就是相邻两个元素对比，大的往上冒
             if(相邻有个元素对比) {
                 // 大的网上冒，那就是交换元素位置
             }
         }
     }

     */
    vector<int> array = testData;
    for (int i=0; i<array.size()-1; i++) {
        // 这个为什么是j<array.size() - 1 因为下面有array[j+1],
        // 如果是j < array.size(),那下面的array[j+1] 当j=数组的最后下标时，array[j+1]就溢出了
        for (int j = 0; j<array.size()-1; j++) {
            if (array[j]>array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
    
    cout << "还未开始冒泡排序的数据" << endl;
    for (int i=0; i<testData.size(); i++) {
        cout << testData[i] << endl;
    }
    cout << "冒泡排序后的数据" << endl;
    for (int i=0; i<array.size(); i++) {
        cout << array[i] << endl;
    }
}

上面的代码是简单的冒泡排序，这个排序存在一个问题：如果我一共要走5趟，但是第3趟的时候，我就已经排好序了，那么这个时候应该停止比较了，但是这个算法，还是会继续比较，相当做了无用功

那么对于这个问题，我们要做的操作就是控制走几趟，如果我已经有序了，那么最外层的for循环应该就不用走了；因此我们应该在for循环的判断条件中加一个开关，当我打开开关的时候，照常进行，当我关闭开关的时候，停止循环，我已经有序了。
那么问题来了，我什么时候关闭开关呢？如果我有序了，那么在内部for循环里面，应该是不存在交换元素的操作了
那么我们在交换元素的操作将开关打开，然后在内部for的时候将开关关闭，这样，如果内部for了一遍，没有走交换元素的操作，那么开关就是关闭的，那么等下外部for循环就停止了

// 交换元素的操作
  if (array[j]>array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }

完整代码

void BubbleSortClass::bubbleSort(vector<int> testData)
{
    /*
     冒泡算法思路：相邻的两个数两两交换，交换完整个数组后，就算一趟，然后再继续交换，一共交换数组长度-1次
     那这里，我脑中的思路就是有个for循环
     for() { // 控制走多少趟 -> 数组长度-1 趟
         for() { // 走的每一趟做的操作都是一样的，就是相邻两个元素对比，大的往上冒
             if(相邻有个元素对比) {
                 // 大的网上冒，那就是交换元素位置
             }
         }
     }

     */
    vector<int> array = testData;
    // 添加控制外部循环的开关
    int flag = 1;
    
    // array.size()-1 && flag 当flag = 0的时候 这整个就为0了，i是不可能小于0的，所以循环就停止了
    for (int i=0; i<array.size()-1 && flag; i++) {
        flag = 0;
        // 这个为什么是j<array.size() - 1 因为下面有array[j+1],
        // 如果是j < array.size(),那下面的array[j+1] 当j=数组的最后下标时，array[j+1]就溢出了
        for (int j = 0; j<array.size()-1; j++) {
            if (array[j]>array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                flag = 1;
            }
        }
    }
    
    cout << "还未开始冒泡排序的数据" << endl;
    for (int i=0; i<testData.size(); i++) {
        cout << testData[i] << endl;
    }
    cout << "冒泡排序后的数据" << endl;
    for (int i=0; i<array.size(); i++) {
        cout << array[i] << endl;
    }
}

code地址

https://github.com/ChenZeBin/TheDataStructureByUsingCpp.git