#include
#include
//冒泡排序
voidbubleSort(int data[], int n);
//快速排序
voidquickSort(int data[], int low, int high); intfindPos(int data[], int low, int high);
//插入排序
voidbInsertSort(int data[], int n);
//希尔排序
voidshellSort(int data[], int n);
//选择排序
voidselectSort(int data[], int n);
//堆排序
voidheapSort(int data[], int n);
void swap(int data[], inti, int j);
voidheapAdjust(int data[], inti, int n);
//归并排序
voidmergeSort(int data[], int first, int last);
void merge(int data[], int low, int mid, int high); //基数排序
voidradixSort(int data[], int n);
intgetNumPos(intnum, intpos);
int main() {
int data[10] = {43, 65, 4, 23, 6, 98, 2, 65, 7, 79}; inti;
printf("原先数组:");
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
/*printf("冒泡排序:");
bubleSort(data, 10);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf("快速排序:");
quickSort(data, 0, 9);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf("插入排序:");
bInsertSort(data,10);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf("希尔排序:");
shellSort(data, 10);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf("选择排序:");
selectSort(data, 10);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79}; inti;
printf("原先数组:");
int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79}; for(i=1;i<11;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf(" 堆排序:");
heapSort(data, 10);
for(i=1;i<11;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf("归并排序:");
mergeSort(data, 0, 9);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");*/
printf("基数排序:");
radixSort(data, 10);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}
/*--------------------冒泡排序---------------------*/ voidbubleSort(int data[], int n) {
inti,j,temp;
//两个for循环,每次取出一个元素跟数组的其他元素比较
//将最大的元素排到最后。
for(j=0;j //外循环一次,就排好一个数,并放在后面, //所以比较前面n-j-1个元素即可 for(i=0;i if(data[i]>data[i+1]) { temp = data[i]; data[i] = data[i+1]; data[i+1] = temp; } } } } /*--------------------快速排序---------------------*/ intfindPos(int data[], int low, int high) { //将大于t的元素赶到t的左边,大于t的元素赶到t的右边 int t = data[low]; while(low < high) { while(low < high && data[high] >= t) { high--; } data[low] = data[high]; while(low < high && data[low] <=t) { low++; } data[high] = data[low]; } data[low] = t; //返回此时t在数组中的位置 return low; } //在数组中找一个元素,对大于该元素和小于该元素的两个数组进行再排序//再对两个数组分为4个数组,再排序,直到最后每组只剩下一个元素为止voidquickSort(int data[], int low, int high) { if(low > high) { return; } intpos = findPos(data, low, high); quickSort(data, low, pos-1); quickSort(data, pos+1, high); } /*--------------------插入排序---------------------*/ voidbInsertSort(int data[], int n) { intlow,high,mid; inttemp,i,j; for(i=1;i low = 0; //把data[i]元素插入到它的前面data[0-(i-1)]中 temp =data[i]; high = i-1; //该while是折半,缩小data[i]的范围(优化手段) while(low <= high) { mid = (low+high)/2; if(data[mid] > temp) { high = mid-1; } else { low = mid+1; } } int j = i; //让data与已经排序好的数组的各个元素比较,小的放前面while((j > low) && data[j-1] > temp) { data[j] = data[j-1]; --j; } data[low] = temp; } } /*--------------------希尔排序---------------------*/ voidshellSort(int * data, int n) { intstep,i,j,key; //将数组按照step分组,不断二分到每组只剩下一个元素 for(step=n/2;step>0;step/=2) { //将每组中的元素排序,小的在前 for(i=step;i key = data[i]; for(j=i-step;j>=0 && key data[j+step] = data[j]; } //和上面的for循环一起,将组中小的元素换到数组的前面data[j+step] = key; } } } /*--------------------选择排序---------------------*/ voidselectSort(int data[], int n) { inti,j,mix,temp; //每次循环数组,找出最小的元素,放在前面,前面的即为排序好的for(i=0;i //假设最小元素的下标 int mix = i; //将上面假设的最小元素与数组比较,交换出最小的元素的下标for(j=i+1;j if(data[j] < data[mix]) { mix = j; } } //若数组中真的有比假设的元素还小,就交换 if(i != mix) { temp = data[i]; data[i] = data[mix]; data[mix] = temp; } } } /*--------------------堆排序---------------------*/ //堆排序将数组先组成二叉树,默认从数组的data[1]开始排,data[0]是//无效数据 voidheapSort(int data[], int n) { inti; //先将数组组成一棵完全二叉树 //从2/n开始,就是从倒数第二排结点往前开始 for(i=n/2;i>0;i--) { heapAdjust(data, i, n); } //循环每个结点,将大的结点交换到堆顶 for(i=n;i>1;i--) { swap(data, 1, i); //每次交换完都要调整二叉树,将剩下的最大的结点交换到堆顶 heapAdjust(data, 1, i-1); } } //交换函数 void swap(int data[], inti, int j) { int temp; temp = data[i]; data[i] = data[j]; data[j] = temp; } voidheapAdjust(int data[], inti, int n) { int j, temp; //假设第一个结点的元素是最大的 temp = data[i]; //i结点:2*i是i结点的左结点,2*i+1是i结点的右结点 //把结点元素大的交换到前面 for(j=2*i;j<=n;j*=2) { if(j < n && data[j] < data[j+1]) { j++; } if(temp >= data[j]) { break; } data[i] = data[j]; i = j; } data[i] = temp; } /*--------------------归并排序---------------------*/ voidmergeSort(int data[], int first, int last) { int mid = 0; //将数组不停的二分分组再组合,直到每组只剩一个元素 if(first < last) { mid = (first+last)/2; mergeSort(data, first, mid); mergeSort(data, mid+1, last); merge(data, first, mid, last); } return; } void merge(int data[], int low, int mid, int high) { inti, k; //定义一个临时数组存放传进来的无序数组排好序之后的数组 int *temp = (int *)malloc((high-low+1)*sizeof(int)); //将无序数组分成两个序列 intleft_low = low; intleft_high = mid; intright_low = mid+1; intright_high = high; //将两个序列比较排序,小的排前 for(k=0;left_low<=left_high&&right_low<=right_high;k++) { if(data[left_low]<=data[right_low]) { temp[k] = data[left_low++]; } else{ temp[k] = data[right_low++]; } } //左序列如果有剩下元素未排序,加到临时数组的末尾 if(left_low<= left_high) { for(i=left_low;i<=left_high;i++) { temp[k++] = data[i]; } } //右序列如果有剩下元素未排序,加到临时数组的末尾 if(right_low<= right_high) { for(i=right_low;i<=right_high;i++) { temp[k++] = data[i]; } } //将排好序的小分组转移到原数组中 for(i=0;i data[low+i] = temp[i]; } free(temp); return; } /*--------------------基数排序---------------------*/ //该函数的作用是找出num的pos位数的数字(比如:23的个位数数字是3) intgetNumPos(intnum, intpos) { inti; int temp = 1; for(i=0;i temp *= 10; } return (num / temp) % 10; } voidradixSort(int data[], int n) { inti,j,k,pos,num,index; //这几句话是创建一个从0-9(行)× (n+1)(列)的网格,第一列从上往下是0-9, //第二列是该行包含的元素个数,默认为0个 int *radixArrays[10]; for(i=0;i<10;i++) { radixArrays[i] = (int *)malloc(sizeof(int) * (n+1)); radixArrays[i][0] = 0; } //pos最大为31为数,计算机能承受的最大范围了 for(pos=1;pos<=31;pos++) { //该for循环是将数组的元素按照位数(pos)的值放进网格内 for(i=0;i num = getNumPos(data[i], pos); index = ++radixArrays[num][0]; radixArrays[num][index] = data[i]; } //该for循环是将上面的for循环已经按照某个位数(pos)排列好的元素存入数组 for(i=0,j=0;i<10;i++) { for(k=1;k<=radixArrays[i][0];k++) { data[j++] = radixArrays[i][k]; } //清空网格,以便给下个位数排列 radixArrays[i][0] = 0; } } } 以上排序算法的优劣(时间复杂度和空间复杂度对比): C语言几种常见的排序方法 2009-04-2219:55 插入排序是这样实现的: 首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表")。 从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态。 重复2号步骤,直至原数列为空。 插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的: 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。 重复2号步骤,直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法。 选择排序 选择排序是这样实现的: 设数组内存放了n个待排数字,数组下标从1开始,到n结束。 i=1 从数组的第i个元素开始到第n个元素,寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n-1算法结束,否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始,我们要接触高效排序算法了。实践证明,快速排序是所有排序算法中最高效的一种。它采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部分排序,这样整个列表就有序了。这是一种先进的思想,也是它高效的原因。因为在排序算法中,算法的高效与否与列表中数字间的比较次数有直接的关系,而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了,大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同,它是这样的: 首先新建一个空列表,作用与插入排序中的"有序列表"相同。 找到数列中最大的数字,将其加在"有序列表"的末尾,并将其从原数列中删除。 重复2号步骤,直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高(因为有堆这种数据结构以及它奇妙的特征,使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度,维护需要logn的时间复杂度),但是实现相对复杂(可以说是这里7种算法中比较难实现的)。 C语言9种常用排序法 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.带哨兵的直接插入排序 9.基数排序 例子:乱序输入n个数,输出从小到大排序后的结果1.冒泡排序 #include for(i=0;i int i, j, n, a[100], t, temp; while(scanf("%d",&n)!=EOF) { for(i=0;i 五种排序算法的分析与比较 广东医学院医学信息专业郭慧玲 摘要:排序算法是计算机程序设计广泛使用的解决问题的方法,研究排序算法具有重要的理论意义和广泛的应用价值。文章通过描述冒泡、选择、插入、归并和快速5种排序算法,总结了它们的时间复杂度、空间复杂度和稳定性。通过实验验证了5种排序算法在随机、正序和逆序3种情况下的性能,指出排序算法的适用原则,以供在不同条件下选择适合的排序算法借鉴。 关键词:冒泡排序;选择排序;插入排序;归并排序;快速排序。 排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除。随着计算机的发展与应用领域的越来越广,基于计算机硬件的速度和存储空间的有限性,如何提高计算机速度并节省存储空间一直成为软件设计人员的努力方向。其中,排序算法已成为程序设计人员考虑的因素之一[1],排序算法选择得当与否直接影响程序的执行效率和内外存储空间的占用量,甚至影响整个软件的综合性能。排序操作[2,3],就是将一组数据记录的任意序列,重新排列成一个按关键字有序的序列。而所谓排序的稳定性[4]是指如果在排序的序列中,存在前后相同的两个元素,排序前和排序后他们的相对位臵不发生变化。 1 算法与特性 1.1冒泡排序 1.1.1冒泡排序的基本思想 冒泡排序的基本思想是[5,6]:首先将第1个记录的关键字和第2个记录的关键字进行比较,若为逆序,则将2个记录交换,然后比较第2个和第3个记录的关键字,依次类推,直至n-1个记录和第n个记录的关键字进行过比较为止。然后再按照上述过程进行下一次排序,直至整个序列有序为止。 1.1.2冒泡排序的特性 容易判断冒泡排序是稳定的。可以分析出它的效率,在最好情况下,只需通过n-1次比较,不需要移动关键字,即时间复杂度为O(n)(即正序);在最坏情况下是初始序列为逆序,则需要进行n-1次排序,需进行n(n-1)/2次比较,因此在最坏情况下时间复杂度为O(n2),附加存储空间为O(1)。 1.2选择排序 1.2.1选择排序的基本思想 选择排序的基本思想是[5,6]:每一次从待排序的记录中选出关键字最小的记录,顺序放在已排好序的文件的最后,直到全部记录排序完毕.常用的选择排序方法有直接选择排序和堆排序,考虑到简单和易理解,这里讨论直接选择排序。直接选择排序的基本思想是n个记录的文件的直接排序可经过n-1次直接选择排序得到有序结果。 1.2.2选择排序的特性 容易得出选择排序是不稳定的。在直接选择排序过程中所需进行记录移动的操作次数最少为0,最大值为3(n-1)。然而,无论记录的初始排序如何,所需进行的关键字间的比较次数相同,均为n(n-1)/2,时间 一、设计思想 插入排序:首先,我们定义我们需要排序的数组,得到数组的长度。如果数组只有一个数字,那么我们直接认为它已经是排好序的,就不需要再进行调整,直接就得到了我们的结果。否则,我们从数组中的第二个元素开始遍历。然后,启动主索引,我们用curr当做我们遍历的主索引,每次主索引的开始,我们都使得要插入的位置(insertIndex)等于-1,即我们认为主索引之前的元素没有比主索引指向的元素值大的元素,那么自然主索引位置的元素不需要挪动位置。然后,开始副索引,副索引遍历所有主索引之前的排好的元素,当发现主索引之前的某个元素比主索引指向的元素的值大时,我们就将要插入的位置(insertIndex)记为第一个比主索引指向元素的位置,跳出副索引;否则,等待副索引自然完成。副索引遍历结束后,我们判断当前要插入的位置(insertIndex)是否等于-1,如果等于-1,说明主索引之前元素的值没有一个比主索引指向的元素的值大,那么主索引位置的元素不要挪动位置,回到主索引,主索引向后走一位,进行下一次主索引的遍历;否则,说明主索引之前insertIndex位置元素的值比主索引指向的元素的值大,那么,我们记录当前主索引指向的元素的值,然后将主索引之前从insertIndex位置开始的所有元素依次向后挪一位,这里注意,要从后向前一位一位挪,否则,会使得数组成为一串相同的数字。最后,将记录下的当前索引指向的元素的值放在要插入的位置(insertIndex)处,进行下一次主索引的遍历。继续上面的工作,最终我们就可以得到我们的排序结果。插入排序的特点在于,我们每次遍历,主索引之前的元素都是已经排好序的,我们找到比主索引指向元素的值大的第一个元素的位置,然后将主索引指向位置的元素插入到该位置,将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法,使得挪动的次数相对较多,如果对于排序数据量较大,挪动成本较高的情况时,这种排序算法显然成本较高,时间复杂度相对较差,是初等通用排序算法中的一种。 选择排序:选择排序相对插入排序,是插入排序的一个优化,优化的前提是我们认为数据是比较大的,挪动数据的代价比数据比较的代价大很多,所以我们选择排序是追求少挪动,以比较次数换取挪动次数。首先,我们定义我们需要排序的数组,得到数组的长度,定义一个结果数组,用来存放排好序的数组,定义一个最小值,定义一个最小值的位置。然后,进入我们的遍历,每次进入遍历的时候我们都使得当前的最小值为9999,即认为每次最小值都是最大的数,用来进行和其他元素比较得到最小值,每次认为最小值的位置都是0,用来重新记录最小值的位置。然后,进入第二层循环,进行数值的比较,如果数组中的某个元素的值比最小值小,那么将当前的最小值设为元素的值,然后记录下来元素的位置,这样,当跳出循环体的时候,我们会得到要排序数组中的最小值,然后将最小值位置的数值设置为9999,即我们得到了最小值之后,就让数组中的这个数成为最大值,然后将结果数组result[]第主索引值位置上的元素赋值为最小值,进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result[]。选择排序的优势在于,我们挪动元素的次数很少,只是每次对要排序的数组进行整体遍历,找到其中的最小的元素,然后将改元素的值放到一个新的结果数组中去,这样大大减少了挪动的次序,即我们要排序的数组有多少元素,我们就挪动多少次,而因为每次都要对数组的所有元素进行遍历,那么比较的次数就比较多,达到了n2次,所以,我们使用选择排序的前提是,认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序,他的比较次数大于插入排序的次数,而挪动次数就很少,元素有多少个,挪动次数就是多少个。 希尔排序:首先,我们定义一个要排序的数组,然后定义一个步长的数组,该步长数组是由一组特定的数字组成的,步长数组具体得到过程我们不去考虑,是由科学家经过很长时间计算得到的,已经根据时间复杂度的要求,得到了最适合希尔排序的一组步长值以及计算 一插入排序 1.1 直接插入排序 基本思想:每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中,直到全部记录排好序。 图解: 1.//直接顺序排序 2.void InsertSort(int r[], int n) 3.{ 4.for (int i=2; i 代码实现: [cpp]view plain copy 1.//希尔排序 2.void ShellSort(int r[], int n) 3.{ 4.int i; 5.int d; 6.int j; 7.for (d=n/2; d>=1; d=d/2) //以增量为d进行直接插入排序 8. { 9.for (i=d+1; i 一.插入:C语言数组怎么插入一个元素#include for(i=0;i 基于C语言地多种排序方法地实现 1 引言 1.1 课题背景 排序问题源远流长,一直是数学地重要组成部分.随着各种信息地快速更新,排序问题也走进了其他领域以及我们地日常生活.如何高效地排序一直困扰着我们. 1.2 课程设计目地 排序是数学地重要组成部分,工作量大是其存在地问题.如何高效地排序?本程序就是解决这个问题而设计.程序中,把数列储存在数组中,采用插入排序等十种排序方法对数组元素进行排序,高效地解决了排序问题.本软件开发地平台为最新地微软公司出版地市面最新系统Windows 2000,而且可以作为自身地运行平台非常广泛,包括 Windows 98/2000/XP/Vista等等. 1.3课程设计内容 本程序把对数列地排序转化为对数组元素地排序,用户可以根据自己地实际问题选择系统提供地七种排序方法地任意一种进行排序.程序通过自身地判断以及处理实现排序.程序最后输出每趟排序及初始排序结果. 2 系统分析与设计方案 2.1 系统分析 设计一个排序信息管理系统,使之能够操作实现以下功能: 1) 显示需要输入地排序长度及其各个关键字 2) 初始化输入地排序序列 3) 显示可供选择地操作菜单 4) 显示输出操作后地移动次数和比较次数 5) 显示操作后地新序列 5) 可实现循环继续操 2.2 设计思路 通过定义C语言顺序表来存储排序元素信息,构造相关函数,对输入地元素进行相应地处理. [2] 2.3 设计方案 设计方案如图2.1所示 图2.1 设计方案 具体流程见图2.2 图 2.2 程序流程图 3功能设计 3.1 SqList顺序表 其中包括顺序表长度,以及顺序表.源代码如下:[1] typedef struct { KeyType key。 //关键字项 InfoType otherinfo。 //其他数据项 }RedType。 typedef struct { RedType r[MaxSize+1]。 //r[0]作为监视哨 int length。 //顺序表长度 }SqList。 3.2 直接插入排序 直接插入排序是将一个记录插入到已排好序地有序表中,从而得到一个新地、记录数增1地有序表 图3.1 直接插入排序示意图 将第i个记录地关键字r[i].key顺序地与前面记录地关键字r[i-1].key,r[i-2].key,……,r[1].key进行比较,把所有关键字大于r[i].key地记录依次后移一位,直到关键字小于或者等于r[i].key地记录C语言几种常见的排序方法
C语言9种常用排序法
五种排序算法的分析与比较
几种排序算法的分析与比较--C语言
c语言各种排序法详细讲解
C语言一维数组的基本操作
基于C语言的多种排序方法的实现
C语言算法锦集(六) 数组常用操作