冒泡排序
2017-11-07 本文已影响0人
Random_
基本思想：一种交换排序，两两比较相邻记录的关键字，如果反之则交换，直到没有反序的记录为止。
排序用到的结构与函数
#define MAXSIZE 10
typedef struct
{
int r[MAXSIZE+1]; /*r[0]用作临时变量或者哨兵
int length;
}SqList;
数组两个元素的交换函数
/*交换L中数组r下标为i和j的值*/
void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->[i]=L->r[j];
L->r[j]=temp;
}
冒泡排序初级版(不是标准的冒泡排序，知识最简单的交换)
void BubbleSort0(SeList *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);
}
}
}
}
正宗的冒泡排序
void BubbleSort(SqList *L)
{
int i,j;
for(i=1;i<L->length;i++)
{
for(j=L->length-1;j>=i;j--)
{
if(L->r[j]>r[j+1])
{
swap(L,j,j+1);
}
}
}
}
最小值放在了第1位置
冒泡排序最优化
假设有数组[2,1,3,4,5,6,7,8,9]，当i=1时就可以排好序，当i=2时就应该不再进行交换，提高算法的执行效率，设置flag避免不必要的交换
void BubbleSort(SqList *L)
{
int i,j;
int flag=1;
for(i=1;i<L->length&&flag;i++)
{
flag=0;
for(j=l->length-1;j>=i;j--)
{
if(L->r[j]>L->r[j+1])
{
swap(L,j,j+1);}
}
}
}
}
复杂度分析
最好情况下：排序本身有序的话，只需要进行n-1次的比较；
最坏情况下：待排序是逆序的话，需要n*(n-1)/2
因此，时间复杂度为 O（n2）
空间复杂度是 O（1)
稳定性
稳定排序
js代码
<!doctype html>
<html>
<head>
<title></title>
<script type="text/javascript">
function BubbleSort(arr){
var flag=1;
for (var i = 0; i < arr.length &&flag; i++)
{
for (var j=arr.length-1; j>= i; j--)
{
if(arr[j]>arr[j+1])
{
var temp;
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
flag=0;
}
}
}
return arr;
}
var array=[1,3,4,2,5,6];
BubbleSort(array);
document.write(array);
</script>
</head>
<body>
</body>
</html>
执行结果
在浏览器中的执行结果
