* @param high
* @param array
* @return 返回枢轴记录
*/
private int partition(int low, int high, int... array) {
int mid = (low + high) / 2;
// 枢轴记录三取一，优化的代码，用于待排序数组元素不是很大的时候
{
if (array[low] > array[high]) {
swap(low, high, array);
}
if (array[mid] > array[high]) {
swap(mid, high, array);
}
if (array[mid] > array[low]) {
swap(mid, low, array);
}
}
int pivotKey = array[low]; // 将三取一后的中间值作为枢轴记录
while (low < high) {
while (low < high && array[high] >= pivotKey) {
high--;
}
array[low] = array[high]; // 把比枢轴记录小的值赋给low下标的记录
while (low < high && array[low] <= pivotKey) {
low++;
}
array[high] = array[low]; // 把比枢轴记录大的值赋给high下标的记录
array[low] = pivotKey; // 然后将枢轴记录赋给low
}
return low; // 返回枢轴记录的下标
}
/**
* 直接插入排序的核心程序
* @param array
*/
public void insertSort(int... array) {
int length = array.length;
// 此循环从1开始，就是将0下标的元素当做一个参照
for (int i = 1; i < length; i++) {
if (array[i] < array[i - 1]) { // 将当前下标的值与参照元素比较，如果小于就进入里面
int vacancy = i; // 用于记录比较过程中那个空缺出来的位置
int sentry = array[i]; // 设置哨兵，将当前下标对应的值赋给哨兵
// 这个循环很关键，从当前下标之前一个元素开始倒序遍历，比较结果如果比当前大的，就后移
for (int j = i - 1; j >= 0 && array[j] > sentry; j--) {
vacancy = j;
array[j + 1] = array[j]; // 后移比当前元素大的元素
}
array[vacancy] = sentry; // 将哨兵，也就是当前下标对应的值置入空缺出来的位置
}
}
}
/**
* 内部实现，用于交换数组的两个引用值
*
* @param beforeIndex
* @param afterIndex
* @param arr
*/
private void swap(int oneIndex, int anotherIndex, int[] array) {
int temp = array[oneIndex];
array[oneIndex] = array[anotherIndex];
array[anotherIndex] = temp;
}