插值查找

前提是数据有顺序

	int[] list = {7,23,79,81,103,127,131,147};  
	int l = 0;  
	int r = list.length - 1;  
	int x = sc.nextInt();  
	int mid;
	while (l <= r && x >= list[l] && x <= list[r]) {
	// 先乘后除
		mid = l + (x - list[l]) * (r - l) / (list[r] - list[l]);

		if (x == list[mid]) {
			System.out.println("找到了，索引为：" + mid);
			break;
		} else if (x > list[mid]) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}

插值查找优点：对于均匀分布的数组，速度极快（时间复杂度接近 $O(\log(\log n))$）。
插值查找缺点：如果数据分布极不均匀（比如：{1, 2, 3, 100, 1000, 10000}），插值查找的性能可能还不如二分查找。

冒泡排序

相邻的数据两两比较
if(a[i] > [j]) swap(a[i],a[j])

选择排序

从0索引开始，拿着每一个索引上的元素跟后面的元素一一比较，小的放前面，大的放后面。
第一轮循环，确定确定了最小元素

插入排序

分为有序组和无序组
将无序组逐个插入有序组中

public class TestDemo {  
    public static void main(String[] args) {  
        int[] arr = {4,16,5,9,12,21,18,  
                32,23,37,26,45,34,  
                50,48,61,52,73,66};  
        int startIndex = -1;  
        for (int i = 0; i < arr.length; i++) {  
            if(arr[i] > arr[i+1]){  
                startIndex = i + 1;  
                break;  
            }  
        }  
        if(startIndex == -1){  
            return ;  
        }  
        for(int i = startIndex; i < arr.length; i++){  
            int  j = i;  
            while(j > 0 && arr[j] < arr[j-1]) {//寻找正确的位置
                int temp = arr[j];  
                arr[j] = arr[j - 1];  
                arr[j - 1] = temp;  
                j--;  
            }  
        }  
    }  
}

递归

方法再次调用方法本身
递归一定要有出口，否则就会内存溢出

快速排序

第一轮：将0索引数字作为基准数，确定基准数在数组中的正确位置

// 快速排序主方法：递归分治  
private static void quickSort(int[] a, int l, int r) {  
    if(l < r){  
        int mid_index = find(a,l,r); // 分区，返回基准值的正确索引  
        quickSort(a,l,mid_index-1); // 排序左子数组（小于基准）  
        quickSort(a,mid_index+1,r); // 排序右子数组（大于基准）  
    }  
}  
  
// 分区函数：选a[l]为基准，返回基准值的最终索引  
private static int find(int[] a, int l, int r) {  
    int pivot = a[l]; // 基准值（保存副本，避免被修改）  
    int left = l + 1; // 左指针：从基准下一位开始找大于pivot的元素  
    int right = r;    // 右指针：从右边界开始找小于pivot的元素  
  
    while (true) {  
        // 右指针找小于基准值的元素（left<=right 防止越界）  
        while (left <= right && a[right] >= pivot) {  
            right--;  
        }  
        // 左指针找大于基准值的元素（left<=right 防止越界）  
        while (left <= right && a[left] <= pivot) {  
            left++;  
        }  
  
        // 左指针超过右指针，分区结束  
        if (left > right) {  
            break;  
        }  
  
        // 交换左右指针指向的元素（真正修改数组）  
        int temp = a[left];  
        a[left] = a[right];  
        a[right] = temp;  
    }  
  
    // 把基准值放到正确位置（right是小于基准区域的最后一位）  
    int temp = a[l];  
    a[l] = a[right];  
    a[right] = temp;  
  
    return right; // 返回基准值的最终索引  
}