算法-冒泡算法三种实现方法-C语言

[TOC]

1.特点与适用场合

• 特点
  • 优点
    • 简单
    • 空间复杂度低
    • 稳定
  • 缺点
    • 时间复杂度太高
    • 效率不好
• 适用数据规模较小的场合

2.过程简述

1. 有大小为N的数组 int arr[N]，并要求从小到大排序。
2. 比较相邻的前后二个数，若前面数大于后面的数，则互换。
3. 这样对数组进行遍历，最后最大的那个数就“沉”到数组的最后一个位置，即a[N-1]。
4. N=N-1，一直重复以上操作，直到N为0为止。

3.代码

3.1基础冒泡排序

void BubbleSort_base(int n,int arr[])  
{  
       int i, j;  
       for (i = 0; i < n; i++)  
              for (j = 1; j < n - i; j++)  
                     if (arr[j - 1] > arr[j]){
                        //交换数据
                        int temp=arr[j - 1];
                        arr[j - 1]=arr[j];
                        arr[j]=temp;
                       }  
}

3.2第一次优化算法——设立标志

设置一个标志 bool flag=true; 还是循环遍历，从 arr[0] 到 arr[n-1] ，当其中一次遍历没有发生交换，就把flag设置为false，然后结束循环，排序已经完成。（显然没有发生交换即代表排序完成）

void BubbleSort_flag(int n,int arr[])  
{  
       int j, k;  
       bool flag;  
  
       k = n;  
       flag = true;  
       while (flag)  
       {  
              flag = false;  
              for (j = 1; j < k; j++)  
                     if (arr[j - 1] > arr[j])  
                     {  
                        //交换数据
                        int temp=arr[j - 1];
                        arr[j - 1]=arr[j];
                        arr[j]=temp;
                        //改变flag为true，以使循环继续执行
                         flag = true;  
                     }  
              k--;  //因为每经过一趟排序，尾部就有一个数一定是被排好的
       }  
}  

3.3第一次优化算法——设立变量 int index 指定每趟需要遍历到的位置。

如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。

void BubbleSort_index(int n,int arr[])  
{  
    int j, k;  
    int index;  
      
    index = n;  
    while (index > 0)  
    {  //显然当index=0时，就说明排序完成
        k = index;  
        index= 0;  
        for (j = 1; j < k; j++)  
            if (arr[j - 1] > arr[j])  
            {  
                //交换数据
                int temp=arr[j - 1];
                arr[j - 1]=arr[j];
                arr[j]=temp;
                index = j;  
            }  
    }  
}