目录
一、冒泡排序
1.冒泡排序介绍
2.排序的思路
3.完整代码
二、折半查找
1.折半查找介绍
2.查找的思路
3.完整代码
三、逆序数组
1.逆序思路
2..完整代码
一、冒泡排序
冒泡排序是众多排序的一种,无论在C语言或者Java中都很常见,后续在数据结构中也会用到
1.冒泡排序介绍
(1)冒泡排序思想
- 为两两排序,每次的排序后,最大(或最小的)就会升起到最后
- 每完成一轮排序,需要比较的数就少一个
(2)冒泡排序场景
- 多用于对数组内容的排序
2.排序的思路
(1)完成排序需要的内容
- 有数组
- 需要求数组长度
(2)排序的过程解析
我们将下面数组排序成升序
int[] arr = {10,9,8,7,6,5,4,3,2,1};
- 第一趟冒泡排序:10个数需要比较9次,成功把一个数字排好序
- 第二趟冒泡排序:待排序的数字有9个,所以需要比较的次数是8次
后续的排序趟数是类似的,接下来我们总结一下规律
- 由上图可知:10个数字一共需要比较的趟数是10-1次,也就是(arr.length-1)
- 第一趟排序需要比较的次数为9,第二次是8;与趟数有关系,于是得出下面的代码
int i =0; for (i = 0; i < arr.length-1; i++) { for (int j = 0; j arr[j+1]) {//完成两个数字的交换 int tmp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = tmp;}}}
- 升序的条件是第一个数大于第二个数就要交换;如果是排逆序则是第一个数小于第二个数则需要交换
3.完整代码
import java.util.Arrays;public class Sort{public static void main(String[] args) {//冒泡排序int[] arr = {10,9,8,7,6,5,4,3,2,1};bubbleSort(arr);System.out.println(Arrays.toString(arr));}public static void bubbleSort(int[] arr) {//升序int i =0;for (i = 0; i < arr.length-1; i++) {for (int j = 0; j arr[j+1]) {int tmp = arr[j+1];arr[j+1] = arr[j];arr[j] = tmp;}}}}}
二、折半查找
1.折半查找介绍
(1)折半查找,又称二分查找。
(2)二分查找每次都是从中间位置开始查找,因此称为折半查找(二分查找)
(3)可以进行二分查找的条件
- 数组内的数据必须是有序的
- 若是无序的,可以先将其排成有序
2.查找的思路
(1)方法的参数写法
- 我们规定一下:找到了就返回它的下标位置,否则返回-1
- 需要将数组和需要查找的数据传给下面的方法
public static int binarySearch(int[] arr,int k) { }
(2)查找的内部细节
- 定位下标:定好两头位置,便于找到中间位置
public static int binarySearch(int[] arr,int k) {int left = 0;int right = arr.length-1;}
- 中间数字表示:
int mid = (left+right)/2;
(3)二分查找的过程解析
- 先看代码
public static int binarySearch(int[] arr,int k) {int left = 0;int right = arr.length-1;while(left <= right) {//从中间位置开始找int mid = (left+right)/2;if(k arr[mid]) {//在右边left=mid+1;} else {return mid;}}return -1;}
- 查找过程图解 :第一次查找
- 第二次查找:查找后,right指向10,left和mid都指向8
- 第三、四次查找:找到了就返回mid位置的下标
3.完整代码
public static void main(String[] args) {//1.折半查找,要求数组内容为有序.找到了返回下标int[] arr1 = {2,5,7,8,10,11,15,17,20,22};int ret = binarySearch(arr1,10);System.out.println(ret);//2.当数组无序时,使用Array.sort排序后折半查找int[] arr2 = {9,8,7,6,5,4,3,2,1,0};Arrays.sort(arr2);System.out.println(Arrays.toString(arr2));int cur = binarySearch(arr2,11);System.out.println(cur);}public static int binarySearch(int[] arr,int k) {int left = 0;int right = arr.length-1;while(left <= right) {//从中间位置开始找int mid = (left+right)/2;if(k arr[mid]) {//在右边left=mid+1;} else {return mid;}}return -1;}
三、逆序数组
1.逆序思路
(1)要求将数组内容逆序,不是逆序打印
int[] arr = {10,9,8,7,6,5,4,3,2,1,0};
(2)设置头尾位置
public static void reverse(int[] arr) {int left = 0;//头位置int right =arr.length-1;//尾位置 }
这样是为了从两头开始交换数据
(3)循环交换数据
while(left < right) {//相等的时候就不需要逆序了int tmp = arr[left];arr[left] = arr[right];arr[right] = tmp;left++;right--;}
内部代码其实就是实现两个数的交换;当left==right的时候,就是只剩下一个数据没有完成交换了,其实也就不需要再交换了(非要交换也行)
2..完整代码
public static void main(String[] args) {//逆序数组int[] arr = {10,9,8,7,6,5,4,3,2,1,0};reverse(arr);System.out.println(Arrays.toString(arr));}public static void reverse(int[] arr) {int left = 0;int right =arr.length-1;while(left < right) {//相等的时候就不需要逆序了int tmp = arr[left];arr[left] = arr[right];arr[right] = tmp;left++;right--;}}