冒泡排序(Bubble Sort)
冒泡排序是一种极其简单的排序算法,也是我所学的第一个排序算法。它重复地走访过要排序的元素,依次比较相邻两个元素,如果他们的顺序错误就把他们调换过来,直到没有元素再需要交换,排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下:
-
比较相邻的元素,如果前一个比后一个大,就把它们两个调换位置。
-
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
-
针对所有的元素重复以上的步骤,除了最后一个。
-
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
由于它的简洁,冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。冒泡排序的代码如下:
//单向冒泡排序(升序)
void BubbleSort1(int* arr,int value)
{
int i = 0;
int j = 0;
for (i=0;i<value;i++)
{
int flag = 0; //定义flag用来判断是否原来就是按照顺序排列的
for (j=value-1;j>=i;j--)
{
if (arr[j]<arr[j-1])
{
int tmp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = tmp;
flag = 1;
}
}
if(flag == 0)
break;
}
}
//指针实现单向冒泡排序(降序)
void BubbleSort2(int *arr,int sz)
{
int *start = arr;
int *end = arr+sz-1;
int *cur = NULL;
assert(arr!=NULL);
while (start<end)
{
cur = start;
while (cur<end)
{
if (*cur<*cur+1)
{
int tmp = *cur;
*cur = *cur+1;
*(cur+1) = tmp;
}
cur++;
}
end--;
}
}
//双向冒泡排序
void Swap( int *num_a, int *num_b )
{
int temp = *num_b;
*num_b = *num_a;
*num_a = temp;
}
void BubbleSort3(int array[], int n)
{
int low, high, flag, i;
low = 0;
high = n - 1;
while(low < high)
{
flag=0;
for(i=low; i<high; i++) //正向冒泡
{
if(array[i] > array[i+1]) //找到剩下中最大的
{
Swap(&array[i], &array[i+1]);
flag = 1; //标志, 有数据交换
}
}
if( !flag )
break;
high--;
for( i=high; i>low; i-- ) //反向冒泡
{
if(array[i] < array[i-1]) //找到剩下中最小的
Swap(&array[i], &array[i-1]);
}
low++;
}
}
下面我们测试一下:
int main()
{
int arr[] = {1,2,3,4,5,6,7,8,9};
int i = 0;
int sz = sizeof(arr)/sizeof(arr[0]);
printf("单向升序排序:\n");
BubbleSort1(arr,sz);
for (i=0;i<sz;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
printf("单向降序排序:\n");
BubbleSort2(arr,sz);
for (i=0;i<sz;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
printf("双向升序排序:\n");
BubbleSort3(arr,sz);
for (i=0;i<sz;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}
输出结果: