精华内容
下载资源
问答
  • #include<stdio.h> #define MAXSIZE 10 ... printf("\n\n排序的结果为:\n"); for(i = 0; i < n; i ++ ) printf("%d ",arr[i]); printf("\n"); } //交换函数 void Swap(int *num_a, int *num_b) {
    #include<stdio.h>
      
    #define MAXSIZE 10
      
    //打印函数
    void Show(int arr[], int n)
    {
        int i;
        printf("\n\n排序的结果为:\n");
        for(i = 0; i < n; i ++ )
            printf("%d ",arr[i]);
        printf("\n");
    }
      
    //交换函数
    void Swap(int *num_a, int *num_b)
    {
        int temp = *num_b;
        *num_b = *num_a;
        *num_a = temp;
    }
      
    //双向起泡排序算法
    void BidBubbleSort(int array[], int n)
    {
        int low, high, flag, i;
        low = 0;
        high = n - 1;
        while(low < high)
        {
            flag = 0;
            for(i = low; i < high; i ++)  //正向冒泡
            {
                if(array[i] > array[i+1]) //找到剩下中最大的
                {
                    Swap(&array[i], &array[i+1]);
                    flag = 1;    //标志, 有数据交换
                }
            }
            if(!flag)
                break;
            high --;
            for(i = high; i > low; i --) //反向冒泡
            {
                if(array[i] < array[i-1])   //找到剩下中最小的
                    Swap(&array[i], &array[i-1]);
            }
            low++;
        }
    }
      
    int main()
    {
        int a[MAXSIZE] = {0};
        int n;
        printf("输入个数\n");
        scanf("%d",&n);
        printf("输入数组\n");
        for(int i = 0; i < n; i ++)
        {
            scanf("%d",&a[i]);
        }
        BidBubbleSort(a, n);
        Show(a, n);
        return 0;
    }
    
    
    展开全文
  • 本文实例为大家分享了C++实现双向冒泡排序算法的具体代码,供大家参考,具体内容如下一、概念(来源于百度百科)传统冒泡算法原理冒泡排序算法的运作如下:(从后往前)1.比较相邻的元素。如果第一个比第二个大,就交换...

    本文实例为大家分享了C++实现双向冒泡排序算法的具体代码,供大家参考,具体内容如下

    一、概念(来源于百度百科)

    传统冒泡算法原理

    冒泡排序算法的运作如下:(从后往前)

    1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。

    2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

    3.针对所有的元素重复以上的步骤,除了最后一个。

    4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    双向冒泡算法原理

    双向冒泡排序算法的运作如下:

    1.传统冒泡气泡排序的双向进行,先让气泡排序由左向右进行,再来让气泡排序由右往左进行,如此完成一次排序的动作

    2.使用left与right两个旗标来记录左右两端已排序的元素位置。

    一个排序的例子如下所示:

    排序前:45 19 77 81 13 28 18 19 77 11

    往右排序:19 45 77 13 28 18 19 77 11 [81]

    向左排序:[11] 19 45 77 13 28 18 19 77 [81]

    往右排序:[11] 19 45 13 28 18 19 [77 77 81]

    向左排序:[11 13] 19 45 18 28 19 [77 77 81]

    往右排序:[11 13] 19 18 28 19 [45 77 77 81]

    向左排序:[11 13 18] 19 19 28 [45 77 77 81]

    往右排序:[11 13 18] 19 19 [28 45 77 77 81]

    向左排序:[11 13 18 19 19] [28 45 77 77 81]

    如上所示,括号中表示左右两边已排序完成的部份,当left >= right时,则排序完成。

    二、实现程序:

    #include

    #include

    const int MAX = 30;

    // 交换两个数

    void Swap(int &x, int &y) {

    int temp;

    temp = x;

    x = y;

    y = temp;

    }

    // 双向冒泡排序

    void twoBubbleSort(int arr[], int len) {

    int left, right, shift, i; // shift为记录左右两端已排序的元素位置

    left = 0;

    right = len - 1;

    shift = 1;

    while(left < right) { // 往右排序

    for(i = left; i < right; i++) {

    if(arr[i] > arr[i+1]) { // 第一个数比第二个数大,交换

    Swap(arr[i], arr[i+1]);

    shift = i;

    }

    }

    right = shift;

    for(i = right-1; i >= left; i--) { // 向左排序

    if(arr[i] > arr[i+1]) { // 第一个数比第二个数大,交换

    Swap(arr[i], arr[i+1]);

    shift = i + 1;

    }

    }

    left = shift;

    }

    }

    int main(int argc, const char * argv[]) {

    // insert code here...

    int arr[MAX], i;

    srand((int)time(NULL)); // 设置时间为随机点

    std::cout << "排序前:";

    for(i = 0; i < MAX; i++) {

    arr[i] = rand() % 100;

    std::cout << arr[i] << " ";

    }

    // 调用双向冒泡排序函数

    twoBubbleSort(arr, MAX);

    std::cout << "\n排序后:";

    for(i = 0; i < MAX; i++)

    std::cout << arr[i] << " ";

    std::cout << std::endl;

    return 0;

    }

    运行结果:

    a06127aead62312cefefe90a55587d82.png

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

    展开全文
  • 个人原创总结的常用排序算法C语言示例代码解说PDF,可以动态输出排序过程,以便理解排序算法的主旨思想。包含有直接插入排序,折半插入排序,2路直接插入排序,起泡排序,简单选择排序,快速排序,堆排序,(希尔排序,归并...
  • 一些常用的排序算法C语言描述 包括起泡排序,shell排序,快速排序,直接插入排序,折半插入排序,简单选择排序的C语言实现以及代码讲解,改进与分析

    一些常用的排序算法C语言描述:

    1. 冒泡排序
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define type int 
    void printarr(type a[],int n)
    {
        for(int i=0;i<n;i++)
        printf("%d ",a[i]);
        printf("\n");
    }
    void bubblesort(type arr[],type n)
    {
        int flag=1;
        for(int i=n-1;i>=1&&flag;i--)
        {   
            flag=0;                 //也可以令i从0递增到n-1,则j从0到n-1-i 
             for( int j=0;j<i;j++)//也可以令i从1递增到n,则j从0到n-i 
              if(arr[j]>arr[j+1]) //逆序则为<号 每次将小的朝后放 
                {
                arr[j]=arr[j]+arr[j+1];//交换 
                arr[j+1]=arr[j]-arr[j+1];
                arr[j]=arr[j]-arr[j+1];
                flag=1; 
               }
                printarr(arr,12);
     }
      }
    • 此为向后起泡,也可以改为向前起泡,代码如下:
        for(int i=1;i<=n-1&&flag;i++)
           for(int j=n-1;j>=i;j--)
              if(a[j-1]>a[j]) //逆序则为<号 每次将大的朝前放,同样也可以加上flag标志判断是否有序 
              swap(a[j],a[j-1]);
    • 不管是从前向后还是从后向前起泡,相等时不进行交换起泡排序该算法稳定
    • 最好的情况即完全有序外层循环一次内层循环n-2次
    • 最坏情况即完全逆序,外层循环n-1次内层循环n-i次 共n(n-1)/2次

    2.选择排序

    void selectsort(type arr[],type n)
    {
        int m=0;
        for(int i=0;i<n-1;i++)//同样此处是选择最小的向相应位置交换,也可以从后向前将最大的与待交换点交换,不再赘述 
        {        int min=i;       
             for( int j=i+1;j<n;j++)
              if(arr[min]>arr[j]) 
                {
                    min=j;
               }
               if(min!=i)
               {           
                arr[i]=arr[i]+arr[min];//交换 
                arr[min]=arr[i]-arr[min];
                arr[i]=arr[i]-arr[min];
                printarr(arr,12);
             }
    }
      }
    • 选择排序该算法最坏最好也要进行(n-1)n/2次元素之间比较最小的交换次数为0,由于有三条交换语句,最大交换3(n-1)次
    • 由于每次拿最小的朝相应位置元素进行交换,若这个最小的在与相应位置相同的之后元素的后面则把相应位置上的元素交换到和他下一个相同元素的后面 ,所以不稳定

      3.直接插入排序

    void directinsertsort(int a[],int n)
    {
        int m=0; 
        for(int i=1;i<n;i++)
         {
            if(m++,a[i]<a[i-1])//若要实现逆序,则将所有<号 改为>号 
             {       
            int t=a[i];
            int j;
            for(j=i-1;j>=0&&m++,t<a[j];j--)//m用来计算元素之间的比较次数 
            a[j+1]=a[j];
             a[j+1]=t;
             printf(" m=%d ",m);
             printarr(a,12);
         }
    
         }
    
    }
    • 直接插入排序 这是把小的向前插,同样也可以把大的向后插即认定待插记录以后的都是有序的 代码如下:
       for(int i=n-2;i>=0;i--)
       if(a[i]>a[i+1])//若要实现逆序,则将所有>号 改为<   {
       t=a[i];
       for(int j=i+1;t>a[j]&&j<=n-1;t++)
       a[j-1]=a[j];
       a[j-1]=t;
       } 
    • 当序列正序时比较的次数为n-1次,不需要移动记录
    • 当序列逆序时比较次数 外层循环从1到n-1,内层循环比较i次再加if一次共i+1次,总比较(n+2)(n-1)/2次,此时所有交换语句为(n-1)(n+4)/2次
    • 由于插入位置是比它大的向后移动,与他相等的不移动,故稳定

    4.折半插入排序

     void bininsertsort(type a[],int n)
    {
        for(int i=1;i<n;i++)
           {
            int t=a[i];
            int low=0;
            int high=i-1;
           if(a[i]<a[i-1]) //若要逆序需要将两个if语句里改为大于号 
           {                
            while(low<=high)
               high=(low+high)/2-1;
             else 
               low=(low+high)/2+1; 
             for(int j=i-1;j>=low;j--)
               a[j+1]=a[j];
               a[low]=t;
               printarr(a,12);
           }
    }
    }
    • 折半插入排序,同样可以在后面进行折半插入,不再赘述
    • 平均比较次数log2(n-1)!而记录的比较次数不变T=O(n^2)
    • 对前面有序序列折半查找,找到应该插入的位置 必定使得区间逐步缩小,直至low和high相差1 此时t和low比较若t大low移动至high上去,否则high移动到low上去 使得high和low相等此时t再和此处比较,若t大意味着插入low+1处,low增加1后从low处后移,否则意味着 t插入low位置从low开始向后移动

    5.希尔排序

    void shellsort(int a[],int n) 
    {
        for(int d=n/2;d>=1;d/=2)//步长递减 
        {   
        for(int j=0;j<d;j++)//对划分出来的d个子序列进行直接插入排序 
        for(int i=j+d;i<=n-1;i+=d)//默认每个子序列第一个元素有序,从第二个元素(j+d)开始选择位置插入 
         {
            if(a[i]<a[i-d])//若要实现逆序,则将所有<号 改为>号 子序列里要插入的元素先和上一个元素进行比较,顺序则不插入 
             {       
            int t=a[i];
            int k;
            for(k=i-d;k>=0&&t<a[k];k-=d)//子序列里依次朝前比较,若要插入的小于正在比较的,则将此元素后在子序列里移一位,
            a[k+d]=a[k];                //即在 数组k+d位置 
            a[k+d]=t;
             }  
             printarr(a,13);
         }
    
    }
    }
    • 此为希尔排序,时间复杂度的计算在数学上未解决,不过增量除三可达到O(n^1.5)
    • 若相同元素未划分进如同一个子序列,会使相对位置发生改变故不稳定

    5.快速排序

    //以a[low]为轴,将大于其的放在右边,对小于的放在左边a[low]放在中间 
    type onequicksort(type a[],type low,type high)
    {
        type tem=a[low];
        while(low<high)
        {
            while(low<high&&a[high]>=tem) --high;
              a[low]=a[high];
           while(low<high&&a[low]<tem) ++low;
              a[high]=a[low];
        }
         a[low]=tem;
         printarr(a,13);
        return low;
    }
    //将划分的两个子区间都进行快速排序 
    void quicksort(type a[],type low,type high)
    {
        type pos;
        if(low<high){
       pos=onequicksort(a,low,high-1);//获得分割点 
       quicksort(a,low,pos-1);
       quicksort(a,pos+1,high-1);
    }
    }
    • 快速排序最坏即正序或逆序情况,时间复杂度O(n^2)
      可以证明一般情况下T=O(nlog2n)

    6.二路归并排序

    void mergesort(type a[],type arr[],int left,int right)
    {
        int mid;
        if(left<right)
        {
            mid=(left+right)/2;
            mergesort(a,arr,left,mid) ;
            mergesort(a,arr,mid+1,right);
            merge(a,arr,left,right,mid);
        }
         printarr(arr,13);
    }
    • 此为归并排序,总共要n个辅助空间,故空间复杂度为O(n)
    • 时间复杂度,划分序列的时间为常数可以忽略不计,一趟归并算法的时间复杂度为O(n)共需进行log2(n)次归并,所以总的时间复杂度为·O(nlog2(n))

      7.测试程序

     int main(void)
     {
        type arr[]={2,4,2,7,9,7,5,3,2,2,12,1,-9};
        printarr(arr,13);
     // bubblesort(arr,13);
     // selectsort(arr,13);
     //directinsertsort(arr,13);
     //bininsertsort(arr,13);
     //shellsort(arr,13);
     quicksort(arr,0,13);
     }
    
    展开全文
  • 起泡排序,别名“冒泡排序”,该算法的核心思想是将无序表中的所有记录,通过两两比较关键字,得出升序序列或者降序序列。 例如,对无序表{49,38,65,97,76,13,27,49}进行升序排序的具体实现过程如图1 所示: ...

    起泡排序,别名“冒泡排序”,该算法的核心思想是将无序表中的所有记录,通过两两比较关键字,得出升序序列或者降序序列。

    例如,对无序表{49,38,65,97,76,13,27,49}进行升序排序的具体实现过程如 1 所示:

                                                                            图 1 第一次起泡


    如图 1 所示是对无序表的第一次起泡排序,最终将无序表中的最大值 97 找到并存储在表的最后一个位置。具体实现过程为:

    1. 首先 49 和 38 比较,由于 38<49,所以两者交换位置,即从(1)到(2)的转变;
    2. 然后继续下标为 1 的同下标为 2 的进行比较,由于 49<65,所以不移动位置,(3)中 65 同 97 比较得知,两者也不需要移动位置;
    3. 直至(4),97 同 76 进行比较,76<97,两者交换位置,如(5)所示;
    4. 同样 97>13(5)、97>27(6)、97>49(7),所以经过一次冒泡排序,最终在无序表中找到一个最大值 97,第一次冒泡结束;

    由于 97 已经判断为最大值,所以第二次冒泡排序时就需要找出除 97 之外的无序表中的最大值,比较过程和第一次完全相同。


    经过第二次冒泡,最终找到了除 97 之外的又一个最大值 76,比较过程完全一样,这里不再描述。

    通过一趟趟的比较,一个个的“最大值”被找到并移动到相应位置,直到检测到表中数据已经有序,或者比较次数等同于表中含有记录的个数,排序结束,这就是起泡排序。

    起泡排序的具体实现代码为:

    #include <stdio.h>
    //交换 a 和 b 的位置的函数
    void swap(int *a, int *b);
    int main()
    {
        int array[8] = {49,38,65,97,76,13,27,49};
        int i, j;
        int key;
        //有多少记录,就需要多少次冒泡,当比较过程,所有记录都按照升序排列时,排序结束
        for (i = 0; i < 8; i++){
            key=0;//每次开始冒泡前,初始化 key 值为 0
            //每次起泡从下标为 0 开始,到 8-i 结束
            for (j = 0; j+1<8-i; j++){
                if (array[j] > array[j+1]){
                    key=1;
                    swap(&array[j], &array[j+1]);
                }
            }
            //如果 key 值为 0,表明表中记录排序完成
            if (key==0) {
                break;
            }
        }
        for (i = 0; i < 8; i++){
            printf("%d ", array[i]);
        }
        return 0;
    }
    void swap(int *a, int *b){
        int temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }

    运行结果为:

    13 27 38 49 49 65 76 97

    总结

    使用起泡排序算法,其时间复杂度同实际表中数据的无序程度有关。若表中记录本身为正序存放,则整个排序过程只需进行 n-1(n 为表中记录的个数)次比较,且不需要移动记录;若表中记录为逆序存放(最坏的情况),则需要 n-1 趟排序,进行 n(n-1)/2 次比较和数据的移动。所以该算法的时间复杂度为 O(n^{2})

    数据结构教程已经过作者多次打磨和润色,现已初具规模。教程分为入门教程(免费)和高级课程(收费),有想深入学习数据结构,购买高级课程的读者,可联系作者(QQ:834937624(备注信息:购买教程)),或登录数据结构网站获取。

    展开全文
  • 排序算法C语言实现

    2013-05-02 13:55:34
    排序算法,包括典型的排序,起泡法、快速排序、选择排序等等
  • 冒泡排序算法C语言

    2020-12-23 16:53:49
    冒泡排序算法C语言版 1、算法思想 冒泡排序就是将大的元素往后移动,类似排队排成一列,从前往后进行n轮遍历,每次从最前面的人开始,将他和他身后的人比较,高的站后面。然后第二个人和第三个人继续比较,高的站...
  • nbsp数据结构与算法数据结构(C语言)_各种排序算法性能比较.doc36页本文档一共被下载:次,您可全文免费在线阅读后下载本文档。 下载提示1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的...
  • 起泡排序算法When working with large databases, it is necessary to add the functionality to search for values or find the highest or lowest values from a range of items. The Bubble Sort Algorithm is an...
  • 下面哪种排序方法是从未排序序列中依次取出元素,与已排序序列中的元素作比较,将其放入已排序序列的正确位置上。(插入排序 )对序列15, 9, 7, 8, 20, -1, 4进行排序,若经一趟排序后的排列为9, 15, 7, 8, 20, -1, 4...
  • 排序算法c语言描述---双向冒泡排序

    万次阅读 多人点赞 2013-08-14 19:13:15
    排序算法系列学习,主要描述冒泡排序,选择排序,直接插入排序,希尔排序,堆排序,归并排序,快速排序等排序进行分析。 文章规划: 一。通过自己对排序算法本身的理解,对每个方法写个小测试程序。 具体思路分析...
  • 排序算法系列学习,主要描述冒泡排序,选择排序,直接插入排序,希尔排序,堆排序,归并排序,快速排序等排序进行分析。 文章规划: 一。通过自己对排序算法本身的理解,对每个方法写个小测试程序。 具体思路...
  • 代码学习过程中总结一下起泡排序法。起泡排序法的基本思路:每次将相邻的两个数进行比较,将小的调到前头。若有6个数:9,8,5,4,2,0第一次先将最前面的两个数8和9对调,第二次将第二个和第三个数(9和5对调)……...
  • c语言排序算法,其中包含插入排序,起泡排序,快速排序,选择排序
  • 排序算法起泡排序

    2020-03-24 11:15:29
    起泡排序 题目描述 起泡排序属于交换排序的一种,排序过程中小的元素不断“上浮”(交换到数组前面位置),就如同水里的气泡逐步冒出水面一样,故称为“起泡法”或“冒泡法”。给出一组数据,根据由小到大顺序输出。...
  • 最近看数据结构,把常用的排序算法C语言写了一下。 没有按数据结构上的定义SqList结构体,只是用数组的形式实现。 有的算法并没有完全按书上给出的算法,但思路一致。 #include void InsertSort(int[], int); /...
  • 冒泡排序算法整理 面试的时候问到二分查找的时候居然忘记最重要的步骤,先进行排序了,面试官也提醒了怎么还是没反应过来呢,所以还是好好理一下一些常用的排序算法,努力总是会有收获的,加油! 冒泡排序算法,以...
  • 冒泡排序算法-C语言实现及针对性优化详解

    千次阅读 多人点赞 2021-03-22 20:15:42
    提示:本文是为C语言排序算法小萌新科普,其他语言的朋友可以参考,大佬“非礼勿视”对于冒泡排序,我们应该对它的思想进行理解,作为排序算法学习的引导,让我们的思维更加开阔。 文章目录前言一、冒泡排序算法是...
  • 冒泡排序是一种相对简单的排序,它每次比较相邻的两个元素,如果前者大于后者,则交换< swap >这两个元素(从小到大排序),这样每一趟比较就把大的元素沉入最后,形象的称之为“冒泡”,每走一趟,实际上最尾...
  • 算法 c语言 冒泡排序改进

    千次阅读 2017-07-31 16:00:29
    #include #define N 8 void show(int a[]); void bubble(int a[]); int main() {  int a[N] = {50,36,66,76,95,12,25,36};  printf("原无序记录:\n");... printf("排序过程如下:\n");  bubble
  • C语言写的常见排序算法,包括直接选择排序、折半插入排序、起泡排序、快速排序、简单选择排序、归并排序等,已通过VC 6.0 测试。绝对实用。
  • 主要介绍了C语言 实现归并排序算法的相关资料,需要的朋友可以参考下
  • C语言排序算法

    2016-08-14 10:35:00
    C语言中三种常见排序算法分析 一、冒泡法(起泡法) 算法要求:用起泡法对10个整数按升序排序。 算法分析:如果有n个数,则要进行n-1趟比较。在第1趟比较中要进行n-1次相邻元素的两两比较,在第j趟比较中要进行n-...
  • #include void main() { int a, b, c, d; int x[9]; for (a = 1; a;a++) { scanf_s("%d", &x[a]); } for (b = 1; b; b++) { for (c = 0; c ; c++) { if (x[c+1] [c]) { d = x[c];...
  • 要求对以下6种常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。待排序表的表长不小于1000;其中的数据要用伪随机数产生程序产生,至少要用5组不同的输入数据作比较...
  • c语言排序算法的比较

    2011-08-19 10:13:58
    本程序对6种较为常见的排序算法进行实测比较。他们分别是:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序;2. 待排序表元素的关键字为整型。使用正序、逆序和不同程度的打乱获得不同的数据做...
  • 请教下C中对于数据多,处理效率较高的排序法及其实际如何编写,运用c语言排序法有选择法和冒泡法是最常见的。1冒泡法对10个数排序#include voidmain() {inta[10]; inti,j,t; printf("pleaseinput10numbers:\n");...
  • 写了一下排序算法,冒泡,选择,插入,思路写在注释里了,仅供参考。 #include<stdio.h> int a[10] = {1,48,12,16,13,19,34,24,26,36}; int b[10]; void bubble_sort(int a[],int n)//冒泡排序 { int temp; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 721
精华内容 288
关键字:

起泡排序算法c语言

c语言 订阅