常见排序&查询算法Java代码实现

/**
 * ascending sort
 *  外层循环边界条件：总共需要冒泡的轮数--每一轮都将最大或最小的数冒泡到最后
 *  内层循环边界条件：冒泡数字移动的边界--最终数字需冒泡到此处
 *  时间复杂度：O(n^2)
 * @param arr
 */
public static void bubbleSort(int[] arr) {
	if (arr == null) {
		throw new RuntimeException("Input arr is null!");
	}
	
	for(int i = 0; i  arr[j+1]) {
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

/**
 * 每次都将未排序数组中的最大或最小元素找出来和第一个元素交换位置
 *  时间复杂度：O(n^2)
 * @param arr
 */
public static void selectSort(int[] arr) {
	if (arr == null) {
		throw new RuntimeException("Input arr is null!");
	}
	
	for(int i = 0; i 插入排序：顺次从数组中选择一个数，插入到前面已排序的数组中
 * 时间复杂度：O(n)~O(n^2)
 * @param arr
 */
public static void insertSort(int[] arr) {
	if (arr == null) {
		throw new RuntimeException("Input arr is null!");
	}
	
	for(int i = 1; i = 0; j--) {
			if(arr[j] > value) {
				arr[j+1] = arr[j];
			} else {
				break;
			}
		}
		arr[j+1]=value;
	}
}

/**
 * 	希尔排序：插入排序的改进版，也称缩小增量排序
 *
 * @param arr
 */
public static void shellSort(int[] arr) {
	if (arr == null) {
		throw new RuntimeException("Input arr is null!");
	}
	
	int length = arr.length;
	//区间
	int gap = 1;
	while(gap  0) {
		for(int i = gap; i = 0 && arr[j] > tmp) {
				arr[j+gap] = arr[j];
				j -= gap;
			}
			arr[j + gap] = tmp;
		}
		gap = gap / 3;
	}
}

/**
 * 	归并排序--核心为分治法
 *	时间复杂度O(nlogn)
 * @param arr
 */
public static void mergeSort(int[] arr) {
	if (arr == null) {
		throw new RuntimeException("Input arr is null!");
	}
	int[] tmpArr = new int[arr.length];
	mSort(arr,tmpArr, 0, arr.length - 1);
}

private static void mSort(int[] arr, int[] tmpArr, int startIndex, int endIndex) {
	//边界条件：数组已不可再拆
	if (endIndex  middleIndex) {
			arr[k] = tmpArr[right++];
		} else if (right > endIndex) {
			arr[k] = tmpArr[left++];
		} else if (tmpArr[left] 快速排序：随机选取一个参考值，将比参考值小的数移到数组前段，大的值移到后段
 * 	以参考值为临界点递归拆分数组直至数组不能拆分，此时数组本身已排好序
 * 	快速排序时间复杂度为O(nlogn)，对于逆序数组复杂度退化为O(n^2)，为了避免极端情况，可随机选取参考值
 * @param arr
 */
public static void quickSort(int[] arr) {
	if (arr == null) {
		throw new RuntimeException("Input arr is null!");
	}
	
	qSort(arr , 0, arr.length - 1);		
}

private static void qSort(int[] arr, int startIndex, int endIndex) {
	// 设置边界条件
	if (endIndex  startIndex) {
		qSort(arr, startIndex, refIndex - 1);
	}
	if (endIndex > refIndex) {
		qSort(arr, refIndex + 1, endIndex);
	}			
}

private static int partition(int[] arr, int startIndex, int endIndex) {
	// 将数组中refValue的值与最后一个数交换，随机选取参考值可避免时间复杂度退化为O(n^2)
	int refIndex = startIndex + new Random().nextInt(endIndex - startIndex + 1);
	// 深坑，当两个数指向同一个时，会影响异或结果
	if (refIndex != endIndex) {
		arr[endIndex] = arr[endIndex] ^ arr[refIndex];
		arr[refIndex] = arr[endIndex] ^ arr[refIndex];
		arr[endIndex] = arr[endIndex] ^ arr[refIndex];
	}
	
	// 分组下标
	int partitionIndex = startIndex - 1;
	// 数组最后一个值为参考值，不参与循环
	for (int dataIndex = startIndex; dataIndex  0; i--) {
		//将堆元素与末位元素调换
		int temp = arr[0];
		arr[0] =arr[i];
		arr[i] = temp;
		//数组长度-1 隐藏堆尾元素
		length--;
		//将堆顶元素下沉，目的是将最大的元素浮到堆顶来
		sink(arr, 0, length);
	}
}
	
private static void buildHeap(int[] arr, int length) {
	for (int i = length / 2; i >= 0; i--) {
		sink(arr, i , length);
	}
}

private static void sink(int[] arr, int index, int length) {
	//左子节点下标
	int leftChild = 2 * index + 1;
	//右子节点下标
	int rigthChild = 2 * index + 2;
	//要调整的节点下标
	int present = index;
	
	//下沉左边
	if (leftChild  arr[present]) {
		present = leftChild;
	}
	
	//下沉右边
	if (rigthChild  arr[present]) {
		present = rigthChild;
	}
	
	//如果下标不相等，证明调换过了
	if (present != index) {
		//交换值
		int temp = arr[index];
		arr[index] = arr[present];
		arr[present] = temp;
		
		//继续下沉
		sink(arr, present, length);
	}
}

/**
 *	计数排序--时间复杂度为O(n+m)，空间大小取决于数组值，时间复杂度为O(n)
 *	问题点：数组中不能有负数，否则会抛出越界异常
 * @param arr
 */
public static void countSort(int[] arr) {
	if (arr == null) {
		throw new RuntimeException("Input arr is null!");
	}
	
	//找出数组中的最大值
	int max = arr[0];
	for(int i = 1; i  0) {
			arr[index++] = i;
			countArr[i]--;
		}
	}
}


/**
 * 	桶排序--类似于Hash分桶策略
 * 	良好的分桶策略可实现O(n)时间复杂度
 * @param arr
 */
public static void bucketSort(int[] arr) {
	if (arr == null) {
		throw new RuntimeException("Input arr is null!");
	}
	
	//最大最小值
	int max = arr[0];
	int min = arr[0];
	int length = arr.length;
	
	for (int i = 1; i  max) {
			max = arr[i];
		} else if (arr[i] > bucketList = new ArrayList();
	for (int i = 0; i ());
	}
	
	//每个桶的存数区间
	float section = (float)diff / (float)(length -1);
	
	//数据入桶
	for (int i = 0; i  arrayList: bucketList) {
		for (int value : arrayList) {
			arr[index] = value;
			index++;
		}
	}
}

/**
 * 	基数排序
 * @param arr
 */
public static void radixSort(int[] arr) {
	if (arr == null) {
		throw new RuntimeException("Input arr is null!");
	}

	int length = arr.length;

	//最大值
	int max = arr[0];
	for(int i = 0;i  max){
			max = arr[i];
		}
	}
	//当前排序位置
	int location = 1;

	//桶列表
	ArrayList> bucketList = new ArrayList();

	//长度为10 装入余数0-9的数据
	for(int i = 0; i ());
	}

	while(true)
	{
		//判断是否排完
		int dd = (int)Math.pow(10, (location - 1));
		if(max 

/**
 *    顺序查找，即为遍历数组，时间复杂度为O(n)
 * @param arr
 * @param value
 * @return
 */
public static int sequentialSearch(int[] arr, int value) {
    if (arr == null) {
        throw new RuntimeException("Input arr is null!");
    }
    
    for (int i = 0; i ) {
        if (arr[i] == value) {
            return i;
        }
    }
    
    return -1;
}

/**
 *    二分查找针对以升序排列的数组进行，每次取数组的中间值进行查找
 *    时间复杂度为O(logn)
 * @param arr
 * @param value
 * @return
 */
public static int binarySearch(int[] arr, int value) {
    if (arr == null) {
        throw new RuntimeException("Input arr is null!");
    }
    
    int low = 0;
    int high = arr.length - 1;
    int mid = 0;
    while (low  high) {
        mid = (low + high)/2;
        if (arr[mid] == value) {
            return mid;
        } else if (arr[mid] > value) {
            high = mid -1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

/**
 *     二分查找--递归实现
 * @param arr    待查询数组
 * @param value    查找目标值
 * @param low    数组起始下标
 * @param high    数组结束下标
 * @return    目标值的下标
 */
public static int binarySearchByRecursion(int[] arr, int value, int low, int high) {
    if (arr == null) {
        throw new RuntimeException("Input arr is null!");
    }
    int mid = low + (high -low)/2;
    if (low == high && arr[mid] != value) {
        return -1;
    }
    if (arr[mid] == value) {
        return mid;
    } else if (arr[mid] > value) {
        return binarySearchByRecursion(arr, value, low, mid - 1);
    } else {
        return binarySearchByRecursion(arr, value, mid + 1, high);
    }
}

/**
 *     插值查找--递归实现，原理与二分查找类似，按目标值的大小计算在数组中的权重，适用于均有有序的数组
 * @param arr    待查询数组
 * @param value    查找目标值
 * @param low    数组起始下标
 * @param high    数组结束下标
 * @return    目标值的下标
 */
public static int insertionSearch(int[] arr, int value, int low, int high) {
    if (arr == null) {
        throw new RuntimeException("Input arr is null!");
    }
    // 按目标值与最小值的差估算插值下标的位置
    int mid = low + ((value - arr[low]) / (arr[high] - arr[low])) * (high -low);
    if (low == high && arr[mid] != value) {
        return -1;
    }
    if (arr[mid] == value) {
        return mid;
    } else if (arr[mid] > value) {
        return binarySearchByRecursion(arr, value, low, mid - 1);
    } else {
        return binarySearchByRecursion(arr, value, mid + 1, high);
    }
}