直接插入排序法算法思想

1. 关于数据结构排序算法的问题

选择排序

插入排序：每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。

选择排序：简单的选择排序，它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数
据可以发现它耗时相差不多，相差的只是数据移动时间），可见对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情
况下将快于冒泡排序。

冒泡排序：在最优情况下只需要经过n-1次比较即可得出结果，（这个最优情况那就是序列己是正序，从100K的正序结果可以看出结果正是如此），但在最坏情况下，即倒序（或一个较小值在最后），下沉算法将需要n(n-1)/2次比较。所以一般情况下，特别是在逆序时，它很不理想。它是对数据有序性非常敏感的排序算法。
堆排序：由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。

基数排序：在程序中采用的是以数值的十进制位分解，然后对空间采用一次性分配，因此它需要较多的辅助空间(10*n+10), （但我们可以进行其它分解，如以一个字节分解，空间采用链表将只需辅助空间n+256）。基数排序的时间是线性的(即O(n))。由此可见，基数排序非常吸引人，但它也不是就地排序，若节点数据量大时宜改为索引排序。但基数排序有个前提，要关键字能象整型、字符串这样能分解，若是浮点型那就不行了。

2. 排序法都有哪些

一、插入排序(InsertionSort)
1.基本思想：
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
2.排序过程：
【示例】：
[初始关键字][49]38659776132749
J=2(38)[3849]659776132749
J=3(65)[384965]9776132749
J=4(97)[38496597]76132749
J=5(76)[3849657697]132749
J=6(13)[133849657697]2749
J=7(27)[13273849657697]49
J=8(49)[1327384949657697]

1. ProcereInsertSort(VarR:FileType);
   
2. //对R[1..N]按递增序进行插入排序,R[0]是监视哨//
   
3. Begin
   
4. forI:=2ToNDo//依次插入R[2],...,R[n]//
   
5. begin
   
6. R[0]:=R;J:=I-1;
   
7. WhileR[0]<R[J]Do//查找R的插入位置//
   
8. begin
   
9. R[J+1]:=R[J];//将大于R的元素后移//
   
10. J:=J-1
    
11. end
    
12. R[J+1]:=R[0];//插入R//
    
13. end
    
14. End;//InsertSort//

复制代码二、选择排序
1.基本思想：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
2.排序过程：
【示例】：
初始关键字[4938659776132749]
第一趟排序后13［38659776492749]
第二趟排序后1327［659776493849]
第三趟排序后132738[9776496549]
第四趟排序后13273849[49976576]
第五趟排序后1327384949[979776]
第六趟排序后132738494976[7697]
第七趟排序后13273849497676[97]
最后排序结果1327384949767697

1. ProcereSelectSort(VarR:FileType);//对R[1..N]进行直接选择排序//
   
2. Begin
   
3. forI:=1ToN-1Do//做N-1趟选择排序//
   
4. begin
   
5. K:=I;
   
6. ForJ:=I+1ToNDo//在当前无序区R[I..N]中选最小的元素R[K]//
   
7. begin
   
8. IfR[J]<R[K]ThenK:=J
   
9. end;
   
10. IfK<>IThen//交换R和R[K]//
    
11. beginTemp:=R;R:=R[K];R[K]:=Temp;end;
    
12. end
    
13. End;//SelectSort//

复制代码三、冒泡排序(BubbleSort)
1.基本思想：
两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。
2.排序过程：
设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
【示例】：
4913131313131313
3849272727272727
6538493838383838
9765384949494949
7697654949494949
1376976565656565
2727769776767676
4949497697979797

1. ProcereBubbleSort(VarR:FileType)//从下往上扫描的起泡排序//
   
2. Begin
   
3. ForI:=1ToN-1Do//做N-1趟排序//
   
4. begin
   
5. NoSwap:=True;//置未排序的标志//
   
6. ForJ:=N-1DownTo1Do//从底部往上扫描//
   
7. begin
   
8. IfR[J+1]<R[J]Then//交换元素//
   
9. begin
   
