数据结构JAVA版.ppt
《数据结构JAVA版.ppt》由会员分享,可在线阅读,更多相关《数据结构JAVA版.ppt(34页珍藏版)》请在三一文库上搜索。
1、,数据结构(JAVA版),www.YT_JAVA.com,烟台职业学院精品课,第八章 排序,81 排序,排序是将一组杂乱无章的数据重新排列成按照关键字有序的序列 排序算法的稳定性 如果有两个数据元素ri 和rj ,他们关键字ki等于 kj,且排序前ri位于rj之前。若排序后,元素ri仍在rj之前,则称这样的排序算法是稳定的,否则就是不稳定的。 内部排序与外部排序 内部排序:在待排序的数据序列中,元素的个数较少,排序整个过程所有的元素都保留在内存。 外部排序:待排序的数据很多,排序过程中数据要不断的内外存数据交替存取。 这里我们重点介绍的是内部排序 排序算法的性能评价 算法的时间复杂度:算法执行
2、中,数据的比较次数、移动次数与数据个数的关系 算法的空间复杂度:算法执行中,除待排序数据本身所占用的内存空间外,需要附加内存空间与数据元素个数的关系,82 交换排序,821 冒泡排序,排序方法 将相邻的两个数据按关键字进行比较。若反序则交换,经一趟排序后,最大的值移到最后的位置,再对上面的元素重复刚才的操作,直到剩下一个元素为止。 算法分析 该算法最好的情况是已排序好的数据,只需一趟排序即可,比较次数为n,没有移动。最坏情况是反序的数据序列,需要n-1趟排序,比较次数和移动次数都是(n2)因此,此算法的时间复杂度是(n2)。,821 冒泡排序,实例,821 冒泡排序,程序实现 public s
3、tatic void BubbleSort(int Index) int i,j,k; /循环计数变量 boolean Change; /数据是否有改变 int Temp; /数据暂存变量 for (j = Index ; j1; j-) /外层循环 Change = false; /设置为数据未改变 for (i=0;jj-1;j+) /内层循环 /比较两数值 if(Datai+1Datai),821 冒泡排序, / 交换两数值 Temp = Datai+1; Datai+1 = Datai; Datai = Temp; Change = true; /设置数据已改变 if(Change)
4、/如果数据已改变则输出结果 /打印目前排序状况 System.out.print(“Current Sorting Result :“); for(k=0;kIndex;k+) System.out.print(“ “+Datak+“ “); System.out.println(“); ,8.2.2 快速排序,算法思想 在待排序的数据中选一个数据作为基准,由序列的两边交替地向中间比较、交换,使得所有比基准小的元素都处于序列的左端,比基准大的元素都处于序列的右端,这样序列就被划分成两个子序列。再对两个子序列分别进行同样的操作,直到子序列的长度为1为止。 实例,8.2.2 快速排序,程序实现 p
5、ublic static void QuickSort(int left,int Right,int Index) int i,j,k; /循环计数变量 int Pivot; /枢纽变量 int Temp; /暂存变量 i=Left; /设定左指针 j=right+1; /设定右指针 Pivot=DataLeft; /取最左边的元素 if (i=Pivot,8.2.2 快速排序,if(ij); if(ij) Temp=Datalefe; /交换DataLeft和Dataj DataLeft=Dataj; Dataj=Temp; /打印目前排序结果 System.out.print(“Curre
6、nt sorting result;”); for(k=0;kIndex;k+) System,out.print(“”+Datak+”); System,out.println(“”); QuickSort(Left,j-1,Index); /排序左半边 QuickSort(j+1,Right,Index); /排序右半边 ,8.2.2 快速排序,算法分析 快速排序是目前平均性能较好的一种排序方法。时间复杂度为(nlog2n)。最好情况是,每趟排序后将序列分成两个长度相同的子序列。最坏情况是,当序列已排好序。此时时间复杂度为(n2),比直接插入排序还慢。 快速排序是不稳定的算法,另外它是递归
7、算法,所以运行时,系统需要设立一个工作栈。,83 选择排序,831 简单选择排序,算法思想 假设待排序的数据序列有n个元素,第一趟,比较n个元素,选择关键字最小的元素,跟第一个元素交换;第二趟,在余下的n-1个元素中选择关键字次小的元素与第二个数据交换经过n-1趟排序就完成。 实例,831 简单选择排序,程序实现 Public static void selectsort(int index) Int I,j,k; /循环计数变量 Int minvalue; /最小值变量 Int intdexmin; /最小值下标变量 Int temp; /暂存变量 For(i=o;iindex -1;i+)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 JAVA
链接地址:https://www.31doc.com/p-3185597.html