冒泡排序算法
时间复杂度: O(n²)
稳定性: 稳定排序算法(即排序前两个相同元素的相对位置在排序后不会改变)
算法
void BUBBLESORT(int a[],int n)
{
int i, j, tmp;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - 1 - i; j++)
{
if(a[j] > a[j + 1])
{
tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
冒泡排序算法复杂度分析
若数组初始是升序的,一趟扫描即可完成,并不交换元素。冒泡排序最好的时间复杂度为 O(n)
若初始文件是降序的,需要进行n-1趟遍历,每趟排序要进行n-i次关键字的比较。冒泡排序的最差时间复杂度为O(n^2)。
冒泡排序算法测试
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>
#include<time.h>
#define MAX 101
void BUBBLESORT(int a[],int n)
{
int i, j, tmp;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - 1 - i; j++)
{
if(a[j] > a[j + 1])
{
tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
void main ()
{
int i;
int a[MAX];
memset(a,0x00,sizeof(int)*MAX);
srand((unsigned)time(NULL));
for (i = 0; i < MAX; i++)
{
a[i] =rand()%100;
printf("%d\t",a[i]);
}
printf("\n");
BUBBLESORT(a,MAX);
for (i = 0; i < MAX; i++)
{
printf("%d\t",a[i]);
}
printf("\n");
}
## 测试结果