社区首页 >专栏 >冒泡排序和简单选择排序的算法实现及优化

冒泡排序和简单选择排序的算法实现及优化

lexingsen

发布于 2022-02-24 07:32:22

36200

代码可运行

文章被收录于专栏：乐行僧的博客乐行僧的博客

运行总次数：0

代码可运行

一.在排序算法中使用到的结构与函数

int arr[] = {50,60,90,10,30,40,20,70,80};
int len = sizeof(arr)/sizeof(arr[0]);
//由于数组作为形参会退化为指针，所以在函数中计算不出数组的长度。
//因此数组的长度应在主函数中求出，并传入到函数当中以便使用。
函数

void swap(int *arr,int i,int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

二.冒泡排序

冒泡排序作为最基础的排序算法，其核心就是通过两两相邻的同类型数据进行比较，进行交换。一组数据经过一次比较之后，就可以最大或最小的元素放在尾部，现实生活中很形象的例子就是冒泡，其名称也因此而来。下面实现冒泡排序算法：

void BubbleSort(int *arr,int len)
{
    for(int i = 0;i < len - 1;++i)
    {
        for(int j = 0;j < len - 1 -i;++j)
        {
            if(arr[j] > arr[j+1])
            {
                swap(arr,j,j+1);
            }
        }
    }
}

上述的算法虽然可以成功的解决一组数据排列的问题，但是涉及到一个具体的算法时，我们就必须从两方面考虑其性能及空间复杂度和时间复杂度。

由于计算机硬件发展迅速，硬件价格也随之迅速降低。在实际使用算法时，往往通过牺牲空间复杂度来获取较低的时间复杂度，这样的做法其实也是合理的。

针对时间复杂度，对冒泡排序算法进行优化。

int arr[] = {11,22,33,44,55,66,77,88,99};
//要求对arr数组中的数字进行升序排序，可以发现，进过一趟比较。数组中的数字顺序已完成排序
//但是在算法中还依此进行了七趟没有必要的比较
第一趟 int arr[] = {11,22,33,44,55,66,77,88,99}; 
第二趟 int arr[] = {11,22,33,44,55,66,77,88,99}; 
第三趟 int arr[] = {11,22,33,44,55,66,77,88,99}; 
第四趟 int arr[] = {11,22,33,44,55,66,77,88,99}; 
第五趟 int arr[] = {11,22,33,44,55,66,77,88,99}; 
第六趟 int arr[] = {11,22,33,44,55,66,77,88,99}; 
第七趟 int arr[] = {11,22,33,44,55,66,77,88,99}; 
第八趟 int arr[] = {11,22,33,44,55,66,77,88,99};
//可见，这样的算法在时间复杂度上的浪费非常大

当然上述的例子，是非常极端的。但是在实际的排序问题中也不乏数据几个或多个相邻的数据已经有序，因此针对已经有序的序列，就不需要进行排序。减少浪费不必要的时间。

优化后的冒泡排序

void BubbleSort(int *arr,int len)
{
    bool flag;//设置标识位，用于判断相邻两数据之间是否有序
    for(int i = 0;i < len - 1;++i)
    {
        flag = true;//flag设置为flase,假设已经有序
        for(int j = 0;j < len - 1 - i;++j)
        {
            if(arr[j] > arr[j+1])
            {
                flag =  false;//进入此分支，证明无序
                swap(arr,j,j+1);
            }
        }
        if(flag == true)
        {
            break;//证明此时数组中数据已经完成排序
        }
    }
}

三.简单选择排序 思路：简单选择排序算法就是通过n-i次关键字间比较，从n-1-i个记录中选择出关键字最小的的，并和第i个（0≤i≤n-i）个记录进行交换。简单选择排序算法的实现

void SelectSort(int *arr,int len)
{
    for(int i = 0;i < len;++i)
    {
        for(j = i+1;j < len;++j)
        {
            if(arr[i] > arr[j])
            {
                swap(arr,i,j);
            }
        }
    }
}

但实际上上述已经实现的简单选择排序也不满足算法在时间复杂度上的要求，其实优化的目的与冒泡排序相同，都是避免出现在已经有序的序列中进行排序，所以其优化的思路与冒泡排序的优化方式一致。 优化的简单排序算法

void  SelectSort(int *arr,int len)
{
    bool flag;
    for(int i = 0;i < len;++i)
    {
        flag = true;
        for(int j = 0;j < len;++j)
        {
            if(arr[i] < arr[j])
            {
                flag = true;
                swap(arr,i,j);
            }
        }
        if(flag == true)
        {
            break;
        }
    }
}