排序算法——冒泡排序

一、冒泡排序的思想

    

    冒泡排序的思想如下：

    依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个和第3个数，将小数放前，大数放后，如此继续，直到比较最后两个数，将小数放前，大数放后。至此，第一趟结束，将最大的数放在了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

二、C代码实现

    

#include "stdio.h"
/*
* 函数：swap(int *a,int *b)
* 功能：进行两个数的交换
*/
void swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
/*
* 函数：bubble_sort(int *array, int n)
* 功能：冒泡排序
* 参数：n为数组元素的个数
*/
void bubble_sort(int *array, int n) {

    int i = 0;
    int j = 0;

    for (i=0;i<n-1;i++) {

        for (j=0;j<n-1-i;j++) {
            if (array[j]>array[j+1]) {
                swap(&array[j], &array[j+1]);
            }
        }
    }
}
int main(int argc,char *argv[])
{
    int array[]={3,8,3,7,1,2,5,6,4,90};
    bubble_sort(array,10);
    for(int i=0;i<10;i++)
    {
        printf("%d ",array[i]);
    }
    printf("\n");
    return 0;
}

三、冒泡排序的时间复杂度

    

   复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。