新网站做内链,雅虎网站收录提交入口,深圳网站开发的公司电话,网站建设佰金手指科杰六一、数组排序【冒泡排序】#xff08;优化#xff09;
1.基本实现思路: 数组排序是通过冒泡排序算法实现的#xff0c;基本实现思路是比较相邻的元素#xff0c;把小的元素往前移动或把大的元素往后移动#xff0c;相邻元素两两进行比较#xff0c;若大元素在小元素前面…一、数组排序【冒泡排序】优化
1.基本实现思路: 数组排序是通过冒泡排序算法实现的基本实现思路是比较相邻的元素把小的元素往前移动或把大的元素往后移动相邻元素两两进行比较若大元素在小元素前面则发生交换(通过^异或运算实现)或者小元素在大元素后面则发生交换若两个元素相等则不交换。 冒泡排序口诀 /* * N个数字来排序 * 两两比较小大靠前 * 总共比较N-1轮 每轮 * 比较N-1-i次 */ 2.代码实现
冒泡排序
1int类型的数组
package com.ztt.exercise.Demo03;import java.util.Arrays;//冒泡排序/** N个数字来排序* 两两比较小大靠前* 总共比较N-1轮 每轮* 比较N-1-i次*/public class demo01 {public static void main(String[] args) {//无序数组int[] numbers {1,9,6,7,2,8};System.out.println(排序前Arrays.toString(numbers));int counter0;//比较n-1轮for(int i0,nnumbers.length;in-1;i) {//是否已经处于“有序”状态//true代表有序//false代表无序boolean isSortedtrue;//每轮比较n-1-i次for(int k0;kn-1-i;k) {counter;//相邻元素比较 交换使用异或运算 两两异或 进行三次if(numbers[k]numbers[k1]) {numbers[k]numbers[k]^numbers[k1];numbers[k1]numbers[k]^numbers[k1];numbers[k]numbers[k]^numbers[k1];isSorted false;}}if(isSorted) {break;}}System.out.println(优化后总共比较了counter次);System.out.println(排序后Arrays.toString(numbers));}}输出结果
排序前[1, 9, 6, 7, 2, 8]
优化后总共比较了14次
排序后[1, 2, 6, 7, 8, 9]
2char类型的数组
package com.ztt.exercise.Demo03;import java.util.Arrays;public class demo02 {public static void main(String[] args) {char[] arr {a,c,e,d,f,j,g};System.out.println(排序前Arrays.toString(arr));int counter0;//比较n-1轮for(int i0 ,narr.length;in-1;i) {boolean isSortedtrue;//每轮比较n-1-i次for(int k0;kn-1-i;k) {counter;//相邻元素比较 交换if(arr[k]arr[k1]) {arr[k](char)(arr[k]^arr[k1]);arr[k1](char)(arr[k]^arr[k1]);arr[k](char)(arr[k]^arr[k1]);isSortedfalse;}}if(isSorted) {break;}}System.out.println(优化后总共比较了counter次);System.out.println(排序后Arrays.toString(arr));}}输出结果
排序前[a, c, e, d, f, j, g]
优化后总共比较了11次
排序后[a, c, d, e, f, g, j]
3String类型的数组
package com.ztt.exercise.Demo03;import java.util.Arrays;public class demo03 {public static void main(String[] args) {String[] names {tian,lucy,bill,herry,deal,candy};System.out.println(排序前Arrays.toString(names));int counter0;//比较n-1轮for(int i0,nnames.length;in-1;i) {boolean isSortedtrue;//每轮比较n-1-i次for(int k0;kn-1-i;k) {counter;//相邻元素比较 交换if(names[k].compareTo(names[k1])0) {String tempnames[k];names[k]names[k1];names[k1]temp;isSortedfalse;}}if(isSorted) {break;}}System.out.println(优化后总共比较了counter次);System.out.println(排序后Arrays.toString(names));}}输出结果
排序前[tian, lucy, bill, herry, deal, candy]
优化后总共比较了15次
排序后[bill, candy, deal, herry, lucy, tian]
通过Arrays工具类的sort()方法
package com.ztt.exercise.Demo03;import java.util.Arrays;public class demo04 {public static void main(String[] args) {// 通过Arrays工具类的sort()方法char[] arr {l,k,j,h,g,f,d,s,a};System.out.println(arr);Arrays.sort(arr);System.out.println(arr);}}
输出结果
lkjhgfdsa
adfghjkls二、无序数组查找
1.基本实现思路: 无序数组查找是通过双指针查找实现的基本实现思路是使用for循环通过两个下标分别从数组的头部和尾部遍历该无序数组将数组中的每个元素与指定元素进行比较从而确定该数组中是否存在目标元素。查找到了返回该元素在数组中所在的下标没有查找到返回-1。 2.代码实现
package com.ztt.exercise.Demo03;import java.util.Scanner;public class demo05 {public static void main(String[] args) {// “无序数组”中指定元素的查找//双指针int[] array {28,12,89,73,65,18,12,96,50,8,36};try (Scanner input new Scanner(System.in)){int target input.nextInt();//目标元素int index-1;//目标元素下标默认为-1代表不存在//案例1查找在“无序数组”中目标元素第一次出现的位置for(int i0;iarray.length;i) {if(array[i]target) {indexi;break;}}//案例2查找在“无序数组”中目标元素最后一次出现的位置//方式1从头部开始遍历依次查找for(int i0;iarray.length;i) {if(array[i]target) {indexi;}}//方式2从尾部开始遍历依次查找for(int iarray.length-1;i0;i--) {if(array[i]target) {indexi;break;}}System.out.printf(元素%d的下标是%d,target,index); }}}package com.ztt.exercise.Demo03;import java.util.Scanner;public class demo06 {public static void main(String[] args) {// 查找String[] singerArray { 李荣浩, 盘尼西林, 王菲, 王贰浪, 鹿先森乐队, 孙燕姿, G.E.M.邓紫棋, 方大同, 品冠儿子 };try (Scanner input new Scanner(System.in)){String target input.next();int index-1;for(int i0,ksingerArray.length-1;ik;i,k--) {//从头开始比较//String字符串的等值比较必须用equalsif(singerArray[i].equals(target)) {indexi;break;}//从尾部开始比较if(singerArray[k].equals(target)) {indexk;break;}}System.out.println(index); }}
}
输出结果
73
元素73的下标是36
元素6的下标是-1王贰浪
3张甜甜
-1
三、有序数组查找二分查找
1.基本实现思路: 有序数组查找是通过二分查找Binary Search算法实现的二分查找算法的基本实现思路是 定义一个有序的数组以及要查找的目标整数 target。 初始化 index 为 -1用于存储找到的目标元素的下标数组的起始下标 low0 和 结束下标 high numbers.length - 1。 使用 while 循环条件是 low high。这意味着只要搜索区间不为空就继续查找。 在每次循环中计算中间位置 mid它是 low 和 high 的平均值向下取整。 使用 if-else 语句判断中间位下标的元素是否与目标元素相等如果 中间位置的元素 target则找到了目标元素将 index 设置为 mid 并break跳出循环。 如果 中间位置的元素 target则目标元素在 mid 的右侧更新 low 为 mid 1。 如果 中间位置的元素 target则目标元素在 mid 的左侧更新 high 为 mid - 1。 循环结束后输出 index。如果找到了目标元素index 将是目标元素在数组中的下标如果没有找到index 将为 -1。 2.代码实现
二分查找
1int类型的数组
package com.ztt.exercise.Demo03;public class demo07 {public static void main(String[] args) {//二分查找算法int[] numbers {1,2,3,4,5,6,7,8,9};int target3;int index-1;//数组的“首”“尾”int low0,highnumbers.length-1;while(lowhigh) {//计算当前位“中间位”下标int mid(lowhigh)/2;//判断中间位下标的元素是否与目标元素相等if(numbers[mid]target) {indexmid;break;}else if(numbers[mid]target){lowmid1;}else if(numbers[mid]target) {highmid-1;}}System.out.println(index);}}输出结果
2
2char类型的数组
package com.ztt.exercise.Demo03;public class demo08 {public static void main(String[] args) {char[] keys { a, b, c, d, e, f, g, h, i, j, k, l, m, n };char targeth;int index-1;int low0,highkeys.length-1;while(lowhigh) {int mid(lowhigh)/2;if(keys[mid]target) {indexmid;break;}else if(keys[mid]target){highmid-1;}else if(keys[mid]target) {lowmid1;}}System.out.println(index);}}
输出结果
73String类型的数组
package com.ztt.exercise.Demo03;import java.util.Arrays;public class demo09 {public static void main(String[] args) {String[] contactArray { egatron,s司马铁锤,s司马铁锤,Laden, angelababy,b比尔盖饭,l林平之,BIGBANG , Adele Adkins, m马云,Gaddafi, g郭德纲,m马伯庸,Ma Tong Seok};String targetm马云;int index-1;//先排序Arrays.sort(contactArray);System.out.println(Arrays.toString(contactArray));int low0,highcontactArray.length-1;while(lowhigh) {int mid(lowhigh)/2;if(contactArray[mid].compareTo(target)0) {indexmid;break;}else if(contactArray[mid].compareTo(target)0){highmid-1;}else if(contactArray[mid].compareTo(target)0) {lowmid1;}}System.out.println(index);}}输出结果
[Adele Adkins, BIGBANG, Gaddafi, Laden, Ma Tong Seok, angelababy, b比尔盖饭, egatron, g郭德纲, l林平之, m马云, m马伯庸, s司马铁锤, s司马铁锤]
10 通过Arrays工具类的binarySearch()方法
package com.ztt.exercise.Demo03;import java.util.Arrays;public class demo03 {public static void main(String[] args) {int[] array {28,12,89,73,65,18,96,50,8,36};int target36; //目标元素//先排序Arrays.sort(array);System.out.println(Arrays.toString(array));//再查找int indexArrays.binarySearch(array, target);System.out.println(index);}
}
输出结果
[8, 12, 18, 28, 36, 50, 65, 73, 89, 96]
4 四、数组乱序
1.基本实现思路: 数组乱序 的基本实现思路是对一个打乱顺序的数组通过for循环逆序遍历产生随机下标从数组的最后一个元素(数组的长度-1)开始到第二个元素(i0)设置一个随机数作为循环中遍历到的元素之前的所有元素的下标即可从该元素之前的所有元素中随机取出一个每次将随机取出的元素与遍历到的元素交换即可完成乱序 2.代码实现
package com.ztt.exercise.Demo03;import java.util.Arrays;public class demo10 {public static void main(String[] args) {// 乱序排序int[] numbers{11,13,14,16,19};System.out.println(Arrays.toString(numbers));System.out.println();for(int inumbers.length-1; i0;i--) {int index(int)(Math.random()*i);numbers[index]numbers[index]^numbers[i];numbers[i]numbers[index]^numbers[i];numbers[index]numbers[index]^numbers[i];}System.out.println(Arrays.toString(numbers));}}package com.ztt.exercise.Demo03;public class demo11 {
public static void main(String[] args) {String[] playMusicList { 1反方向的钟, 2七里香, 3半岛铁盒, 4双节棍, 5晴天, 6青花瓷, 7一路向北, 8稻香 };for(int iplayMusicList.length-1;i0;i--) {int randIndex(int)(Math.random()*i);String tempplayMusicList[i];playMusicList[i] playMusicList[randIndex];playMusicList[randIndex] temp;}for(String music :playMusicList ) {System.out.println(music);}}}
输出结果
[11, 13, 14, 16, 19][13, 16, 11, 19, 14]6青花瓷
1反方向的钟
8稻香
2七里香
4双节棍
7一路向北
3半岛铁盒
5晴天
五、数组旋转
1.基本实现思路: 数组旋转的基本实现思路是: 向右旋转从数组的尾部开始遍历(逆序遍历)逐步向前移动每次都将当前元素与其前一个元素交换(通过^异或运算实现)直到到达数组的开始位置。这样数组就实现了向右旋转一位的效果。重复旋转由于外层循环执行了3次所以数组总共向右旋转了3位。 向左旋转从数组的头部开始遍历(顺序遍历)逐步向后移动每次都将当前元素与其后一个元素交换(通过^异或运算实现)直到到达数组的结束位置。这样数组就实现了向左旋转一位的效果。重复旋转由于外层循环执行了3次所以数组总共向左旋转了3位。 2.代码实现
1向右旋转
package com.ztt.exercise.Demo03;import java.util.Arrays;public class demo12 {public static void main(String[] args) {// 数组旋转int[] numbers {1,2,3,4,5,6,7};//外层循环控制旋转的位数循环3次代表旋转3次for(int i0; i3;i) {//内层循环控制旋转的方向每次向右旋转1位//向右旋转将尾部元素通过不断交换交换至数组头部//遍历的方向从尾部开始逆序//交换的双方当前元素k 与 前一个元素k-1//每次向右旋转1位for(int knumbers.length-1;k0;k--) {//交换numbers[k]numbers[k]^numbers[k-1];numbers[k-1]numbers[k]^numbers[k-1];numbers[k]numbers[k]^numbers[k-1];}}System.out.println(Arrays.toString(numbers));}}输出结果
[5, 6, 7, 1, 2, 3, 4]2向左旋转
package com.ztt.exercise.Demo03;import java.util.Arrays;public class demo13 {public static void main(String[] args) {// 数组旋转int[] numbers {1,2,3,4,5,6,7};//外层循环控制旋转的位数循环3次代表旋转3次for(int i0; i3;i) {//内层循环控制旋转的方向每次向左旋转1位//向左旋转将头部元素通过不断交换交换至数组尾部//遍历的方向从头部开始顺序//交换的双方当前元素k 与 前一个元素k1//每次向左旋转1位for(int k0;knumbers.length-1;k) {//交换numbers[k]numbers[k]^numbers[k1];numbers[k1]numbers[k]^numbers[k1];numbers[k]numbers[k]^numbers[k1];}}System.out.println(Arrays.toString(numbers));}}输出结果
[4, 5, 6, 7, 1, 2, 3]
