一起学习交流~

排序-00-内部排序和外部排序的区别

算法 laomuji 12个月前 (10-07) 349次浏览 已收录 0个评论

一、什么是内部排序和外部排序

排序是计算机程序设计中的一种重要操作,其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个相知有序的序列。排序分为两类:内排序和外排序。

二、内部排序

  • 内部排序是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。
  • 内部排序方法:
  • 1.插入排序;
  • 2.快速排序;
  • 3.选择排序;
  • 4.归并排序;
  • 5.冒泡排序;
  • 6.希尔排序;
  • 7.堆排序;
  • 8.基数排序;

三、外部排序

外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。

  • 一般来说外排序分为两个步骤:预处理和合并排序。
  • 首先,根据可用内存的大小,将外存上含有n个纪录的文件分成若干长度为t的子文件(或段);
  • 其次,利用内部排序的方法,对每个子文件的t个纪录进行内部排序。
  • 这些经过排序的子文件(段)通常称为顺串(run),顺串生成后即将其写入外存。
  • 这样在外存上就得到了m个顺串(m=[n/t])。
  • 最后,对这些顺串进行归并,使顺串的长度逐渐增大,直到所有的待排序的记录成为一个顺串为止。

喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论