10. Temp:=R[J+1];R[J+1:=R[J];R[J]:=Temp;
    
11. NoSwap:=False
    
12. end;
    
13. end;
    
14. IfNoSwapThenReturn//本趟排序中未发生交换，则终止算法//
    
15. end
    
16. End;//BubbleSort//

复制代码四、快速排序（QuickSort）
1.基本思想：
在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
2.排序过程：
【示例】：
初始关键字[4938659776132749］
第一次交换后
［2738659776134949］
第二次交换后
［2738499776136549］
J向左扫描，位置不变，第三次交换后
［2738139776496549］
I向右扫描，位置不变，第四次交换后
［2738134976976549］
J向左扫描
［2738134976976549］
（一次划分过程）

初始关键字
［4938659776132749］
一趟排序之后
［273813］49［76976549］
二趟排序之后
［13］27［38］49［4965］76［97］
三趟排序之后1327384949［65］7697
最后的排序结果1327384949657697
各趟排序之后的状态

1. ProcereParttion(VarR:FileType;L,H:Integer;VarI:Integer);
   
2. //对无序区R[1,H]做划分，I给以出本次划分后已被定位的基准元素的位置//
   
3. Begin
   
4. I:=1;J:=H;X:=R;//初始化，X为基准//
   
5. Repeat
   
6. While(R[J]>=X)And(I<J)Do
   
7. begin
   
8. J:=J-1//从右向左扫描，查找第1个小于X的元素//
   
9. IfI<JThen//已找到R[J]〈X//
   
10. begin
    
11. R:=R[J];//相当于交换R和R[J]//
    
12. I:=I+1
    
13. end;
    
14. While(R<=X)And(I<J)Do
    
15. I:=I+1//从左向右扫描，查找第1个大于X的元素///
    
16. end;
    
17. IfI<JThen//已找到R>X//
    
18. begin R[J]:=R;//相当于交换R和R[J]//
    
19. J:=J-1
    
20. end
    
21. UntilI=J;
    
22. R:=X//基准X已被最终定位//
    
23. End;//Parttion//

复制代码

1. ProcereQuickSort(VarR:FileType;S,T:Integer);//对R[S..T]快速排序//
   
2. Begin
   
3. IfS<TThen//当R[S..T]为空或只有一个元素是无需排序//
   
4. begin
   
5. Partion(R,S,T,I);//对R[S..T]做划分//
   
6. QuickSort(R,S,I-1);//递归处理左区间R[S,I-1]//
   
7. QuickSort(R,I+1,T);//递归处理右区间R[I+1..T]//
   
8. end;
   
9. End;//QuickSort//

复制代码五、堆排序(HeapSort)
1.基本思想：
堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2.堆的定义:N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：
Ki≤K2iKi≤K2i+1(1≤I≤[N/2])


堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。
3.排序过程：
堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。
【示例】：对关键字序列42，13，91，23，24，16，05，88建堆

1. ProcereSift(VarR:FileType;I,M:Integer);
   
2. //在数组R[I..M]中调用R，使得以它为完全二叉树构成堆。事先已知其左、右子树(2I+1<=M时)均是堆//
   
3. Begin
   
4. X:=R;J:=2*I;//若J<=M,R[J]是R的左孩子//
   
5. WhileJ<=MDo//若当前被调整结点R有左孩子R[J]//
   
6. begin
   
7. If(J<M)AndR[J].Key<R[J+1].KeyThen
   
8. J:=J+1//令J指向关键字较大的右孩子//
   
9. //J指向R的左、右孩子中关键字较大者//
   
10. IfX.Key<R[J].KeyThen//孩子结点关键字较大//
    
11. begin
    
12. R:=R[J];//将R[J]换到双亲位置上//
    
13. I:=J;J:=2*I//继续以R[J]为当前被调整结点往下层调整//
    
14. end;
    
15. Else
    
16. Exit//调整完毕，退出循环//
    
17. end
    
18. R:=X;//将最初被调整的结点放入正确位置//
    
19. End;//Sift//

复制代码

1. ProcereHeapSort(VarR:FileType);//对R[1..N]进行堆排序//
   
2. Begin
   
3. ForI:=NDivDownto1Do//建立初始堆//
   
4. Sift(R,I,N)
   
5. ForI:=NDownto2do//进行N-1趟排序//
   
6. begin
   
7. T:=R[1];R[1]:=R;R:=T;//将当前堆顶记录和堆中最后一个记录交换//
   
8. Sift(R,1,I-1)//将R[1..I-1]重成堆//
   
9. end
   
10. End;//HeapSort//

复制代码六、几种排序算法的比较和选择
1.选取排序方法需要考虑的因素：
(1)待排序的元素数目n；
(2)元素本身信息量的大小；
(3)关键字的结构及其分布情况；
(4)语言工具的条件，辅助空间的大小等。
2.小结：
(1)若n较小(n<=50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2)若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4)在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。

这句话很重要它告诉我们自己写的算法是有改进到最优当然没有必要一直追求最优
(5)当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。