基础算法之四–排序: 之冒泡排序

基础算法之四–排序: 之冒泡排序

冒泡排序,是所有排序中用的最多和最易想起的一种排序算法。

其排序思想: 对未排序的相邻元素进行两两比较,找出未排序元素中的最值,并将其置入应有位置。

算法特点:

1) 一次遍历,即可在未排序元素中,找到一个最值(最大值或最小值)

2) 当进行第i次遍历时(以第0次为出发点),说明已经遍历了i次,因此已经对i个元素排好了序。

3) 在未排序元素中寻找最值时,按由小到大次序寻找,可找到最大值

按由大到小次序寻找,可找到最小值

程序代码:

1)首先确定最小值

    // R[0...n-1] 为待排数组
    // 先确定最小值
    void BubbleSort(int R[],int n)
    {
        int i,j;
        int t; // 用于交换的临时变量
        BOOL bExchage;// 交换标志
        for (i=0;i<n-1;i++) // 最多做n-1趟排序
        {
            bExchage=FALSE;
            // 已经比较了i趟,因此,已经有i个有序   还有 n-i个无序 
            // 从大到小,最先确定的是最小值
            for (j=n-2;j>=i;j--)  // R[0...i-1] 有序  R[i...n-1]无序
            {
                if (R[j+1]<R[j])
                {
                    t=R[j+1];
                    R[j+1]=R[j];
                    R[j]=t;
                    bExchage=TRUE;
                }
            }
            if (!bExchage)  // 本趟未发生交换,则提前终止算法
                return;
        }
    }

2)首先确定最大值

 
    // R[0...n-1] 为待排数组
    // 先确定最大值
    void BubbleSort(int R[],int n)
    {
        int i,j;
        int t; // 用于交换的临时变量
        BOOL bExchage;// 交换标志
        for (i=0;i<n-1;i++) // 最多做n-1趟排序
        {
            bExchage=FALSE;
            // 已经比较了i趟,因此,已经有i个有序   还有 n-i个无序 
            // 从小到大,最先确定的是最大值
            for (j=0;j<=n-i-2;j++)  // R[0...n-(i+1)] 无序  R[n-i...n-1]有序
            {
                if (R[j+1]<R[j])
                {
                    t=R[j+1];
                    R[j+1]=R[j];
                    R[j]=t;
                    bExchage=TRUE;
                }
            }
            if (!bExchage)  // 本趟未发生交换,则提前终止算法
                return;
        }
    }

下面两个为参考程序:R[0]用作交换单元

1)

//R[0]暂存单元  R(1...n) 是待排序文件, 对R做冒泡排序

1) 先保存最小值

void BubbleSort(SeqList R)
{
    int i,j;
    BOOL bExchage;// 交换标志
    for (i=1;i<n;i++) // 最多做n-1趟排序
    {
        bExchage=FALSE;
        for (j=n-1;j>=i;j--)  //R[0]为暂存单元  R[1...i-1] 有序  R[i...n]无序
        {
            if (R[j+1].key<R[j].key)
            {
                R[0]=R[j+1];
                R[j+1]=R[j];
                R[j]=R[0];
                bExchage=TRUE;
            }
        }
        if (!bExchage)  // 本趟未发生交换,则提前终止算法
            return;
    }
}

2)

2) 先保存最大值

void BubbleSort(SeqList R)
{
    int i,j;
    BOOL bExchage;// 交换标志
    for (i=1;i<n;i++) // 最多做n-1趟排序
    {
        bExchage=FALSE;
        for (j=1;j<=n-i;j++)  //R[0]为暂存单元  R[1...n-(i-1)] 无序  R[n-(i-2)...n]有序
        {
            if (R[j+1].key<R[j].key)
            {
                R[0]=R[j+1];
                R[j+1]=R[j];
                R[j]=R[0];
                bExchage=TRUE;
            }
        }
        if (!bExchage)  // 本趟未发生交换,则提前终止算法
            return;
    }
}

如果此文对您有所帮助,还往点击一下以下网站:

360导航

2345导航