冒泡排序，选择排序，快速排序，堆排序与二分查找算法

拼搏现实的明天。 2022-08-18 00:55 204阅读 0赞

public class Test {
    
    	public static void main(String[] args) {
    		int arr[] = { 5, 2, 3, 1, 4, -4, 6, 2 };
    		// arr = sort1(arr);
    		// arr = sort2(arr);
    		//arr = sort3(arr, 0, arr.length - 1);
    		arr = sort4(arr);
    		for (int i = 0; i < arr.length; i++) {
    			System.out.println(arr[i]);
    		}
    		System.out.println("下标是:" + binarySearch(arr, 1));
    	}
    
    	// 冒泡排序
    	public static int[] sort1(int[] arr) {
    		for (int i = 0; i < arr.length - 1; i++) {
    			for (int j = 0; j < arr.length - i - 1; j++) {
    				if (arr[j] > arr[j + 1]) {
    					int temp = arr[j];
    					arr[j] = arr[j + 1];
    					arr[j + 1] = temp;
    				}
    			}
    		}
    		return arr;
    	}
    
    	// 选择排序
    	public static int[] sort2(int[] arr) {
    		for (int i = 0; i < arr.length; i++) {
    			int min = i;
    			for (int j = i + 1; j < arr.length; j++) {
    				if (arr[min] > arr[j]) {
    					min = j;
    				}
    			}
    			if (i != min) {
    				int temp = arr[min];
    				arr[min] = arr[i];
    				arr[i] = temp;
    			}
    		}
    		return arr;
    	}
    
    	// 快速排序
    	public static int[] sort3(int arr[], int l, int r) {
    		if (l < r) {
    			int i = l, j = r, x = arr[l];
    			while (i < j) {
    				while (i < j && arr[j] >= x) {// 从向左找出第一个小于x的数并交换
    					j--;
    				}
    				if (i < j) {
    					arr[i++] = arr[j];
    
    				}
    				while (i < j && arr[i] < x) {
    					i++;
    				}
    				if (i < j) {
    					arr[j--] = arr[i];
    				}
    			}
    			arr[i] = x;
    			sort3(arr, l, i - 1);
    			sort3(arr, i + 1, r);
    		}
    		return arr;
    	}
    
    	// 堆排序
    	//3.交换
    	public static void swap(int i, int j, int[] arr) { 
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    
    	//2.排序
    	public static int[] sort4(int arr[]) {
    		for (int i = 0; i < arr.length - 1; i++) {
    			buildMaxHeap(arr, arr.length - i - 1);
    			swap(0, arr.length - i - 1, arr);
    		}
    		return arr;
    	}
    
    	//1.构建最大堆
    	public static void buildMaxHeap(int[] array, int lastIndex) {
    		for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
    			// 记录当前的节点
    			int k = i;
    			// 说明有左孩子
    			while (2 * k + 1 <= lastIndex) {
    				int bigIndex = 2 * k + 1;
    				// 说明有右孩子
    				if (bigIndex < lastIndex) {
    					if (array[bigIndex] < array[bigIndex + 1]) {
    						bigIndex++;
    					}
    				}
    				if (array[bigIndex] > array[i]) {
    					swap(k, bigIndex, array);
    					k = bigIndex;
    				} else {
    					break;
    				}
    			}
    		}
    	}
    
    	// 二分查找
    	public static int binarySearch(int arr[], int v) {
    		int l = 0;
    		int r = arr.length - 1;
    		while (l < r) {
    			int m = (l + r) / 2;
    			if (arr[m] == v) {
    				return m;
    			} else if (arr[m] < v) {
    				l = m + 1;
    			} else if (arr[m] > v) {
    				r = m - 1;
    			}
    		}
    		return -1;
    	}
    
    }