冒泡排序算法以及改进

客官°小女子只卖身不卖艺 2022-07-12 08:58 210阅读 0赞

为了能给老是忘记的自己做个笔记。

冒泡排序（升序）的思想就是将最大的数逐步后移  
例如：`arr[n] ={5, 9, 8, 6, 7}`,i从数组下标0开始，j从数组下标n-1开始，依次将arr\[j\]与arr\[j-1\]比较，如果arr\[j\] < arr\[j-1\]就将arr\[j\]与arr\[j-1\]交换，直到j = i第一趟结束，然后i++进入第二趟，直到i = n - 2结束排序。

第一趟：i      j
    arr =  5 9 8 6 7    //arr[j] > arr[j-1]不做交换
           i     j
           5 9 6 8 7    //arr[j] < arr[j-1]交换8和6
           i   j
           5 6 9 8 7    //arr[j] < arr[j-1]交换9和6
           i j          
           5 6 9 8 7    //arr[j] > arr[j-1]不做交换
    第二趟：  i     j   // i++
    arr =  5 6 9 7 8    //交换7，8
             i   j
           5 6 7 9 8    //arr[j] < arr[j-1]交换7，9
             i j        
           5 6 7 9 8    //arr[j] > arr[j-1]不做交换
    依次写下去直到i = n - 2

C++代码：

#include <iostream>
    
    using namespace std;
    
    void swap(int *a, int *b){
        int t;
        t = *a;
        *a = *b;
        *b = t;
    }
    
    void sort(int p[], int n){
        for(int i = 0; i < n; i++){
            for(int j = n-1; j > i; j--){
                if(p[j] < p[j-1]){
                    swap(&p[j], &p[j-1]);
                }
            }
        }
    
        for(int i = 0; i < n; i++){
            cout << p[i] <<" ";
        }
    
    }
    
    int main(){
        int n, *p;
        cin >> n;
        p = new int[n];
        for(int i = 0; i < n; i++){
            cin >> p[i];
        }
        sort(p, n);
        return 0;
    }

改进：设置bool型变量temp，当上一次循环没有交换元素则证明排序已经完成，无需进行下一次排序，直接跳出循环。

C++代码：

#include<iostream>
    using namespace std;
    
    void swap(int *a, int *b){
        int t;
        t = *a;
        *a = *b;
        *b = t;
    }
    
    void sort(int p[], int n){
    
        bool temp; //设置变量，如果上次循环没有交换则停止排序
        for(int i = 0; i < n; i++){
            temp = 0;
            for(int j = n-1; j > i; j--){
                if(p[j] < p[j-1]){
                    temp = 1;
                    swap(&p[j], &p[j-1]);
                }
            }
    
            if(temp == 1) break;
        }
    
        for(int i = 0; i < n; i++){
            cout << p[i] <<" ";
        }
    
    }
    
    int main(){
        int n, *p;
        cin >> n;
        p = new int[n];
        for(int i = 0; i < n; i++){
            cin >> p[i];
        }
        sort(p, n);
        return 0;
    }