资源描述：
《数据结构之java排序javasort》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构排序思想和算法分析（java版）一、排序的概念：1、设n个记录的序列为{R1,R2,R3,...,Rn}其相应的关键字序列为{K1,K2,K3,...,Kn}若规定1,2,3,...,n的一个排列p1,p2,p3,...,pn，使得相应的关键字满足如下非递减关系:Kp1≤Kp2≤Kp3≤...≤Kpn则原序列变为一个按关键字有序的序列:Rp1,Rp2,Rp3,...,Rpn此操作过程称为排序。2、排序问题一般分为内排序(internalsorting)和外排序(externalsorting)两类：2.1.内排序：待排序的表中记录个数较少，整个排序过程中所有
2、的记录都可以保留在内存中；按照排序过程中所依据的原则的不同可以分类为:Ø插入排序（直接插入排序、折半插入排序、希尔排序）Ø交换排序(快速排序)（冒泡泡排序、快速排序）Ø选择排序（直接选择排序、堆排序） Ø归并排序Ø基数排序Ø二叉排序树排序2.2.外排序：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存。3、排序的时间复杂性：排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认
3、为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。 二、各种排序算法及代码详解： 1、插入类排序--直接插入排序插入类排序算法思想：主要就是对于一个已经有序的序列中，插入一个新的记录，但要求插入后此数据序列仍然有序，这个时候就要用到插入排序法。它包括：直接插入排序，折半插入排序和希尔排序。1.1、直接插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，直接插入排序用顺序比
4、较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j]≤L[j+1]时为止。算法描述1.2、一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：1.从第一个元素开始，该元素可以认为已经被排序，2.取出下一个元素，在已经排序的元素序列中从后向前扫描，3.如果该元素（已排序）大于新元素，将该元素移到下一位置，4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位
5、置，5.将新元素插入到下一位置中，6.重复步骤2；如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一种，称为二分查找排序。1.3、算法代码实现：publicclassDirectInserSort{publicstaticvoidmain(String[]args){intcount1=0,count2=0;//复制次数，比较次数longbegin=System.currentTimeMillis();System.out.println("插入前时间为："+begin);//TODOAuto-generated
6、methodstubintdata[]={2,6,10,3,9,80,1,16,27,20};inttemp,j;for(inti=1;i=0&&data[j]>temp){data[j+1]=data[j];j--;count1++;}data[j+1]=temp;count2++;}longend=System.currentTimeMillis();System.out.println("插入后时间为："+end);System.out.pr
7、intln("插入法用时为："+(end-begin));//输出排序好的数据for(intk=0;k
