冒泡排序的探究

冒泡排序

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

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

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 <stdio.h>
#include <math.h>
//#define bubble
#define N 14
void 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<arrLen;i++){
        printf("%d ",*(p+i));
    }

    return 0;
}

//-------------------------------------
//--- 选择排序
//--- 排序思想：从队头向队尾，直接找出每个位置的值。每进行一轮比较，能按从队头往队尾顺序，确定一个位置的值。
//-------------------------------------
void selectSort(int arr[], int index, int len)
{
    int i, j;
    int indexMark;                                //下标标记，用于定位要寻找的值
    for (i = index;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("
");
}

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