技术笔试面试

起泡排序-也叫冒泡排序

起泡排序算法,是一种借助“交换”进行排序的方法,英文名叫Bubble Sort。

起泡排序的过程其实很简单。首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序(即r[1]>r[2]),则将两记录交换之,然后比较第二个记录和第三个记录,以此类推,直到第n-1个记录和第n个记录的关键字进行过比较为止。这个过程称作“第一趟起泡排序”,其结果是使得关键字最大的记录被安置到最后一个记录的位置上。类似的,可以对前n-1, n-2, … 2进行起泡排序,最终即可得到有序序列。

一个小技巧就是,判别起泡排序结束的条件应该是“在一趟排序过程中没有进行过交换记录的操作”。

起泡排序源代码如下:

#include
#include

void bubble_sort(int *arr,int arrsize)
{
        int i,j,tmp;
        char flag;
        for(i=arrsize-1;i>=1;i--){
                flag=0;
                for(j=1;j<=i;j++){
                        if(arr[j]>arr[j+1]){
                                tmp=arr[j];
                                arr[j]=arr[j+1];
                                arr[j+1]=tmp;
                                flag=1;
                        }
                }
                if(flag==0)
                        return;
        }
}

int main(int argc,char *argv[])
{
        printf("Quick Sort:\n");
        int arr[10]={0,4,2,5,1,8,7,9};
        int arrsize=7;
        bubble_sort(arr,arrsize);
        int i;
        printf("Sorted array: ");
        for(i=1;i<=arrsize;i++){
                printf("%d ",arr[i]);
        }
        printf("\n");
        return 0;
}

发表您的评论

请您放心,您的信息会被严格保密。必填项已标识 *