接做名片的网站/国内看不到的中文新闻网站

1.1 冒泡排序的过程

数据长度n，那么则需要进行n-1轮冒泡排序
⁣⁣⁣⁣　
第一趟冒泡排序过程：
将第一个关键字与第二个关键字比较，若为逆序，则交换，然后比较第二个和第三个关键字，直到第n-1个关键字和第n个关键字比较完毕为止。 （比较n-1次）
⁣⁣⁣⁣　
第 i 趟冒泡排序过程：
从第一个关键字开始，依次向后进行比较，直到第n-i个关键字为止。 （比较n-i次）
⁣⁣⁣⁣　
这里的第 i 趟过程为从第一个关键字到第 n-i 个关键字 ，第 n-i 个关键字的下标为n-i-1，那么比较的前一个关键字的下标j就是从j = 0到j = n-i-2。

2.1 时间复杂度

第1趟：比较n-1次
第2趟：比较n-2次
…
第i趟：比较n-i次
⁣⁣⁣⁣　
长度为n时，需要比较n-1趟
那么比较次数 = (n-1) + (n-2) + (n-3) + … + (n - (n-1)) = n * (n-1) / 2
　
Bubble Sort的时间复杂度:
最好情况：O(n)
最坏情况：O(n²)
Bubble Sort的平均时间复杂度：O(n²)

2.2 空间复杂度

Bubble Sort的空间复杂度：O(1)

2.3 稳定性

相同大小的数据在排序前后不会改变顺序，冒泡排序是稳定排序

3.1 functions code(c/c++)

//遍历
void TravelArray(ElemType *arr,int length,bool isAfter){if(isAfter)   //如果为真 即!=0 排序后遍历cout<<"After  Sort：  ";elsecout<<"Before Sort：  ";for(int i = 0;i<length;++i)cout<<arr[i]<<" ";cout<<endl;
}//冒泡排序
void BubbleSort(ElemType *arr,int length){for(int i = 0;i<length-1;++i){  //length个数据 需要排序length - 1 轮for(int j = 0;j<length-i-1;++j){   //每一轮j从下标0开始 到下标len-i-2结束if(arr[j]>arr[j+1]){    //如果前面比后面大 交换ElemType temp;temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}//打印每趟排序结果cout<<"第"<<i+1<<"趟排序序列：";for(int k = 0;k<length;k++)cout<<arr[k]<<" ";cout<<endl<<"-----------------------"<<endl;}
}

3.2 main code(c/c++)

int main(){ElemType arr[NUM] = {99,10,33,16,44,23,12,53,66,95};TravelArray(arr,NUM);cout<<"-----------------------"<<endl;cout<<"-----------------------"<<endl;BubbleSort(arr,NUM);cout<<"-----------------------"<<endl;TravelArray(arr,NUM,true);
}

4. 程序示例

Before Sort： 99 10 33 16 44 23 12 53 66 95
-----------------------
-----------------------
第1趟排序序列：10 33 16 44 23 12 53 66 95 99
-----------------------
第2趟排序序列：10 16 33 23 12 44 53 66 95 99
-----------------------
第3趟排序序列：10 16 23 12 33 44 53 66 95 99
-----------------------
第4趟排序序列：10 16 12 23 33 44 53 66 95 99
-----------------------
第5趟排序序列：10 12 16 23 33 44 53 66 95 99
-----------------------
第6趟排序序列：10 12 16 23 33 44 53 66 95 99
-----------------------
第7趟排序序列：10 12 16 23 33 44 53 66 95 99
-----------------------
第8趟排序序列：10 12 16 23 33 44 53 66 95 99
-----------------------
第9趟排序序列：10 12 16 23 33 44 53 66 95 99
-----------------------
-----------------------
After  Sort： 10 12 16 23 33 44 53 66 95 99Process returned 0 (0x0)   execution time : 0.145 s
Press any key to continue.

——————END-2021-12-31——————