Bubble Sort冒泡排序C语言实现

#Bubble Sort

此贴特意为戴维营教育零基础学员课外学习之用.

这是一种排序算法,他就是相邻的两个元素两两比较,如果顺序不对就互相交换位置,比较一直往后重复,直到不需要交换为止,也就是已经排好序. 那个比较小的元素"像气泡一样往上冒泡"到最顶端,因此而得名冒泡排序.

###算法

从待排列表的第一个元素开始,一直比较和交换相邻的两个元素直到列表被排好序

  • 比较相邻的两个元素,并检查他们是否是正确的序号(第二个应该比第一个要大).
  • 如果他们的顺序不正确,那么交换他们的位置,使其第二个比第一个大.

让一个整型变量int iter;来表示循环的次数,那么iter的取值范围就是从1到n-1这样一个整型区间,n是待排序列表的元素的个数.
判断

  1. 如果在循环变量iter的位置,第二个元素的值小于第一个元素的值(iter-1位置),那么就交换他们的位置.
  2. 否则,比较的位置移动到下一个元素的地方:iter+1的位置.
    这样,待排序列表的有效大小就会在每次遍历中把最大的元素移动到有序子列表里最终的位置后减少一. 一直重复上面2个步骤知道列表被全部排好序,不需要任何元素交换. 如:有效大小缩减至1.

###特性

  1. 最佳性能:当列表是有序的,那么我们只需遍历一下.因此时间复杂度是 O(n).
  2. 最差性能:当列表是倒序的,那么我们需要遍历N次,每次要N次比较和交换,因此时间复杂度是 O(n2)
  3. 平均性能:时间复杂度是: O(n2)
  4. 这个不需要任意额外的临时变量空间,因此空间复杂度是 O(1)

###冒泡排序-C语言代码

#include <stdio.h>

/*
Logic steps : Do the following thing until the list is sorted
(i) Compare two adjacent elements and check if they are in correct order(that is second one has to be greater than the first).
(ii) Swap them if they are not in correct order.
 */

void BubbleSort(int *array,int number_of_elements)
{
        int iter, temp, swapped;
        do
        {
                swapped = 0; /* If no element is swapped array is sorted */
                /* In the following loop compare every pair of adjacent elements and check if they are in correct order */
                for(iter = 1; iter < number_of_elements; iter++)
                {
                        if(array[iter-1] > array[iter])
                        {
                                temp = array[iter-1];
                                array[iter-1] = array[iter];
                                array[iter] = temp;
                                swapped = 1;
                        }
                }

        }while(swapped);
}
int main(void)
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        BubbleSort(array,number_of_elements); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;

}

标签:none

添加新评论