©2020-2024 ioDraw All rights reserved
Dynamic demonstration ：
Train of thought analysis
*
Two adjacent numbers are compared ,n[i] Follow n[j+1] than , If n[i]>n[j+1], Then the number will be exchanged ,
*
j++, Repeat the above steps , After the first trip , The maximum number will be determined in the last place , This is bubble sorting, also known as big （ Small ） Numerical bottom ,
*
i++, Repeat the above steps , until i=n-1 end , Sorting complete .
Negative impurity analysis
*
Whether the original array is ordered or not , The time complexity is O（n2）. Because no number has to be compared with other numbers ,（n-1）2 second , decompose ：n2+2n-1,
Remove the low power sum constant , be left over n2, So the final time complexity is n2
*
Spatial complexity is O（1）, Because only one auxiliary variable is defined , And n Regardless of the size of the , So the spatial complexity is O（1）
If only exchange 5 Number of columns ：
# 1. The diagram is as follows ：
<>2. What does bubble sorting mean ?
<>3. Bubble sort ascending idea ：
The core code is as follows ：
for (i = n - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (a[j] > a[j + 1]) {
temp= a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } }
<>4.PTA Examples ：
This question requires bubble sorting , Will the given n An integer is output after sorting from small to large , And output the intermediate results of each step in the sorting process .
The algorithm steps of bubble sorting are described as follows ：
The first 1 step ： In unsorted n number （a[0]〜
a[n−1]） in , from a[0] rise , Compare two adjacent numbers in turn , If the adjacent elements do not meet the order requirements , Then exchange them . After this operation , Maximum element in array “ Bubbling ” reach a[n−1];
The first 2 step ： In the remaining unordered n−1 number （a[0] 〜
a[n−2]） in , from a[0] rise , Compare two adjacent numbers in turn , If the adjacent elements do not meet the order requirements , Then exchange them . After this operation ,a[0] 〜
a[n−2] Maximum element in “ Bubbling ” reach a[n−2]; ……
The first i step ： In the remaining unordered n−k number （a[0]〜a[n−i]） in , from a[0] rise , Compare two adjacent numbers in turn , If the adjacent elements do not meet the order requirements , Then exchange them . After this operation ,a[0]
〜 a[n−i] Maximum element in “ Bubbling ” reach a[n−i]; …… The first n−1 step ： In the remaining unordered 2 number （a[0]
〜a[1]） in , Compare the two numbers , If the order requirements are not met , Then exchange them . After this operation ,a[0] 〜 a[1] Maximum element in “ Bubbling ” reach a[1].
Input format ：
The first line of input gives a value of no more than 10 Positive integer of n. The second line gives n Integer , Separated by spaces .
Output format ：
The intermediate results of the corresponding steps in the sorting process are output in each row , After each step a[0]〜 a[n−1] Value of , There is a space between adjacent numbers , There must be no extra space at the end of the line .
sample input ：
input ：
5 8 7 6 0 1
output ：
7 6 0 1 8 6 0 1 7 8 0 1 6 7 8 0 1 6 7 8
code ：
#include<stdio.h> int main() { int a[10],i,j,n,k,temp,flag; scanf("%d",&n); for
(i=0;i<n;i++) {scanf("%d",&a[i]);} if(n==1) printf("%d",a[0]); for(i=n-1;i>=1;i
--) { flag=1; for(j=0;j<i;j++) { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1
]=temp; flag=0; } } for(k=0;k<n-1;k++) { printf("%d ",a[k]); } printf("%d\n",a[n
-1]); } return 0; }
Technology