`
- 浏览:
113435 次
- 性别:
- 来自:
西安
-
- 内部排序算法的C/C++实现
- 排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重;并且排序本身对推动算法分析的发展也起很大作用。目前已有上百种排序方法,但尚未有一个最理想的尽如人意的方法,本文介绍常用的如下排序方法的C/C++实现,并对它们进行分析和比较。
- 更详细的算法思想的介绍可以参考这里
-
-
-
-
-
#include<iostream>
-
usingnamespacestd;
-
-
voidswap(int&a,int&b)
- {
-
inttmp;
- tmp=a;
- a=b;
- b=tmp;
- }
-
-
voiddisplay(intarray[],intlen)
- {
-
cout<<"theresultis:"<<endl;
-
for(inti=0;i<len;i++)
- {
-
cout<<array[i]<<"";
- }
- cout<<endl;
- }
-
-
-
voidbubble_sort(intarray[],intlen)
- {
-
for(inti=len-1;i>=0;i--)
- {
-
for(intj=0;j<i;j++)
-
if(array[j]>array[j+1])
- swap(array[j],array[j+1]);
- }
- }
-
-
-
voidinsert_sort(intarray[],intlen)
- {
-
inttmp,i,j;
-
for(i=1;i<len;i++)
- {
-
if(array[i]<array[i-1])
- {
- tmp=array[i];
- array[i]=array[i-1];
-
-
for(j=i-2;j>=0;j--)
- {
-
-
if(array[j]>tmp)
- array[j+1]=array[j];
-
else
- {
- array[j+1]=tmp;
-
break;
- }
- }
-
if(j==-1)
- array[j+1]=tmp;
- }
- }
- }
-
-
-
-
voidbi_insert_sort(intarray[],intlen)
- {
-
int*arr_d=(int*)malloc(sizeof(int)*len);
- arr_d[0]=array[0];
-
inthead=0,tail=0;
-
for(inti=1;i<len;i++)
- {
-
if(array[i]>arr_d[0])
- {
-
intj;
-
for(j=tail;j>0;j--)
- {
-
if(array[i]<arr_d[j])
- arr_d[j+1]=arr_d[j];
-
else
-
break;
- }
- arr_d[j+1]=array[i];
- tail+=1;
- }
-
else
- {
-
if(head==0)
- {
- arr_d[len-1]=array[i];
- head=len-1;
- }
-
else
- {
-
intj;
-
for(j=head;j<=len-1;j++)
- {
-
if(array[i]>arr_d[j])
- arr_d[j-1]=arr_d[j];
-
else
-
break;
- }
- arr_d[j-1]=array[i];
- head-=1;
- }
- }
- }
-
for(inti=0;i<len;i++)
- {
-
intpos=(i+head);
-
if(pos>=len)pos-=len;
- array[i]=arr_d[pos];
- }
- free(arr_d);
- }
-
-
-
-
voidshell_insert(intarray[],intd,intlen)
- {
-
inttmp,j;
-
for(inti=d;i<len;i++)
- {
-
if(array[i]<array[i-d])
- {
- tmp=array[i];
- j=i-d;
-
do
- {
- array[j+d]=array[j];
- j=j-d;
-
}while(j>=0&&tmp<array[j]);
- array[j+d]=tmp;
- }
- }
- }
-
voidshell_sort(intarray[],intlen)
- {
-
intinc=len;
-
do
- {
- inc=inc/2;
- shell_insert(array,inc,len);
-
}while(inc>1);
- }
-
-
-
-
intpartition(intarray[],intlow,inthigh)
- {
-
intpivotkey=array[low];
-
while(low<high)
- {
-
while(low<high&&array[high]>=pivotkey)
- --high;
- swap(array[low],array[high]);
-
while(low<high&&array[low]<=pivotkey)
- ++low;
- swap(array[low],array[high]);
- }
- array[low]=pivotkey;
-
returnlow;
- }
-
voidquick_sort(intarray[],intlow,inthigh)
- {
-
if(low<high)
- {
-
intpivotloc=partition(array,low,high);
- quick_sort(array,low,pivotloc-1);
- quick_sort(array,pivotloc+1,high);
- }
- }
-
-
-
-
intSelectMinKey(intarray[],intiPos,intlen)
- {
-
intret=0;
-
for(inti=iPos;i<len;i++)
- {
-
if(array[ret]>array[i])
- {
- ret=i;
- }
- }
-
returnret;
- }
-
voidselect_sort(intarray[],intlen)
- {
-
for(inti=0;i<len;i++)
- {
-
intj=SelectMinKey(array,i,len);
-
if(i!=j)
- {
- swap(array[i],array[j]);
- }
- }
- }
-
-
-
-
voidmerge(intarray[],inti,intm,intn)
- {
-
intj,k;
-
intiStart=i,iEnd=n;
-
intarrayDest[256];
-
for(j=m+1,k=i;i<=m&&j<=n;++k)
- {
-
if(array[i]<array[j])
- arrayDest[k]=array[i++];
-
else
- arrayDest[k]=array[j++];
- }
-
if(i<=m)
-
for(;k<=n;k++,i++)
- arrayDest[k]=array[i];
-
if(j<=n)
-
for(;k<=n;k++,j++)
- arrayDest[k]=array[j];
-
for(j=iStart;j<=iEnd;j++)
- array[j]=arrayDest[j];
- }
-
voidmerge_sort(intarray[],ints,intt)
- {
-
intm;
-
if(s<t)
- {
- m=(s+t)/2;
- merge_sort(array,s,m);
- merge_sort(array,m+1,t);
- merge(array,s,m,t);
- }
- }
-
-
-
-
voidheap_adjust(intarray[],inti,intlen)
- {
-
intrc=array[i];
-
for(intj=2*i;j<len;j*=2)
- {
-
if(j<len&&array[j]<array[j+1])j++;
-
if(rc>=array[j])break;
- array[i]=array[j];i=j;
- }
- array[i]=rc;
- }
-
voidheap_sort(intarray[],intlen)
- {
-
inti;
-
for(i=(len-1)/2;i>=0;i--)
- heap_adjust(array,i,len);
-
for(i=(len-1);i>0;i--)
- {
-
swap(array[0],array[i]);
- heap_adjust(array,0,i-1);
- }
- }
-
intmain(){
-
intarray[]={45,56,76,234,1,34,23,2,3,55,88,100};
-
intlen=sizeof(array)/sizeof(int);
-
-
-
-
-
-
-
-
heap_sort(array,len);
- display(array,len);
-
return0;
- }
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
五种内部排序算法性能比较, 1.直接插入排序算法。 2.简单选择排序。 3.希尔排序。 4.归并排序。5.快速排序。分别对交换次数,比较次数,移动次数,时长,时间复杂度进行性能比较。给出十万到百万级数据量的统计结果...
3、C/C++实现 31 4、对排序算法的总结 41 11、数组和链表的优缺点 42 12、C++操作符优先级: 43 13、B树、B-树、B+树、B*树、红黑树和trie树 44 14、最小生成树算法之Prim算法(C++实现) 49 15、最小生成树之kruskal...
(1)不调用C++/C 的字符串库函数,请编写函数 strcat 答: VC源码: char * __cdecl strcat (char * dst, const char * src) { char * cp = dst; while( *cp ) cp++; /* find end of dst */ while( *cp++ = *src++ ...
内部排序合集(插入、希尔、起泡、快速、选择、堆、归并和基数排序) 这是我在我们期末的时候写的一些内部排序的例子。因为我们的数据结构考试的范围就限定在内部排序上,所以我没有什么办法,只好对自己埋头苦干就...
概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则...
数据结构算法比较,经过C认证运行顺利,并附有实验报告,本人呕心沥血才弄出来的。
C语言课程设计-实训-计算机内部算法性能比较。通过随机数据比较各算法的关键字比较次数和关键字移动次数,以去得直观感受
B:写出下列算法的时间复杂度和实现排序: (1)冒泡排序; (2)选择排序; (3)插入排序; (4)快速排序; (5)堆排序; (6)归并排序; 23、编写gbk_strlen函数,计算含有汉字的字符串的长度,汉字作为一个字符处理;已知...
快速排序算法(C语言版) #include #include "type.h" #define Q_SIZE 10 /************************************* 模块内部数组或变量定义 **************************************/ static UINT8 q_array[Q_...
4.3 数据输入输出的概念及在 C 语言中的实现 54 4.4 字符数据的输入输出 54 4.4.1 putchar 函数(字符输出函数) 54 4.4.2 getchar函数(键盘输入函数) 55 4.5 格式输入与输出 55 4.5.1 printf 函数(格式输出函数...
排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则应...
4.3 数据输入输出的概念及在 C 语言中的实现 54 4.4 字符数据的输入输出 54 4.4.1 putchar 函数(字符输出函数) 54 4.4.2 getchar函数(键盘输入函数) 55 4.5 格式输入与输出 55 4.5.1 printf 函数(格式输出函数...
【STL源代码】中包含了许多常用的数据结构(如vector、list、map等)和算法(如排序、查找、遍历等)。通过阅读代码可以仔细研究这些数据结构和算法的实现,了解它们的内部工作原理和使用方式。
数据结构与算法_C语言 01.swap.mp4 02.BubbleSort.mp4 03.SelecttionSort.mp4 04.顺序查找.mp4 05.C_DS_折半查找.mp4 06.递归.mp4 07递归算法_折半查找.mp4 08.Permutations.mp4 09.插入排序.mp4 10.快速...
实验一 一元稀疏多项式的计算 实验二 长整数四则运算 实验四 算术表达式求值 实验七 哈夫曼编/译码器实验指导书 实验八 最短路径实验指导书 实验十 内部排序算法比较实验指导书
这是一个数据结构演示系统,具体语言可以选择C(C++)和Pascal语言。可以动态演示各种算法,有两个基本作用: 1、理解算法 2、验证算法结果 无论是对老师上课,还是学生自学,都有很大帮助。程序运行的每一步都以...
在编写程序之前,必须清楚地了解如何通过程序实现所要完成的任务。因此,在编写代码之前,应列出程序的提纲,...然而,诸如C+ +之类的面向对象语言(OOL)与抽象数据类型有着直接的联系,这种语言将OOL作为-个类来实现。
该程序以动画的形式向学习者展示各种算法的执行过程,帮助学习者...包括顺序表、链表、栈、串、稀疏矩阵、广义表、二叉树、图、存储管理、静态查找、动态查找、内部排序、外部排序等。使用语言为C/C++以及Pascal语言。
利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目,利用C/C++语言进行程序设计,并规范地完成课程设计报告。通过课程设计,巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识...