内部排序（总结）

内部排序：排序记录放在计算机存储器里面进行的。

内部排序分三类：

1.简单排序，时间复杂度O(n^2);

2.先进排序方法，时间复杂度O(nlogn);

3.基数排序，时间复杂度O(d·n);

1.1直接插入排序

void InsertSort(SqList &L){
//对顺序表L作直接插入排序
      for(i=2;i 
先把第一个看成有序，然后从第二个开始循环
 
箭头就是插入。
 
优化（时间复杂度不变）
 
   折半插入（二分插入） 
 
减少比较移动，在一个有序表里面插入。
 
 
2.2-路插入排序
 
  减少排序过程中的移动次数，但需要牺牲辅助空间。
 
取第一个为起始，放在第一位，构造两个指针，first和final。最开始指针都是指向第一个数，然后开始读取关键字比较， 比第一个大，放在第一个后面，final=final->next，比第一个小，放在第一个前面，因为第一个前面没有空间，然后做循环链表，first=比第一个小那个数位置
 
 
3.表插入。 
 
改变指针数据
 
 
 希尔排序 
也叫缩小增量排序，也是插入排序的一种。时间复杂度O（n）。但是不稳定。
 
第一趟，搁x位为一组，大在右边
 
第二趟，搁小于x的y位一组。。。
 
快速排序 
   冒泡：
 
冒泡思想
 
第一趟：n个里面最大的交换到右边
 
第二：n-1个里面最大的交换到右边
 
快速排序对冒泡的改进
 
通过一趟排序把待排分成两部分，其中一部分关键字均比另外一部分小，分别对两部分排序。任选一个数做枢纽，比他大在一边，小在一边，分成两部分，对那两部分递归，分别选一个数，在那两部分里面比他大在一边，小一边。。。。。。
 
 
 
 
先high比，如果发生交换，又从low开始，交换再到high。
 
为什么交换过去为空，已经存储了减少赋值次数。
 
选择排序 
1.1 简单选择
 
  
 
1.2 树形选择排序
 
构造一个n个叶结点完全二叉树。
 
完全二叉树：从上到下，从左到右排，满二叉是他的一种。
 
 
 
1.3 堆排序 
 
构造完全二叉树。
 
 
根小于左子小于右子叫小顶堆，反之叫大顶堆。
 
出顶后，二叉树最后一个元素作为顶，然后进行大顶小顶判断，符合条件后，再次出顶，再从选最后一个（没出）为顶。
 
时间复杂度O（nlogn） 
 
归并排序 
类似2-路插入
 
基数排序 
多关键字。链式基数排序。
 
 比较 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5684504.html