c语言冒泡排序，指针，数组

矫情吗；* 2021-11-19 13:10 343阅读 0赞

**冒泡排序算法的运作如下：**

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

###  时间复杂度 ###

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数

![C][]

和记录移动次数

![M][]

均达到最小值：

![C\_\{min\}=n-1][C_min_n-1]

，

![M\_\{min\}=0][M_min_0]

。

所以，冒泡排序最好的时间复杂度为 ![O(n)][O_n] 。  
　　若初始文件是反序的，需要进行

![n-1][]

趟排序。每趟排序要进行

![n-i][]

次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

![C\_\{max\}=\\frac\{n(n-1)\}\{2\}=O(n^\{2\})][C_max_frac_n_n-1_2_O_n_2]

![M\_\{max\}=\\frac\{3n(n-1)\}\{2\}=O(n^\{2\})][M_max_frac_3n_n-1_2_O_n_2]

冒泡排序的最坏时间复杂度为

![O(n^\{2\})][O_n_2]

。

综上，因此冒泡排序总的平均时间复杂度为

![O\\left(n^2\\right)][O_left_n_2_right]

。

2. Use pointer to complete the assignment. define array for three integers.

Write three functions, which are input(), deal(), print()  
The input() function needs to complete three number's input.  
The deal() function needs to put the smallest onto the first position, put the biggest one onto the end of the sequence.

The print() function needs to print the result.

#include<stdio.h> int input(int* a); int output(int* a); int deal(int *); int main() { int array[3]; input(array); deal(array); output(array); return 0; } int input(int* a) { int i; for(i=0;i<3;i++) { scanf("%d",&*(a+i)); } return 0; } int deal(int *a) { int min,i,j; for(i=0;i<3-1;i++) for(j=0;j<2-i;j++) if(*(a+j)>*(a+j+1)) { min=*(a+j); *(a+j)=*(a+j+1); *(a+j+1)=min; } return 0; } int output(int* a) { int i; for(i=0;i<3;i++) printf("%d ",*(a+i)); return 0; }

![Center][]

转载于:https://www.cnblogs.com/wsq724439564/p/3258161.html

[C]: /images/20211119/bac183ea92a44ffda79256a75de9c6f3.png
[M]: /images/20211119/8d72ebd711e148909192f3a720ca4105.png
[C_min_n-1]: /images/20211119/8b6494bc2d8849568897d0c73f9b902c.png
[M_min_0]: /images/20211119/c92ab3abccbc42e1b188ea4fc3ae0c55.png
[O_n]: /images/20211119/4e5f7c1cc1a14377a63a5b6ce3341b27.png
[n-1]: /images/20211119/4198eb469eb34e8ab631cdcaab6472ec.png
[n-i]: /images/20211119/e4f6c6bfa8054971a2e8cd534397c4d7.png
[C_max_frac_n_n-1_2_O_n_2]: /images/20211119/5da5b06d4ab04292b7dfe83324b4ab9e.png
[M_max_frac_3n_n-1_2_O_n_2]: /images/20211119/5edf4a046f7e48f1a1e0df542f1652eb.png
[O_n_2]: /images/20211119/14eede133fee486cb00d1637f4230d2d.png
[O_left_n_2_right]: /images/20211119/2fbad1efc8ff458098f65de870593500.png
[Center]: /images/20211119/f7b8cf9e422741d7a8b1868374559a21.png