排序算法汇总25845

《排序算法汇总25845》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关于排序算法本人觉得，当时在学数据结构的时候我承认确实是没有学好，好几次笔试和面试都败在了排序算法上，今天我特意的把一些常用的排序总结一下。一、插入排序(InsertionSort)1.基本思想：  每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。2.排序过程：　【示例】：[初始关键字][49]38659776132749    J=2(38)[3849]659776132749    J=3(65)[384965]9776132749    J=4(97)[38496597]7613

2、2749    J=5(76)[3849657697]132749    J=6(13)[133849657697]2749    J=7(27)[13273849657697]49    J=8(49)[1327384949657697]Java代码：//待排序的数组apublicstaticvoidinsertSort(int[]a){              for(i=1;i

3、i]=a[i-1];               for(j=i;temp0;j--){                   a[j]=a[j-1];               }               a[j]=temp;//插入到正确的位置.           }       }   }二、选择排序1.基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。2.排序过程：【示例】：初始关键字[4938659776132749]第一趟排序后13［386

4、59776492749]第二趟排序后1327［659776493849]第三趟排序后132738[9776496549]第四趟排序后13273849[49976576]第五趟排序后1327384949[979776]第六趟排序后132738494976[7697]第七趟排序后13273849497676[97]最后排序结果1327384949767697Java代码：publicstaticvoidselectSort(int[]a){        intsmall;       inttemp;       for(inti=0;i

5、;i++){          small=i;          //遍历数组找到最小数字的索引值          for(intj=i+1;j

6、temp;          }       }    }三、堆排序（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就是

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

8、16，05，88建堆·Javacode·publicstaticvoidheap