wap网站 什么意思,一个设计公司的简介,东莞地产网站建设,wordpress指定分类投稿阅读本文约需要7分钟大家好#xff0c;我是你们的导师#xff0c;我每天都会在这里给大家分享一些干货内容(当然了#xff0c;周末也要允许老师休息一下哈)。上次老师跟大家分享了下用Navicat for Mysql导入.sql文件的相关知识#xff0c;今天跟大家分享在 各种排序算法的分… 阅读本文约需要7分钟大家好我是你们的导师我每天都会在这里给大家分享一些干货内容(当然了周末也要允许老师休息一下哈)。上次老师跟大家分享了下用Navicat for Mysql导入.sql文件的相关知识今天跟大家分享在 各种排序算法的分析及java实现(一)的知识。参考来源https://www.cnblogs.com/liuling/p/2013-7-24-01.html新的一周又开始了这周也要打起精神好好加油今天我们开始了解排序。排序大的分类可以分为两种内排序和外排序。在排序过程中全部记录存放在内存则称为内排序如果排序过程中需要使用外存则称为外排序。下面讲的排序都是属于内排序。内排序有可以分为以下几类 (1)、插入排序直接插入排序、二分法插入排序、希尔排序。 (2)、选择排序简单选择排序、堆排序。 (3)、交换排序冒泡排序、快速排序。 (4)、归并排序 (5)、基数排序 一、插入排序•思想每步将一个待排序的记录按其顺序码大小插入到前面已经排序的字序列的合适位置直到全部插入排序完为止。•关键问题在前面已经排好序的序列中找到合适的插入位置。•方法–直接插入排序–二分插入排序–希尔排序①直接插入排序(从后向前找到合适位置后插入)1、基本思想每步将一个待排序的记录按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后)直到全部插入排序完为止。2、实例 3、java实现 package com.sort; public class 直接插入排序 { public static void main(String[] args) { int[] a{49,38,65,97,76,13,27,49,78,34,12,64,1}; System.out.println(排序之前); for (int i 0; i a.length; i) { System.out.print(a[i] ); } //直接插入排序 for (int i 1; i a.length; i) { //待插入元素 int temp a[i]; int j; /*for (j i-1; j0 a[j]temp; j--) { //将大于temp的往后移动一位 a[j1] a[j]; }*/ for (j i-1; j0; j--) { //将大于temp的往后移动一位 if(a[j]temp){ a[j1] a[j]; }else{ break; } } a[j1] temp; } System.out.println(); System.out.println(排序之后); for (int i 0; i a.length; i) { System.out.print(a[i] ); } } }4、分析直接插入排序是稳定的排序。关于各种算法的稳定性分析可以参考http://www.cnblogs.com/Braveliu/archive/2013/01/15/2861201.html文件初态不同时直接插入排序所耗费的时间有很大差异。若文件初态为正序则每个待插入的记录只需要比较一次就能够找到合适的位置插入故算法的时间复杂度为O(n)这时最好的情况。若初态为反序则第i个待插入记录需要比较i1次才能找到合适位置插入故时间复杂度为O(n2)这时最坏的情况。直接插入排序的平均时间复杂度为O(n2)。②二分法插入排序(按二分法找到合适位置插入) 1、基本思想二分法插入排序的思想和直接插入一样只是找合适的插入位置的方式不同这里是按二分法找到合适的位置可以减少比较的次数。 2、实例 3、java实现 package com.sort; public class 二分插入排序 { public static void main(String[] args) { int[] a{49,38,65,97,176,213,227,49,78,34,12,164,11,18,1}; System.out.println(排序之前); for (int i 0; i a.length; i) { System.out.print(a[i] ); } //二分插入排序 sort(a); System.out.println(); System.out.println(排序之后); for (int i 0; i a.length; i) { System.out.print(a[i] ); } } private static void sort(int[] a) { for (int i 0; i a.length; i) { int temp a[i]; int left 0; int right i-1; int mid 0; while(leftright){ mid (leftright)/2; if(temp right mid-1; }else{ left mid1; } } for (int j i-1; j left; j--) { a[j1] a[j]; } if(left ! i){ a[left] temp; } } } } 4、分析 当然二分法插入排序也是稳定的。二分插入排序的比较次数与待排序记录的初始状态无关仅依赖于记录的个数。当n较大时比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序算法的相同最坏的情况为n2/2最好的情况为n平均移动次数为O(n2)。③希尔排序 1、基本思想先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序。然后取第二个增量d2 2、实例 3、java实现 package com.sort; //不稳定 public class 希尔排序 { public static void main(String[] args) { int[] a{49,38,65,97,76,13,27,49,78,34,12,64,1}; System.out.println(排序之前); for (int i 0; i a.length; i) { System.out.print(a[i] ); } //希尔排序 int d a.length; while(true){ d d / 2; for(int x0;x for(int ixd;i int temp a[i]; int j; for(ji-d;j0a[j]temp;jj-d){ a[jd] a[j]; } a[jd] temp; } } if(d 1){ break; } } System.out.println(); System.out.println(排序之后); for (int i 0; i a.length; i) { System.out.print(a[i] ); } } } 4、分析我们知道一次插入排序是稳定的但在不同的插入排序过程中相同的元素可能在各自的插入排序中移动最后其稳定性就会被打乱所以希尔排序是不稳定的。希尔排序的时间性能优于直接插入排序原因如下(1)当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。(2)当n值较小时n和n2的差别也较小即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。(3)在希尔排序开始时增量较大分组较多每组的记录数目少故各组内直接插入较快后来增量di逐渐缩小分组数逐渐减少而各组的记录数目逐渐增多但由于已经按di-1作为距离排过序使文件较接近于有序状态所以新的一趟排序过程也较快。因此希尔排序在效率上较直接插人排序有较大的改进。希尔排序的平均时间复杂度为O(nlogn)。二、选择排序•思想每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置直到全部排完。•关键问题在剩余的待排序记录序列中找到最小关键码记录。•方法–直接选择排序–堆排序①简单的选择排序 1、基本思想在要排序的一组数中选出最小的一个数与第一个位置的数交换然后在剩下的数当中再找最小的与第二个位置的数交换如此循环到倒数第二个数和最后一个数比较为止。 2、实例 3、java实现 package com.sort; //不稳定 public class 简单的选择排序 { public static void main(String[] args) { int[] a{49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println(排序之前); for (int i 0; i a.length; i) { System.out.print(a[i] ); } //简单的选择排序 for (int i 0; i a.length; i) { int min a[i]; int ni; //最小数的索引 for(int ji1;j if(a[j] min a[j]; n j; } } a[n] a[i]; a[i] min; } System.out.println(); System.out.println(排序之后); for (int i 0; i a.length; i) { System.out.print(a[i] ); } } } 4、分析 简单选择排序是不稳定的排序。 时间复杂度T(n)O(n2)。②堆排序 1、基本思想堆排序是一种树形选择排序是对直接选择排序的有效改进。堆的定义下具有n个元素的序列 (h1,h2,...,hn),当且仅当满足(hih2i,hi2i1)或(hih2i,hi2i1) (i1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二 叉树可以很直观地表示堆的结构。堆顶为根其它为左子树、右子树。思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树调整它们的存储序使之成为一个 堆这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推直到只有两个节点的堆并对 它们作交换最后得到有n个节点的有序序列。从算法描述来看堆排序需要两个过程一是建立堆二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数二是反复调用渗透函数实现排序的函数。 2、实例初始序列46,79,56,38,40,84建堆 交换从堆中踢出最大数依次类推最后堆中剩余的最后两个结点交换踢出一个排序完成。 3、java实现 package com.sort; //不稳定 import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] a{49,38,65,97,76,13,27,49,78,34,12,64}; int arrayLengtha.length; //循环建堆 for(int i0;i //建堆 buildMaxHeap(a,arrayLength-1-i); //交换堆顶和最后一个元素 swap(a,0,arrayLength-1-i); System.out.println(Arrays.toString(a)); } } //对data数组从0到lastIndex建大顶堆 public static void buildMaxHeap(int[] data, int lastIndex){ //从lastIndex处节点(最后一个节点)的父节点开始 for(int i(lastIndex-1)/2;i0;i--){ //k保存正在判断的节点 int ki; //如果当前k节点的子节点存在 while(k*21lastIndex){ //k节点的左子节点的索引 int biggerIndex2*k1; //如果biggerIndex小于lastIndex即biggerIndex1代表的k节点的右子节点存在 if(biggerIndex //若果右子节点的值较大 if(data[biggerIndex] //biggerIndex总是记录较大子节点的索引 biggerIndex; } } //如果k节点的值小于其较大的子节点的值 if(data[k] //交换他们 swap(data,k,biggerIndex); //将biggerIndex赋予k开始while循环的下一次循环重新保证k节点的值大于其左右子节点的值 kbiggerIndex; }else{ break; } } } } //交换 private static void swap(int[] data, int i, int j) { int tmpdata[i]; data[i]data[j]; data[j]tmp; } } 4、分析堆排序也是一种不稳定的排序算法。堆排序优于简单选择排序的原因直接选择排序中为了从R[1..n]中选出关键字最小的记录必须进行n-1次比较然后在R[2..n]中选出关键字最小的记录又需要做n-2次比较。事实上后面的n-2次比较中有许多比较可能在前面的n-1次比较中已经做过但由于前一趟排序时未保留这些比较结果所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果可减少比较次数。堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多所以堆排序不适宜于记录数较少的文件。今天就分享这么多关于各种排序算法的分析及java实现(一)你学会了多少欢迎在留言区评论对于有价值的留言我们都会一一回复的。如果觉得文章对你有一丢丢帮助请点右下角【在看】让更多人看到该文章。如果有想了解的也可以进行留言
