#include <stdio.h>
#define MAXSIZE 10 //用于要排序数组个数最大值,可根据需要修改
typedef struct{
int r[MAXSIZE+1]; //用于存储要排序数组,r[0]用作哨兵或临时变量
int length; //用于记录顺序表的长度
}SqList;
void swap(SqList *L, int i, int j) //交换L中数组r的下标为i和j的值
{
int temp = L->r[i];
L->r[i] = L->r[i];
L->r[i] = temp;
}
//1.冒泡排序初级版本对顺序表L作为交换排序
void BubbleSort0( SqList *L ) {
int i, j;
for( i = 1; i < L->length; i++ ){
for( j = i+1; j <= L->length; j++ ){
if(L->r[i] > L->r[j]){
swap(L,i,j)
}
}
}
}
//2.对顺序表L作冒泡排序 正宗的冒泡排序
void BubbleSort1( SqList *L ) {
int i, j;
for( i = 1; i < L->length; i++ ){
for( j = L->length-1;j>=i;j-- ){
if(L->r[j] > L->r[j+1]){
swap(L,j,j+1);
}
}
}
}
//3.冒泡算法的改进 冒泡排序的改进版本
void BubbleSort2( SqList *L ) {
int i, j;
bool flag = true;
for( i = 1; i < L->length && flag; i++ ){
flag = false;
for( j = L->length-1; j>=i; j--){
if(L->r[j] > L->r[j+1]){
swap(L,j,j+1);
flag = true;
}
}
}
}
//冒泡排序复杂的分析:
// 如果本身有序的话 进行了 n-1次比较, 没有数据交换复杂度为O(n)
// 最坏的清空问n*(n-1)/2 因此复杂度为O(n^2)