定义一个长度为100的int型数组，输入n(n>=1&&n<=100)
输入个值到数组中，用冒泡排序法将它们从小到大排序后输出。
简单举个"栗子": 排序4, 3, 5, 19, 1, 32, 7
他们在数组a[7]中
for(i=0;i<len-1;i++) [1]
{
for(j=0;j<len-i-1;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}
在上面的代码中(一定要看到最后):
数组: [4, 3, 5, 19, 1, 32, 7]
i = 0 j = 0: [3, 4, 5, 19, 1, 32, 7]; (4>3, 所以3 和 4交换位置)
i = 0 j = 1: [3, 4, 5, 19, 1, 32, 7]; (4<5, 所以4 不和 5交换位置)
i = 0 j = 2: [3, 4, 5, 19, 1, 32, 7]; (5<19, 所以5 不和 19交换位置)
i = 0 j = 3: [3, 4, 5, 1, 19, 32, 7]; (19>1, 所以1 和 19交换位置)
i = 0 j = 4: [3, 4, 5, 1, 19, 32, 7]; (19<32, 所以19 不和 32交换位置)
i = 0 j = 5: [3, 4, 5, 1, 19, 7, 32]; (32>7, 所以7 和 32交换位置)
i = 1 j = 0: [3, 4, 5, 1, 19, 7, 32]; (3<4, 所以3 不和 4交换位置)
i = 1 j = 1: [3, 4, 5, 1, 19, 7, 32]; (4<5, 所以4 不和 5交换位置)
i = 1 j = 2: [3, 4, 1, 5, 19, 7, 32]; (5>1, 所以1 和 5交换位置)
i = 1 j = 3: [3, 4, 1, 5, 19, 7, 32]; (5<19, 所以5 不和 19交换位置)
i = 1 j = 4: [3, 4, 1, 5, 7, 19, 32]; (19>7, 所以7 和 19交换位置)
i = 1 j = 5: [3, 4, 1, 5, 7, 19, 32]; (19<32, 所以19 不和 32交换位置)
i = 2 j = 0: [3, 4, 1, 5, 7, 19, 32]; (3<4, 所以3 不和 4交换位置)
i = 2 j = 1: [3, 1, 4, 5, 7, 19, 32]; (4>1, 所以1 和 4交换位置)
i = 2 j = 2: [3, 1, 4, 5, 7, 19, 32]; (4<5, 所以4 不和 5交换位置)
i = 2 j = 3: [3, 1, 4, 5, 7, 19, 32]; (5<7, 所以5 不和 7交换位置)
i = 2 j = 4: [3, 1, 4, 5, 7, 19, 32]; (7<19, 所以7 不和 19交换位置)
i = 2 j = 5: [3, 1, 4, 5, 7, 19, 32]; (19<32, 所以19 不和 32交换位置)
i = 3 j = 0: [1, 3, 4, 5, 7, 19, 32]; (3>1, 所以1 和 3交换位置)
i = 3 j = 1: [1, 3, 4, 5, 7, 19, 32]; (3<4, 所以3 不和 4交换位置)
i = 3 j = 2: [1, 3, 4, 5, 7, 19, 32]; (4<5, 所以4 不和 5交换位置)
i = 3 j = 3: [1, 3, 4, 5, 7, 19, 32]; (5<7, 所以5 不和 7交换位置)
i = 3 j = 4: [1, 3, 4, 5, 7, 19, 32]; (7<19, 所以7 不和 19交换位置)
i = 3 j = 5: [1, 3, 4, 5, 7, 19, 32]; (19<32, 所以19 不和 32交换位置)
i = 4 j = 0: [1, 3, 4, 5, 7, 19, 32]; (1<3, 所以1 不和 3交换位置)
i = 4 j = 1: [1, 3, 4, 5, 7, 19, 32]; (3<4, 所以3 不和 4交换位置)
i = 4 j = 2: [1, 3, 4, 5, 7, 19, 32]; (4<5, 所以4 不和 5交换位置)
i = 4 j = 3: [1, 3, 4, 5, 7, 19, 32]; (5<7, 所以5 不和 7交换位置)
i = 4 j = 4: [1, 3, 4, 5, 7, 19, 32]; (7<19, 所以7 不和 19交换位置)
i = 4 j = 5: [1, 3, 4, 5, 7, 19, 32]; (19<32, 所以19 不和 32交换位置)
i = 5 j = 0: [1, 3, 4, 5, 7, 19, 32]; (1<3, 所以1 不和 3交换位置)
i = 5 j = 1: [1, 3, 4, 5, 7, 19, 32]; (3<4, 所以3 不和 4交换位置)
i = 5 j = 2: [1, 3, 4, 5, 7, 19, 32]; (4<5, 所以4 不和 5交换位置)
i = 5 j = 3: [1, 3, 4, 5, 7, 19, 32]; (5<7, 所以5 不和 7交换位置)
i = 5 j = 4: [1, 3, 4, 5, 7, 19, 32]; (7<19, 所以7 不和 19交换位置)
i = 5 j = 5: [1, 3, 4, 5, 7, 19, 32]; (19<32, 所以19 不和 32交换位置)
i = 6 j = 0: [1, 3, 4, 5, 7, 19, 32]; (1<3, 所以1 不和 3交换位置)
i = 6 j = 1: [1, 3, 4, 5, 7, 19, 32]; (3<4, 所以3 不和 4交换位置)
i = 6 j = 2: [1, 3, 4, 5, 7, 19, 32]; (4<5, 所以4 不和 5交换位置)
i = 6 j = 3: [1, 3, 4, 5, 7, 19, 32]; (5<7, 所以5 不和 7交换位置)
i = 6 j = 4: [1, 3, 4, 5, 7, 19, 32]; (7<19, 所以7 不和 19交换位置)
i = 6 j = 5: [1, 3, 4, 5, 7, 19, 32]; (19<32, 所以19 不和 32交换位置)
别觉得我写得多, 上面这些都是下面的python代码生成的文字:
a = [4,3,5,19,1,32,7]
print("原数组: "+str(a))
for i in range(len(a)):
for j in range(len(a)-1):
if a[j]>a[j+1]:
tmp = a[j]
a[j] = a[j+1]
a[j+1]=tmp
print("i = "+str(i)+" j = "+str(j)+": "+str(a)+"; ("+str(a[j+1])+">"+str(a[j])+", 所以"+str(a[j])+" 和 "+str(a[j+1])+"交换位置)")
else:
print("i = "+str(i)+" j = "+str(j)+": "+str(a)+"; ("+str(a[j])+"<"+str(a[j+1])+", 所以"+str(a[j])+" 不和 "+str(a[j+1])+"交换位置)")
/*
冒泡排序算法的运作如下：
1、比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。冒泡排序的代码如下：
*/
#include <stdio.h>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void Swap(int A[], int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
void BubbleSort(int A[], int n)
{
int i,j;
for ( j = 0; j < n - 1; j++) // 每次最大元素就像气泡一样"浮"到数组的最后
{
for ( i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移
{
if (A[i] > A[i + 1]) // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
{
Swap(A, i, i + 1);
}
}
}
}
int main()
{
int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; // 从小到大冒泡排序
int n = sizeof(A) / sizeof(int);
BubbleSort(A, n);
printf("冒泡排序结果：");
int i;
for ( i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
return 0;
}
/*