赞
踩
冒泡排序是一种很常见的简单排序。它依次扫描要排序的序列,比较两个相邻的元素,如果逆序就交换位置。
每次经过扫描一趟后,未排序部分最大的元素就“冒泡”到了最上面。
函数接口
void bubble_sort1(int *a, int low, int high)
接受的参数 数组的第一个元素地址 排序的区间 [low, high) 注意:前闭后开
思路
整个序列可以分成两个部分 左边的无序部分和右边的有序部分。
用last将两个部分隔开,无序部分为[low, last) 有序部分为[last, high)
最开始的情况下 另last=high-1 。将最后一个元素看作排好序的。只有一个元素的数组肯定是有序的。
接下来,在有序区间小于总区间的情况下(last > low)不断循环(外层循环)
(内层循环)从i = low开始 依次比较相邻的两个元素
a[i]和a[i+1] 然后i++ 。比较到什么时候结束呢?到了i=last的时候就可以结束了,这时候无序部分已经比较完了。
在这个过程中,设置了一个中间变量sorted 记录比较的时候最后一次交换时元素的下标 内层循环完成时,sorted以后的元素全部有序。
然后将last = sorted 进行下一次外循环。
代码
#include
#include
#include
#define N 1000
void bubble_sort1(int *a, int low, int high);
int main(void)
{
int i;
int a[N];
srand((int)time(NULL));
for (i = 0; i < N; ++i)
{
a[i] = rand() % 10000;
}
bubble_sort1(a, 0, N);
for (i = 0; i < N; ++i)
printf("%d ", a[i]);
printf("\n");
return 0;
}
void bubble_sort1(int *a, int low, int high)
{
int last = high - 1;
int tmp;
int sorted;
int i;
while (last > low)
{
i = low;
sorted = low;
while (i < last)
{
if (a[i] > a[i+1])
{
tmp = a[i+1];
a[i+1] = a[i];
a[i] = tmp;
sorted = i+1;
}
++i;
}
last = sorted;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include
#include
#include
#define N 1000
voidbubble_sort1(int*a,intlow,inthigh);
intmain(void)
{
inti;
inta[N];
srand((int)time(NULL));
for(i=0;i
{
a[i]=rand()%10000;
}
bubble_sort1(a,0,N);
for(i=0;i
printf("%d ",a[i]);
printf("\n");
return0;
}
voidbubble_sort1(int*a,intlow,inthigh)
{
intlast=high-1;
inttmp;
intsorted;
inti;
while(last>low)
{
i=low;
sorted=low;
while(i
{
if(a[i]>a[i+1])
{
tmp=a[i+1];
a[i+1]=a[i];
a[i]=tmp;
sorted=i+1;
}
++i;
}
last=sorted;
}
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。