范文无忧网计划总结工作总结

请问一下:有谁能总结数据结构中排序章内介绍各种算法的时间复杂

02月16日 编辑 fanwen51.com

[请问一下有谁能总结数据结构中排序章内介绍各种算法的时间复杂]1.插入排序:每次将一个待排的记录插入到前面的已经排好的队列中的适当位置。 ①.直接插入排序 直接排序法在最好情况下(待排序列已按关键码有序),每趟排序只需作1次比较而不需要...+阅读

1.插入排序:每次将一个待排的记录插入到前面的已经排好的队列中的适当位置。

①.直接插入排序

直接排序法在最好情况下(待排序列已按关键码有序),每趟排序只需作1次比较而不需要移动元素。所以n个元素比较次数为n-1,移动次数0。

最差的情况下(逆序),其中第i个元素必须和前面的元素进行比较i次,移动个数i+1,所以总共的比较次数 比较多,就不写出来了

总结:是一种稳定的排序方法,时间复杂度O(n^2),排序过程中只要一个辅助空间,所以空间复杂度O(1)

②.希尔排序

缩小增量排序,对直接插入排序的一种改进

分组插入方法。

总结:是一种不稳定的排序方法,时间复杂度O(n^1.25),空间复杂度O(1)

2.交换排序

①.冒泡排序

最好的情况下,就是正序,所以只要比较一次就行了,复杂度O(n)

最坏的情况下,就是逆序,要比较n^2次才行,复杂度O(n^2)

总结:稳定的排序方法,时间复杂度O(n^2),空间复杂度O(1),当待排序列有序时,效果比较好。

②.快速排序

通过一趟排序将待排的记录分割成独立的两部分,其中一部分记录的关键字均比另一个部分的关键字小,然后再分别对这两个部分记录继续进行排序,以达到整个序列有效。

总结:在所有同数量级O(nlogn)的排序方法中,快速排序是性能最好的一种方法,在待排序列无序时最好。算法的时间复杂度是O(nlogn),最坏的时间复杂度O(n^2),空间复杂度O(nlogn)

3.选择排序

①.直接选择排序

和序列的初始状态无关

总结:时间复杂度O(n^2),无论最好还是最坏

②.堆排序

直接选择排序的改进

总结:时间复杂度O(nlogn),无论在最好还是最坏情况下都是O(nlogn)

4.归并排序

总结:时间复杂度O(nlogn),空间复杂度O(n)

5.基数排序

按组成关键字的各个数位的值进行排序,是分配排序的一种。不需要进行排码值间的比较就能够进行排序。

总结:时间复杂度O(d(n+rd))

总总结:

n比较小的时候,适合 插入排序和选择排序

基本有序的时候,适合 直接插入排序和冒泡排序

n很大但是关键字的位数较少时,适合 链式基数排序

n很大的时候,适合 快速排序 堆排序 归并排序

无序的时候,适合 快速排序

稳定的排序:冒泡排序 插入排序 归并排序 基数排序

复杂度是O(nlogn):快速排序 堆排序 归并排序

辅助空间(大 次大):归并排序 快速排序

好坏情况一样:简单选择(n^2),堆排序(nlogn),归并排序(nlogn)

最好是O(n)的:插入排序 冒泡排序

延伸阅读:

数据结构堆排序算法#includevoid adjust(int *list,const int root,const int n); void HeapSort(int *list,const int n) { int i=0; for(i=n/2;i>=1;i--) adjust(list,i-1,n); int t=list[n]...

C语言中的排序方法探索根据自己的学习体会总结各种排序方法的可能会有些小错误,你自己可以根据需要进行改动,比如你可以直接定义一组数,就不需要随机产生数了,我想你应该改得了,呵呵,代码如下:#include#include#include#include#includeusingn...

谁能简单的总结一下民法总论的知识框架结构阿第一章 导言 第一节 法律分立中的私法 第二节 我国民法的制度语源 第三节 民法概念及调整对象 第四节 民法的法律渊源 第五节 民法法条 第二章 法律关系和权利 第六节 民法...

快速排序算法问题看看大家的思路/*刚看了下算法导论,写了一个,感觉效率还可以,你看看 */ #include <stdio.h> static int a[8] = {3, 7, 2, 8, 4, 5, 3, 9}; void swap (int *m, int *n) { int temp = *m; *m...

请问一下:有谁能总结数据结构中排序章内介绍各种算法的时间复杂1.插入排序:每次将一个待排的记录插入到前面的已经排好的队列中的适当位置。 ①.直接插入排序 直接排序法在最好情况下(待排序列已按关键码有序),每趟排序只需作1次比较而不需要...

急!C语言程序数据结构排序算法的问题#include"stdio.h" #include"stdlib.h" #include "string.h" #define Max 100 //假设文件长度 typedef struct{ //定义记录类型 int key; //关键字项 }RecType; typedef RecType Se...

C语言高效排序算法的原理及代码快速排序是通过分治的思想来实现的。即找一个 中间数,让小于这个数字的放在他左边,大于这个数字的放在右边!然后逐渐放小! 以升序为例: int qsort(ArrayStule *aS,int low,int hi...

C语言数据结构中的几种内部排序法求解!高手速度来指导我。以前的实验题。#define OK 1#define NULL 0#define ERROR 2#define ElemType int#include "iostream.h" #include "stdio.h"#include "stdlib.h" typedef struct LNode { int data...

排序算法c语言n个数字的排序我近期做练习的时候专门为排序做了一个c程序,你看看怎么样,包括了很多排序方法 #include#include#include#define LEN 10 //初始化数组 void init(int *arr,int len); //打印数...

推荐阅读
图文推荐
栏目列表