中国做的儿童编程网站,厦门市建设局网站,宁夏建设厅网站,做网站需要招聘内容范本冒泡排序是非常好理解的#xff0c;以从小到大排序为例#xff0c;每一轮排序就找出未排序序列中最大值放在最后。设数组的长度为N#xff1a;(1)比较前后相邻的二个数据#xff0c;如果前面数据大于后面的数据#xff0c;就将这二个数据交换。(2)这样对数组的第0个数据到…冒泡排序是非常好理解的以从小到大排序为例每一轮排序就找出未排序序列中最大值放在最后。设数组的长度为N(1)比较前后相邻的二个数据如果前面数据大于后面的数据就将这二个数据交换。(2)这样对数组的第0个数据到N-1个数据进行一次遍历后最大的一个数据就“沉”到数组第N-1个位置。(3)NN-1如果N不为0就重复前面二步否则排序完成。以上就是冒泡排序的基本思想按照这个定义很快就能写出代码/*** 冒泡排序的第一种实现, 没有任何优化*param a*param n*/public static void bubbleSort1(int [] a, int n){int i, j;for(i0; ifor(j1; jif(a[j-1] a[j]){//前面的数字大于后面的数字就交换//交换a[j-1]和a[j]int temp;temp a[j-1];a[j-1] a[j];a[j]temp;}}}}// end给出一个测试代码public static void main(String[] args) {int[] arr {1,1,2,0,9,3,12,7,8,3,4,65,22};BubbleSort.bubbleSort1(arr, arr.length);for(int i:arr){System.out.print(i,);}}运行结果0,1,1,2,3,3,4,7,8,9,12,22,65,下面开始考虑优化如果对于一个本身有序的序列或则序列后面一大部分都是有序的序列上面的算法就会浪费很多的时间开销这里设置一个标志flag如果这一趟发生了交换则为true否则为false。明显如果有一趟没有发生交换说明排序已经完成。/*** 设置一个标志如果这一趟发生了交换则为true否则为false。明显如果有一趟没有发生交换说明排序已经完成。*param a*param n*/public static void bubbleSort2(int [] a, int n){int j, k n;boolean flag true;//发生了交换就为true, 没发生就为false第一次判断时必须标志位true。while (flag){flagfalse;//每次开始排序前都设置flag为未排序过for(j1; jif(a[j-1] a[j]){//前面的数字大于后面的数字就交换//交换a[j-1]和a[j]int temp;temp a[j-1];a[j-1] a[j];a[j]temp;//表示交换过数据;flag true;}}k--;//减小一次排序的尾边界}//end while}//end运行测试main函数结果0,1,1,2,3,3,4,7,8,9,12,22,65,再进一步做优化。比如现在有一个包含1000个数的数组仅前面100个无序后面900个都已排好序且都大于前面100个数字那么在第一趟遍历后最后发生交换的位置必定小于100且这个位置之后的数据必定已经有序了也就是这个位置以后的数据不需要再排序了于是记录下这位置第二次只要从数组头部遍历到这个位置就可以了。如果是对于上面的冒泡排序算法2来说虽然也只排序100次但是前面的100次排序每次都要对后面的900个数据进行比较而对于现在的排序算法3只需要有一次比较后面的900个数据之后就会设置尾边界保证后面的900个数据不再被排序。public static void bubbleSort3(int [] a, int n){int j , k;int flag n ;//flag来记录最后交换的位置也就是排序的尾边界while (flag 0){//排序未结束标志k flag; //k 来记录遍历的尾边界flag 0;for(j1; jif(a[j-1] a[j]){//前面的数字大于后面的数字就交换//交换a[j-1]和a[j]int temp;temp a[j-1];a[j-1] a[j];a[j]temp;//表示交换过数据;flag j;//记录最新的尾边界.}}}}这种方法是我看到的最优化的冒泡排序了。运行测试例子结果0,1,1,2,3,3,4,7,8,9,12,22,65,1可知运行结果正确。
