操作数组的常用方式二-----排序、查找

秒速五厘米 2022-06-16 09:20 228阅读 0赞

/**
     * 操作数组的常用方式
     */
    public class ArrayDemo {
    
    	public static void main(String[] args) {
    
    		int[] arr = new int[] { 1, 3, 10, 2, 5, 7, 8 };
    
    		// 排序前
    		System.out.println("--------------------排序前--------------------");
    		printArray(arr);
    		// 选择排序
    		// selectSort(arr);
    		// 冒泡排序
    		bubbleSort(arr);
    		System.out.println("--------------------排序后--------------------");
    		printArray(arr);
    		
    		// 普通查找法
    		System.out.println(arrayIndexOf(arr, 10));
    		//二分法查找方式1
    		System.out.println(searchElIndex(arr, 5));
    		//二分法查找方式2
    		System.out.println(searchElIndex2(arr, 5));
    
    	}
    
    	/**
    	 * 选择排序（每一轮将第一个元素和数组中的每个元素进行比较）
    	 * @param arr 待排序的数组
    	 */
    	public static void selectSort(int[] arr) {
    		for (int i = 0; i < arr.length - 1; i++) {
    			for (int j = i + 1; j < arr.length; j++) {
    				if (arr[i] > arr[j]) {
    					/*
    					 * 调换元素的位置 方式1：使用临时变量
    					 */
    					/*int temp = arr[i];
    					arr[i] = arr[j];
    					arr[j] = temp;*/
    
    					/*
    					 * 方式2，将相比的两数做加减运算。
    					 * 如：int[] arr = {2,1}; 
    					 * arr[0] = arr[0] + arr[1]; ==》3=2+1; 
    					 * arr[1] = arr[0] - arr[1]; ==》2=3-1;
    					 * arr[0] = arr[0] - arr[j]; ==》1=3-2;
    					 */
    					/*arr[i] = arr[i] + arr[j];
    					arr[j] = arr[i] - arr[j];
    					arr[i] = arr[i] - arr[j];*/
    
    					swap(arr, i, j);
    				}
    			}
    		}
    	}
    
    	/**
    	 * 冒泡排序（两个相邻的数进行比较）
    	 * @param arr 待排序的数组
    	 */
    	public static void bubbleSort(int[] arr) {
    		for (int i = 0; i < arr.length - 1; i++) { // 控制比较的次数
    			for (int j = 0; j < arr.length - i - 1; j++) { // -i:比较的元素减少  -1:为了避免抛ArrayIndexOutOfBoundsException
    				if (arr[j] > arr[j + 1]) {
    					/*int temp = arr[j];
    					arr[j] = arr[j + 1];
    					arr[j + 1] = temp;*/
    					
    					swap(arr, j, j+1);
    					
    				}
    			}
    		}
    	}
    	
    	/**
    	 * 将数组中的两个元素交换位置
    	 * @param arr 待交换元素位置的数组
    	 * @param index1 元素下标1
    	 * @param index2 元素下标2
    	 */
    	public static void swap(int[] arr, int index1, int index2) {
    		int temp = arr[index1];
    		arr[index1] = arr[index2];
    		arr[index2] = temp;
    	}
    	
    	/**
    	 * 二分法查找一个元素在数组中的下标
    	 * @param arr 数组
    	 * @param key 要查找的元素
    	 * @return 找到返回元素在数组中的下标，没找到则返回-1
    	 */
    	public static int searchElIndex(int[] arr, int key) {
    		int min,max,mid;
    		min = 0;
    		max = arr.length - 1;
    		mid = (min + max) / 2;
    		
    		while (arr[mid] != key) {
    			if (key > arr[mid]) {
    				min = mid + 1;
    			} else if (key < arr[mid]) {
    				max = mid - 1;
    			} 
    			
    			if (min > max) 
    				return -1; 
    			
    			mid = (min + max) / 2;
    		}
    		
    		return mid;
    	}
    	
    	/**
    	 * 二分法查找一个元素在数组中的下标
    	 * @param arr 数组
    	 * @param key 要查找的元素
    	 * @return 找到返回元素在数组中的下标，没找到则返回-1
    	 */
    	public static int searchElIndex2(int[] arr, int key) {
    		int min,max,mid;
    		min = 0;
    		max = arr.length - 1;
    		
    		while (min <= max) {
    			
    			mid = (min + max) >> 1;
    			
    			if (key > arr[mid]) {
    				min = mid + 1;
    			} else if (key < arr[mid]) {
    				max = mid - 1;
    			} else {
    				return mid;
    			}
    		}
    		
    		return -1;
    	}
    	
    	/**
    	 * 查找一个元素在数组中的位置，该函数可以查找未经排序数组的第一个元素所在数组中的下标
    	 * @param arr 查找的数组
    	 * @param key 查找的元素
    	 * @return 如果找到则返回该元素在数组中的下标，没找到则返回-1
    	 */
    	public static int arrayIndexOf(int[] arr, int key) {
    		for(int i = 0; i < arr.length; i++) {
    			if (arr[i] == key) 
    				return i;
    		}
    		return -1;
    	}
    
    	/**
    	 * 打印数组
    	 * @param arr 待打印的数组
    	 */
    	public static void printArray(int[] arr) {
    		System.out.print("[");
    		for (int i = 0; i < arr.length; i++) {
    			if (i < arr.length - 1) {
    				System.out.print(arr[i] + ",");
    			} else {
    				System.out.print(arr[i]);
    			}
    		}
    		System.out.println("]");
    	}
    
    }