冒泡排序

冒泡不是冒泡，冒泡是沉底。

数组的首地址是低地址，末地址是高地址，可以理解为数据往高地址冒。

1、比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（小）的数。

从大到小排列：小数沉底

从小到大排列：大数沉底

3、针对所有的元素重复以上的步骤，除了最后已经选出的元素（有序）。

4、持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。

 

经过计算，若将数组切为两半分别进行冒泡排序，当两半数组长度相等时，数组排序所使用的比较次数最少，约为不切断时的一半。

下面进行数学计算：

设数组长度为n，将数组切为两半，一半长度为m，另一半长度为n-m。则

不切断比较次数为：n*(n-1)/2

切断比较次数为：f1(m)=(n-m)*(n-m-1)/2+m*(m-1)/2+n-1。其中n-1为将两个有序数组合并为一个长度为n的有序数组至多需要的比较次数，最少的次数为min(m, n-m)。

f1(m)在区间[0,n], m∈Z上为下凸函数，当m=n/2时，f1(m)取最小值。

对于赋值次数，我们假设最坏情况，每次比较都导致一次元素值交换，比如将1 2 3 4重新按冒泡法排序为4 3 2 1，就是这种最坏情况。

一次元素值交换至少导致3次值传递，如果你调用函数显然值传递次数不止3次，因为还包括参数值传递。合并操作会导致n-1次赋值操作。那么

不切断比较次数为：3*n*(n-1)/2

切断比较次数为：f2(m)=3*(n-m)*(n-m-1)/2+3*m*(m-1)/2+n-1

经计算，当m=n/2时，f2(m)取最小值，约为3*n*(n-1)/4，即约为切断赋值次数的一半。

 

代码实现如下：

#include 
     
      #include 
      
       //#define bubble#define N 14void bubbleSort(int *arr[], int index, int len);    //冒泡排序void selectSort(int head, int len);            　　　//选择排序void intSwap(int *a, int *b);                　　　　//交换两个元素的值void dispArr(int *arr[], int index, int len); 　　　 //显示数组元素int *conbine(int *a, int *c, int index1, int len1, int index2, int len2);//将两个有序数组结合int main(){    int a[N] = {
   1, 6, 4, 7, 21, 5, 5, 3, 29, 32, 43, 56, 53,88};    int c[N] = {
   0};    float arrLen    = N;                                //数组长度，之所以用浮点数，是为了ceil函数生效。或者也可用int声明，搭配if判断是否整除。    int        len    =    arrLen/2;            　　　//子数组长度    int subArrNum    =    ceil(arrLen / len);   　　　//子数组个数    int i;    int *p;//*****************************************************************************//*****************************************************************************// 原本想将数组切为n段，然后自动合并，但是只能做到将数组切段并排序，合并则极难做到，感觉根本不可行。//第一，数组的长度不能为变量，必须直接指定，效率低下。//第二，用链表将导致赋值次数增多，关键是需要自动创建并正确使用链表，做不到。//第三，难以用循环进行合并，参数不能统一表达。如第一轮合并产生10个合并数组，余下一个子数组，怎么合并？第二轮函数参数必然要改变，因为合并的不是子数组，而是合并后的数组。//第三轮怎么办？后面怎么控制，难度极高。无法处理。//只好退求其次，切为2段，然后用一个固定数组存储合并数组。//*****************************************************************************//***************************************************************************** //将数组切为元素个数为len的子数组    //余下的不足len长度的元素构成一个长度为arrLen - i*len数组，其中i = arrLen / len。    for (i = 0; i < subArrNum; i++){        if(arrLen - i * len < len){        #ifdef bubble            bubbleSort(a, 3, 3);        #else            selectSort(a, i*len, (int)arrLen - i*len);    //将arrLen强制转换为int型，传递给int型形参。        #endif            dispArr(a, i*len, arrLen - i*len);        }        else{            selectSort(a, i*len, len);            dispArr(a, i*len, len);        }    }    p = conbine(a, c, 0, len, len, arrLen - len);    //dispArr(p, 0, arrLen);    for(i=0;i
       
        < (index + len -1); i++){    //控制每一趟起始位置,终止位置在倒数第二个元素        indexMark = i;        for (j = i + 1; j < (index + len); j++){
   //控制第二个比较数的起始位置            if (arr[indexMark] < arr[j])        //寻找最大元素下标                indexMark = j;        }        if (indexMark != i)            intSwap(&(arr[i]), &(arr[indexMark]));    } }//-------------------------------------//--- 冒泡排序//--- 排序思想：依据排序顺序，比较相邻两个元素的值。每进行一轮比较，能按从队尾往队头顺序，确定一个位置的值。//-------------------------------------void bubbleSort(int arr[], int index, int len){    int i, j;    for (i = 1; i < len; i++){                            //控制比较趟数，len个元素比较 len-1 趟        for (j = index; j < (index + len - i); j++){    //控制比较终止位置            if (arr[j] < arr[j + 1])                intSwap(&(arr[j]), &(arr[j+1]));        //传址调用        }    }}//-------------------------------------//--- 两个int类型数据交换//-------------------------------------void intSwap(int *a, int *b) {    int        temp;    temp    = *a;                                        //通过 * 访问变量，而不是取地址符 &     *a        = *b;    *b        = temp;}//-------------------------------------//--- 显示数组所有元素//-------------------------------------void dispArr(int arr[], int index, int len){    int i;    for (i = index; i < (index + len); i++)        printf("%-3d ",arr[i]);    printf("\n");}int *conbine(int *a, int *c, int index1, int len1, int index2, int len2){    int i = 0;    int combLen = len1 + len2;//合并后长度    while(index1 < len1 && index2 < combLen){        if(a[index1] > a[index2]){            c[i] = a[index1];            index1 += 1;            i++;        }        else{            c[i] = a[index2];            index2 += 1;            i++;        }    }    while(index1 < len1){        c[i] 　　= 　a[index1];        index1 += 　　　　　　1;        i++;    }    while(index2 < combLen){        c[i]　　= 　　a[index2];        index2 += 　　　　　　 1;        i++;    }    return c;}
       
      
     

 

请使用手机"扫一扫"x