制作网站用什么软件有哪些,公司禁用网站怎么做,电子商务网站的开发流程,seo最新教程一、简单选择排序 1、思想#xff1a;每遍历一次都记住了当前最小#xff08;大#xff09;元素的位置#xff0c;最后仅需一次交换操作即可将其放到合适的位置。与冒泡排序相比#xff0c;移动数据次数少#xff0c;节省时间 #xff0c;性能优于冒泡排序。 2、时间复杂…一、简单选择排序 1、思想每遍历一次都记住了当前最小大元素的位置最后仅需一次交换操作即可将其放到合适的位置。与冒泡排序相比移动数据次数少节省时间 性能优于冒泡排序。 2、时间复杂度 最好ON2正序 最坏ON2 平均ON2 3、辅助空间O1 4、稳定性不稳定交换过程中可能打乱顺序 5、适用场合n小的情况 public static void selectSort(int[] a) {int i,j,min,t;for(j 0;j a.length; j) {min a[j];//将待排序的第一个元素设置为最小值t j; //设置要交换的位置for(i j1;i a.length; i) {if (min a[i]) {min a[i];t i;}}if (t ! j) swap(a,j,t);//若不为当前位置则交换}} 二、堆排序 1、思想堆排序是一种选择排序整体主要由构建初始堆交换堆顶元素和末尾元素并重建堆两部分组成。选择排序主要是比较的次数多所以从减少比较次数入手来改进选择排序堆排序利用了完全二叉树的性质当前结点i的子节点为2i,2i1例如大根堆则当前结点一定大于或等于其任何子节点。 2、时间复杂度初始建堆On交换堆顶和末尾元素并重建logn 最好Onlogn 最坏Onlogn 平均Onlogn 3、辅助空间O1 4、稳定性不稳定 1 import java.util.Scanner;2 3 public class HeapSort {4 //堆下标从1开始5 //从当前给定的点s开始往下调整6 //大顶堆得到递增数组7 public static void adjustHeap(int[] a,int s,int len ) {8 int rc,i;9 rc a[s];
10 for(i s*2 ; i len ; i i*2 ) {
11 if(i len a[i]a[i1]) i;//取s的两个子节点中较大一个
12 if(rc a[i]) break;//将rc和当前较大的子节点比较若大则不需再往下调整
13 a[s] a[i];//取较大子节点移动到s
14 s i;//s变为移动后的位置,向下调整
15 }
16 a[s] rc;//最后将rc放到相应位置
17 }
18
19 public static void heapSort(int[] a) {
20 int i,tmp;
21 for(i (a.length-1)/2;i 0; i--)
22 adjustHeap(a, i, a.length-1);
23 for(i a.length-1; i 1;i--) {
24 tmp a[1];
25 a[1] a[i];
26 a[i] tmp;
27 adjustHeap(a, 1, i-1);
28 }
29 }
30
31 public static void insertHeap(int[] a,int x) {
32 int c a.length - 1,temp,f;
33 a[c] x;
34 temp a[c];//当前要插入的结点
35 f c/2;//父节点
36 while(f1 c ! 1) {
37 if(temp a[f]) break;
38 a[c] a[f];//若当前结点大于父节点则将父节点往下调整
39 c f;
40 f c/2;
41 }
42 a[c] temp;
43
44 }
45 public static void main(String[] args) {
46 int[] a new int[10];
47 Scanner cin new Scanner(System.in);
48 int i0;
49 while(ia.length) {
50 a[i] cin.nextInt();
51 i;
52 }
53 heapSort(a);
54 //insertHeap(a, 886);
55 for(i 1;i a.length;i) {
56 System.out.print(a[i] );
57 }
58 }
59 } 三、总结 1、堆排序是简单选择排序的一种改进改进的着眼点是如何减少关键码的比较次数。 2、简单选择排序在一趟排序中仅选出最小关键码没有把一趟比较结果保存下来因而记录的比较次数较多。 堆排序在选出最小关键码的同时也找出较小关键码减少了在后面的选择中的比较次数从而提高了整个排序的效率。 3、堆排序对原始记录的排列状态并不敏感相对于快速排序这是堆排序最大的优点。转载于:https://www.cnblogs.com/lizijiangmm/p/8649030.html
