当前位置:  编程技术>c/c++/嵌入式

c语言实现冒泡排序、希尔排序等多种算法示例

    来源: 互联网  发布时间:2014-10-25

    本文导语:  实现以下排序插入排序O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 希尔排序 O(n^1.25) 1.插入排序 O(n^2) 一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:⒈ 从第一...

实现以下排序

插入排序O(n^2)

冒泡排序 O(n^2)

选择排序 O(n^2)

快速排序 O(n log n)

堆排序 O(n log n)

归并排序 O(n log n)

希尔排序 O(n^1.25)

1.插入排序 O(n^2)

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
⒈ 从第一个元素开始,该元素可以认为已经被排序
⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描
⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置
⒋ 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。

代码如下:

void insert_sort(int* array,unsignedint n){
    int i,j;
    int temp;
    for(i=1;i0&&*(array+j-1)>temp;j--){
            *(array+j)=*(array+j-1);
        }
        *(array+j)=temp;
    }
}

2.冒泡排序 O(n^2)

冒泡排序算法的运作如下:
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

代码如下:

#include
#defineSIZE8
void bublle_sort(int a[],int n){//n为数组a的元素个数
    int i,j,temp;
    for(j=0;j1){//确保数组长度至少为2,否则无需排序
         while(ii;j--)//从后向前搜索比val小的元素,找到后填到a[i]中并跳出循环
               if(a[j]= 0; --i)
        HeapAdjust(array, i, length);
    // 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
    for (int i = length - 1; i > 0; --i)
    {
        // 把第一个元素和当前的最后一个元素交换,
        // 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
      ///  Swap(&array[0], &array[i]);
          tmp = array[i];
          array[i] = array[0];
          array[0] = tmp;
        // 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
        HeapAdjust(array, 0, i);
    }
}

 6.归并排序 O(n log n)

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个    有序表合并成一个有序表,称为二路归并。

代码如下:

//归并操作
void Merge(int sourceArr[], int targetArr[], int startIndex, int midIndex, int endIndex)
{
    int i, j, k;
    for(i = midIndex+1, j = startIndex; startIndex

    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 2013年7月和2013年8月编程语言排行榜
  • 如何在GTK2.0下实现国际化(语言选择根据自己设置的语言,不用系统的语言)
  • 2017 年热门编程语言排行榜出炉,你的语言上榜没?
  • C语言中有指针,因此C语言可以创建链表,那么Java语言没有指针,那Java是否可以创建链表呢?
  • 苹果OS X和IOS下最新编程语言swift介绍
  • 求助,在linux下,c语言和汇编语言的接口是什么?
  • c语言判断某一年是否为闰年的各种实现程序代码
  • C语言中间语言 CIL
  • PHP编程语言介绍及安装测试方法
  • 最近学JSP,苦于HTML语言和JAVA语言太差,请教推荐几本书,thanks.
  • Linux下C语言strstr()查找子字符串位置函数详细介绍(strstr原型、实现及用法)
  • 我安装的linux时默认语言选择的是中文,又乱码,怎么可以解决?怎么更改默认语言成英文? iis7站长之家
  • c语言实现MD5算法完整代码示例
  • C语言如何改变当前语言环境
  • 以NetBeans IDE为例介绍如何使用XML中Schema语言
  • 如何在VIM中使汇编语言和C语言自动缩进?
  • c语言基于libpcap实现一个抓包程序过程
  • 我安装的linux时默认语言选择的是中文,又乱码,怎么可以解决?怎么更改默认语言成英文?
  • HTML超文本标记语言教程及实例
  • Redhat9安装时语言只选择了中文,现在还能再增加其它语言的支持吗?如英文
  • MD5算法的C语言实现
  • 请问哪里有ubuntu 9.0版本的中文语言包和KDE的中文语言包下载,我用Google搜索了很多地方都没有!




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3