冒泡排序（C语言）

一.冒泡排序的原理

冒泡排序的原理是：从左到右，相邻元素进行比较，以升序为例，第1次遍历将最大的数沉底。经过n次遍历这组元素以升序排列

->第1次遍历，两个相邻的数比较大小，若左边的数大于右边的数，则两个元素交换位置，反之，继续向后比较，当第1次遍历结束之后该组元素最大的数就被移动到了末尾

->第2次遍历，除去第一次的最大数，将这组数据中最大的数放至末尾

->根据以上原理，直至将这组元素排至升序，循环结束

二.冒泡排序（Bubble Sort）的代码实现

#include <stdio.h>
void BubbleSort(int arr[], int sz)
{
    int i = 0, j = 0, flag = 0;
    //有sz个数据只需要排列sz-1次就可以完成升序
    for(i = 0; i < sz - 1; i++)
    {
        //每排序一次就有一个数不需要排列了，所以是：sz-i-1
        for(j = 0; j < sz - i - 1; j++)
        {
            if(arr[j] > arr[j + 1])
            {
               int temp = arr[j];
               arr[j] = arr[j+1];
               arr[j + 1] = temp;
               flag = 1;
            }
        }
        //如果flag的值改变就证明这数组是升序不需要排序
        if(!flag)
        {
           break;
        }
    }
}

int main()
{
    int arr[] = {5,6,4,3,8,9,7,2,10,1,};
    printf("没排序之前：");
    int sz = sizeof(arr)/sizeof(arr[0]);
    int i = 0;
    for(i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    BubbleSort(arr, sz);
    printf("排序之后：");
    for(i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

但是这种冒泡排序有一个弊端！它只能用来排序整型数据。

C语言给我们提供了一个库函数，可以排序任意类型的数据 qsort

三.qsort的用法

qsort是用快速排序的思想实现的一个排序函数

用到qsort函数我们需要那些参数

void qsort(void* base,
           size_t num,
           size_t width,
           int (*cmp)(const void* e1, const void* e2))

->1.你要排序的数据的起始位置

->2.待排列数据元素的个数

->3.待排列数据元素的大小(一个元素，单位：字节)

->4.函数指针 - 比较大小

知道了qsort函数的参数之后，我们现在来使用一下

用法1：

->测试整型排序

#include <stdio.h>

int cmp(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;     //升序
       //  *(int*)e2 - *(int*)e1;  降序
}

int main()    
{
    int arr[] = {5,6,4,3,8,9,7,2,10,1,};
    printf("没排序之前：");
    int sz = sizeof(arr)/sizeof(arr[0]);
    int i = 0;
    for(i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    qsort(arr, sz, sizeof(arr[0]), cmp);
    printf("排序之后：");
    for(i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

升序：

降序：

用法2：

->测试使用qsort来排序数据结构

使用结构体的整型成员排序

#include <stdio.h>

typedef struct Stu
{
    char name[20];
    int age;
}Stu;

int cmp_Stu_by_age(const void* e1, const void* e2)
{
    return ((Stu*)e1)->age - ((Stu*)e2)->age;; //升序
    //或者用成员运算符：(*(Stu*)e1).age - (*(Stu*)e2).age  都是升序，反过来就是降序
}

int main()
{
    Stu s[] = {{"zhangsan", 18},
               {"lisi", 25}, 
               {"wangwu", 20}, 
               {"xiaoliu", 19}};
    int sz = sizeof(arr) / sizeof(arr[0]);
    qsort(s, sz, sizeof(s[0]), cmp_Stu_by_age);
    int i = 0;
    for(i = 0; i < sz; i++)
    {
        printf("%s %d\n", s[i].name, s[i].age);
    }
    return 0;
}

使用结构体的字符数组成员排序

include <string.h>
int cmp_stu_by_name(const void* e1, const void* e2)
{
    return strcmp(((*Stu)e1)->name, ((*Stu)e2)->name);
}

我们来模仿一下万能快速排序这个函数

模块一

//测试不同类型
#inciude <stdio.h>
void test1()
{
//根据情况放入   
}

模块二

void BubbleSort(void* arr, int sz, int width, int (*cmp)(const void* e1, const void* e2) )
{
    int i = 0, j = 0, flag = 0;
    for(i = 0; i < sz - 1; i++)
    {
        for(j = 0; j < sz - i - 1; j++)
        {
            if(cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)
            {
               swap((char*)arr + j * width, (char*)arr + (j + 1) * width, width);
               flag = 1;
            }
        }
        if(!flag)
        {             
           break;
        }
    }
}

模块三

int cmpare(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
    //这里以整型数据为例，别的类型自己临时变换 
}

模块四

void swap(char* buf1, char* buf2, int width)
{
    int i = 0;
    for(i = 0; i < width; i++)
    {
        int temp = *buf1;
        *buf1 = *buf2;
        *buf2 = temp;
        buf1++;
        buf2++;
    }
}

我们用我们模拟的万能排序来试一下

以整型为例

include <stdio.h>
int cmpare(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
}

void swap(char* buf1, char* buf2, int width)
{
    int i = 0;
    for (i = 0; i < width; i++)
    {
        char temp = *buf1;
        *buf1 = *buf2;
        *buf2 = temp;
        buf1++;
        buf2++;
    }
}

void BubbleSort(void* arr, int sz, int width, int (*cmp)(const void* e1, const void* e2))
{
    int i = 0, j = 0, flag = 0;
    for (i = 0; i < sz - 1; i++)
    {
        for (j = 0; j < sz - i - 1; j++)
        {
            if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)
            {
                swap((char*)arr + j * width, (char*)arr + (j + 1) * width, width);
                flag = 1;
            }
        }
        if (!flag)
        {
            break;
        }
    }
}

void test1()
{
    int arr[] = { 5,6,4,3,8,9,7,2,10,1, };
    printf("没排序之前：");
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    BubbleSort(arr, sz, sizeof(arr[0]), cmpare);
    printf("排序之后：");
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");  
}

int main()
{
    test1();
    return 0;
}

以上就是万能冒泡排序