使用swap函数

template<typename T>
void bubbleSort2(T arr[], int n){
    int newn; //使用newn进行优化
    
    do{
        newn = 0;
        for(int i = 1; i < n; i ++){
            if(arr[i-1] > arr[i]){
                swap(arr[i-1], arr[i]);
                // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                newn = i;            
            }        
        }
        n = newn;
    }while(newn > 0);
}

使用基本交换

template<typename T>
void bubbleSort4(T arr[], int n){
    int newn; //使用newn进行优化
    int i,j;
    T temp;
    do{
        newn = 0;
        for(i = 1; i < n; i ++){
            if(arr[i-1] > arr[i]){
                temp = arr[i-1];
                arr[i-1] = arr[i];
                arr[i] = temp;
                // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                newn = i;            
            }        
        }
        n = newn;
    }while(newn > 0);
}

测试代码

#include "SortTestHelper.h"
#include "SelectionSort.h"
#include "InsertionSort.h"
#include "BubbleSort.h"
int main(){
    int n = 10000;
    int *arr = SortTestHelper::generateRandomArray(n, 0, n);
    int *arr2 = SortTestHelper::copyIntArray(arr, n);
    int *arr3 = SortTestHelper::copyIntArray(arr, n);
    int *arr4 = SortTestHelper::copyIntArray(arr, n);
    int *arr5 = SortTestHelper::copyIntArray(arr, n);
    int *arr6 = SortTestHelper::copyIntArray(arr, n);
    //SortTestHelper::testSort("Selection Sort",selectionSort,arr,n);
    //SortTestHelper::testSort("Insertion Sort",insertionSort,arr2,n);
    //SortTestHelper::testSort("Bubble Sort",bubbleSort,arr3,n);
    SortTestHelper::testSort("Bubble Sort 2",bubbleSort2,arr4,n);
    //SortTestHelper::testSort("Bubble Sort 3",bubbleSort3,arr5,n);
    SortTestHelper::testSort("Bubble Sort 4",bubbleSort4,arr6,n);
    return 0;
}

当n=10000时，

当n=100000时，

不使用swap函数时，性能提升了近一倍。