数据结构JAVA版

ThecourseofelaborationforDataStructures数据结构(JAVA版)．1排序排序是将一组杂乱无章的数据重新排列成按照关键字有序的序列排序算法的稳定性如果有两个数据元素ri和rj,他们关键字ki等于kj，且排序前ri位于rj之前。若排序后，元素ri仍在rj之前，则称这样的排序算法是稳定的，否则就是不稳定的。内部排序与外部排序内部排序：在待排序的数据序列中，元素的个数较少，排序整个过程所有的元素都保留在内存。外部排序：待排序的数据很多，排序过程中数据要不断的内外存数据交替存取。这里我们重点介绍的是内部排序排序算法的性能评价算法的时间复杂度：算法执行中，数据的比较次数、移动次数与数据个数的关系算法的空间复杂度：算法执行中，除待排序数据本身所占用的内存空间外，需要附加内存空间与数据元素个数的关系8．2交换排序冒泡排序(BubbleSort)交换排序快速排序(QuickSort)8．2．1冒泡排序排序方法将相邻的两个数据按关键字进行比较。若反序则交换，经一趟排序后，最大的值移到最后的位置，再对上面的元素重复刚才的操作，直到剩下一个元素为止。算法分析该算法最好的情况是已排序好的数据，只需一趟排序即可，比较次数为n，没有移动。最坏情况是反序的数据序列，需要n-1趟排序，比较次数和移动次数都是Ο（n2）因此，此算法的时间复杂度是Ο（n2）。8．2．1冒泡排序实例初始关键字序列:第一次排序结果:第二次排序结果:第三次排序结果:第四次排序结果:第五次排序结果:最后结果序列:38519264997166519263849166[97]5192638149[6697]51926138[496697]519126[38496697]5119[2638496697]15[192638496697]1[5192638496697]15192638496697第六次排序结果:第七次排序结果:8．2．1冒泡排序程序实现publicstaticvoidBubbleSort(intIndex){inti,j,k;//循环计数变量booleanChange;//数据是否有改变intTemp;//数据暂存变量for(j=Index;j1;j--)//外层循环{Change=false;//设置为数据未改变for(i=0;jj-1;j++)//内层循环{//比较两数值if(Data[i+1]Data[i])8．2．1冒泡排序{//交换两数值Temp=Data[i+1];Data[i+1]=Data[i];Data[i]=Temp;Change=true;//设置数据已改变}}if(Change)//如果数据已改变则输出结果{//打印目前排序状况System.out.print(CurrentSortingResult:);for(k=0;kIndex;k++)System.out.print(+Data[k]+);System.out.println();}}}8.2.2快速排序算法思想在待排序的数据中选一个数据作为基准，由序列的两边交替地向中间比较、交换，使得所有比基准小的元素都处于序列的左端，比基准大的元素都处于序列的右端，这样序列就被划分成两个子序列。再对两个子序列分别进行同样的操作，直到子序列的长度为1为止。实例初始关键字序列:第1次排序后第2次排序后{6055483710908436{3655483710}60{8490}{10}36{483755}6084{90}第3次排序后{10}36{37}48{55}608490最后结果10363748556084908.2.2快速排序程序实现publicstaticvoidQuickSort(intleft,intRight,intIndex){inti,j,k;//循环计数变量intPivot;//枢纽变量intTemp;//暂存变量i=Left;//设定左指针j=right+1;//设定右指针Pivot=Data[Left];//取最左边的元素if(ij){do{do//从左往右找比Pivot大的值{i++;}while(Data[i]=Pivot&&i=Right);do//从右往左找比Pivot小的值{j—}while(Data[j]=Pivot&&j.Left);8.2.2快速排序if(ij)//交换Data[i]和Data[j]{Temp=Data[i];Data[i]=Data[j];Data[j]=Temp;}while(ij);if(ij){Temp=Data[lefe];//交换Data[Left]和Data[j]Data[Left]=Data[j];Data[j]=Temp;//打印目前排序结果System.out.print(“Currentsortingresult;”);for(k=0;kIndex;k++){System,out.print(“”+Data[k]+””);}System,out.println(“”);}QuickSort(Left,j-1,Index);//排序左半边QuickSort(j+1,Right,Index);//排序右半边}}8.2.2快速排序算法分析快速排序是目前平均性能较好的一种排序方法。时间复杂度为Ο（nlog2n）。最好情况是，每趟排序后将序列分成两个长度相同的子序列。最坏情况是，当序列已排好序。此时时间复杂度为Ο（n2），比直接插入排序还慢。快速排序是不稳定的算法，另外它是递归算法，所以运行时，系统需要设立一个工作栈。8．3选择排序简单选择排序(SinpleSelectionSort)选择排序堆排序(HeapSort)8．3．1简单选择排序算法思想假设待排序的数据序列有n个元素，第一趟，比较n个元素，选择关键字最小的元素，跟第一个元素交换；第二趟，在余下的n-1个元素中选择关键字次小的元素与第二个数据交换……经过n-1趟排序就完成。实例645789624[5]64789624[56]7896424[567]896424[56724]6489[5672464]89初始关键字序列:第一次排序结果:第二次排序结果:第三次排序结果:第四次排序结果:第五次排序结果:[567246489]最后结果序列:8．3．1简单选择排序程序实现Publicstaticvoidselectsort(intindex){IntI,j,k;//循环计数变量Intminvalue;//最小值变量Intintdexmin;//最小值下标变量Inttemp;//暂存变量For(i=o;iindex-1;i++){MinValue=32767;//目前最小数值IndexMin=0;//存储最小数值的下标量for(i=0;IIndex;j++){If(Data[j]MinValue)//找到最小值{MinValue=data[j];//存储最小值IndexMin=j;}8．3．1简单选择排序Temp=Data[i]//交换两数值Data[i]=Data[IndexMin];Data[IndexMin]=Temp;}System.out.print(“Currentsortingresult:”);For(k=0;kIndex;k++);System.out.print(“”+Data[k]+””);System.out.print(“”);}}算法分析简单选择排序的比较次数与数据的初始排列无关。其时间复杂度为Ο(n2），是不稳定的排序方法。8.3.2堆排序堆的定义堆是一棵完全二叉树，堆排序用的就是“大根堆”。大根堆的条件是：完全二叉树中所有非终端结点的值均不小于其左孩子和右孩子结点的值。建立堆初始堆:8.3.2堆排序调整5后:8.3.2堆排序调整32后:8.3.2堆排序调整50后:8.3.2堆排序调整10后:8.3.2堆排序利用堆排序先建一个”大根堆”,将根结点与最后一个结点交换,然后对前n-1个数据进行筛选,重复将它调整为一个大根堆,反复重复操作直至排序结束.算法分析堆排序的时间复杂度为Ο（nlog2n）；是不稳定的排序方法；空间复杂度为Ο（1）。8.3.2堆排序8876405010932588764050109325(a)76504051093276504051093288503240510950324051097688(b)(c)4032951040329510507688(d)3210953210954050768832109105932405076889595103240507688(g)559103240507688(h)(f)(e)8.3.2堆排序之建立堆程序//建立堆publicstaticvoidcerateheap(introot，intindex){intI,j；//循环计数变量inttemp；//暂存变量intfinish；//判断是否建立完成j=2*root；//子节点的Indextemp=heap[root]；//暂存堆的Root值finish=0；//欲设堆建立尚未完成while（j《=index——finish==0》{If（j〈index〉//找最大的子节点If（heap[j]heap[j+1]）J++；if（temp=heap[j]）finish=1;//堆建立完成Else{Heap[j/2]=temp;//父节点=目前节点J=2*j;}}Heap[j/2]=temp;//父节点=Root值}8.3.2堆排序之堆排序程序Publicstaticvoidheapsort(intindex){IntI,j,temp;//将二叉树转成堆For(i=(index/2);i=1；i--;)Createheap(I,index);//开始进行堆建设for(i=index/2);i=1;i--){Temp=heap[i+1];//堆的Root值和最后一个值交换Heap[i+1]=heap[1];Heap[i]=temp;createheap(1,i);//对其余数值重建堆//打印堆的处理过程system.out.print(“sortingprocess:”;for(j=1;j=index;j++)system.out.print(““+heap[j]+”“);system.out.print(““);}}8.4插入排序1直接插入排序StraightInsertionSort2希尔排序ShellSort3二叉树排序Binary_treeSort8．4．1直接插入排序排序方法从第二个元素开始依次将每个元素插入到前面有序的序列中，经过n-1次完成。实例[64]789624[564]89624[5764]624[576489]24[5676489][567246489]5789624初始关键字序列:第一次排序:第二次排序:第三次排序:第四次排序:第五次排序:8．4．1直接插入排序程序实现publicstaticvoidinsertsort(intindex){intI,j,k;//循环计数变量intinsertnode;//欲插入数据变量for(I=1;Iindex;I++)//依次插入数值{insertnode=data[I];//设定欲插入的数值j=I-1;//欲插入数组的开始位置//找适当的位置while(j=0&&insertnodedata[j]){data[j+1]=data[j];j--;}data[j+1]=insertnode;//将数值插入//打印目前排序结果system.out.print(“currentsortingresult:”);for(k=0;kindex;k++)system.out.print(““+data[k]+”“);system.out.println(““);}}8．4．1