排序和查找

2017/01/03 Java

排序

冒泡排序

相邻元素两两比较,大的往后放,第一次完毕,最大值出现在了最大索引处。同理,其他的元素就可以排好。

public static void bubbleSort(int[] arr) {
	for(int i=0; i<arr.length-1; i++) {
		for(int j=0; j<arr.length-1-i; j++) {
			if(arr[j] > arr[j+1]) {
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

冒泡排序原理图解

选择排序

把0索引的元素,和索引1以后的元素都进行比较,第一次完毕,最小值出现在了0索引。同理,其他的元素就可以排好。

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[j] < arr[i]) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

选择排序原理图解

查找

基本查找

针对数组无序的情况

public static int getIndei(int[] arr,int value) {
	int indei = -1;
	
	for(int i=0; i<arr.length; i++) {
		if(arr[i] == value) {
			indei = i;
			break;
		}
	}
	
	return indei;
}

二分查找(折半查找)

针对数组有序的情况

千万不要先排序,再查找,因为查找到的索引和原来的索引已经不是同一索引了

//Jdk源码
private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1; 
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1; 
        else if (midVal > key)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}

二分查找原理图解


以上概念总结于传智播客Java基础课程

Search

    Post Directory