首页 > 编程语言 >【基础算法】简单排序-冒泡排序

【基础算法】简单排序-冒泡排序

时间:2023-03-18 17:12:48浏览次数:56  
标签:elements algorithm nums int since 冒泡排序 算法 排序

【基础算法】简单排序-冒泡排序

Bubble Sort is the simplest sorting algorithm that works by repeatly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.

How does Bubble Sort Work?

Input: arr[]={5,1,4,2,8}

First Pass:

  • Bubble sort starts with very first two elements, comparing them to check which one is greater.
    • ( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
    • ( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ), Swap since 5 > 4.
    • ( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ), Swap since 5 > 2.
    • ( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ), Now, since these elements are already in order ( 8 > 5 ), algorithm does not swap them.

Second Pass:

  • Now, during second iteration it should look like this:
    • ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
    • ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
    • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
    • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Third Pass:

  • Now, the array is already sorted, but our algorithm does not know if it is completed.
  • The algorithm needs one whole pass without any swap to know it is sorted.
    • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
    • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
    • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
    • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Code:

#include <stdio.h>
#include <malloc.h>

int main() {
    setbuf(stdout, 0);
    int n = 0;
    printf("请输入数组长度:");
    scanf("%d", &n);
    int* nums = malloc(sizeof(int) * n);
    for(int i=0; i<n; i++) {
        scanf("%d", nums+i);
    }
    // Sorting
    int temp = 0;
    for(int i=0; i<n-1; i++) {
        for (int j=0; j<n-1-i; j++) {
            if (*(nums+j) > *(nums+j+1)) {
                temp = *(nums+j);
                *(nums+j) = *(nums+j+1);
                *(nums+j+1) = temp;
            }
        }
    }
    for(int i=0; i<n; i++) {
        printf("%d ", *(nums+i));
    }
    return 0;
}

标签:elements,algorithm,nums,int,since,冒泡排序,算法,排序
From: https://www.cnblogs.com/yangxuanzhi/p/17231219.html

相关文章

  • 常用排序算法
    1.冒泡排序冒泡排序:相邻的数两两比较,小的放前面,大的放后面。冒泡排序(BubbleSort)也是一种简单直观的排序算法。它重复的遍历过要排序的数列,一次比较相邻的两个元素,如果......
  • 希尔排序、快速排序、KMP算法
    希尔排序背景对N个样本进行排序,顺序为从小至大步骤第一步:对样本不断确定分组的间隔gap,确定分组次数X-》对应第一个循环第一次gap=N/2;第二次gap=gap/2;......
  • 排序组件的使用--OrderingFilter模块的使用
    1.排序组件(OrderingFilter)的用法:  2.响应结果的传参格式:ordering=字段名(不带‘-’是正序,带‘-’是倒序):  3.路由:  ......
  • Tarjan算法详解
    Tarjan算法介绍Tarjan算法是用于在有向图中求强连通分量的算法这里给出强连通分量的定义:有向图中一个最大的图,使这个图中每个两点都能够互相到达。这个最大的图称为强连......
  • 算法随想Day41【动态规划】| LC139-单词拆分
    LC139.单词拆分dp[i]含义:字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词遍历顺序:如题说,是拆分为一个或多个在字典中出现的单词,所以这是完......
  • 一个乱七八糟的冒泡排序
    Input:任意多组数据(保证最多只有5组)对于每组数据,有两行数第一行数n,代表接下来将有n个数第二行数有n个乱序数注意:冒泡排序的越界#include<iostream>usingnamespac......
  • 对n个整数冒泡排序
    对n个整数数进行冒泡排序步骤:首先需要一个整形数组来存放整数,然后输入n个数到数组中去然后对数组中的值两两比较,把最大(小)的放到最后去#include<stdio.h>#defineMAX......
  • c代码实现冒泡排序
    #define_CRT_SECURE_NO_WARNINGS#include<stdio.h>voidbubble_sort(intarr[],intsz){inti=0;for(i=0;i<sz-1;i++){intj=0;for(j=0;......
  • 层次聚类算法
    动动发财的小手,点个赞吧!层次聚类是一种构建聚类层次结构的聚类算法。该算法从分配给它们自己的集群的所有数据点开始。然后将两个最近的集群合并到同一个集群中。最后,当......
  • 漫画:什么是选择排序算法?
    选择排序是一种简单直观的算法,今天我们聊聊选择排序的思想,代码以及复杂度排序思想一天,小一尘和师傅下山去了,在集市中路经一个水果摊,只见水果摊上摆着色泽基本相同但大......