我认为归并排序至少有4种实现方式。
public class MergeSort {
/**
* 下面要实现的是传说中的归并排序算法
* 从代码量上来讲有点复杂
* 本算法采用非递归的方法来实现
* 归并排序是分而治之思想的体现
* 如果是用非递归方式来实现就不
* 用考虑分，直接治就可以了。
* 说得通俗一点就是直接2排序，然后
* 4排序，然后合并起来就行。
* 其实归并排序并没有队列的实现，因
* 为队列的实现归根到底就是本实现，
* 所以它是多余的。
* 另外，就是我想到了一个定理——对于
* 完全二叉树而言，非根结点的长度除
* 以2-1就是其父结点的序号。
* @param sourceArray
*/
static public void mergeSort0(int[] sourceArray) {
//获取数组的长度
int arrayLength = sourceArray.length;
//设置步长初始值为1。
int stepWidth = 1;
//只要步长不大于数组的长度就代表归并还得
//往下进行。
//用于打印第几趟归并
int printCounter = 0;
while (stepWidth <= arrayLength) {
//计算每个步长的边界index
//没办法一次性处理余数的问题
//只能单独处理余数问题
stepWidth *= 2;
for (int counter = 0;counter < arrayLength;counter += stepWidth) {
//单独处理尾index
//把尾index放在循环体里面计算是非常高明的。
int rightIndex;
if (counter + stepWidth > arrayLength)
rightIndex = arrayLength - 1;
else rightIndex = counter + stepWidth - 1;
//中间的分界点
int middleIndex;
//用于最后一次步长的时候
if (stepWidth > arrayLength)
middleIndex = (stepWidth - 1) / 2;
else middleIndex = (counter + rightIndex) / 2;
//生成一个临时数组用于存储排好序的元素
//元素个数恰好等于该步长内的元素个数
int stepLength = rightIndex - counter + 1;
int[] tempArray = new int[stepLength];
int leftPointer = counter;
int rightPointer = middleIndex + 1;
int tempPointer = 0;
//只要两个分组之一没遍历完就把元素放入临时数组中
while (leftPointer <= middleIndex && rightPointer <= rightIndex) {
if (sourceArray[leftPointer] > sourceArray[rightPointer])
tempArray[tempPointer++] = sourceArray[leftPointer++];
else tempArray[tempPointer++] = sourceArray[rightPointer++];
}
//如果前半段没遍历完
while (leftPointer <= middleIndex)
tempArray[tempPointer++] = sourceArray[leftPointer++];
//如果后半段没遍历完
while (rightPointer <= rightIndex)
tempArray[tempPointer++] = sourceArray[rightPointer++];
//把临时数组中的元素赋值给原数组
leftPointer = counter;
tempPointer = 0;
while (tempPointer < stepLength)
sourceArray[leftPointer++] = tempArray[tempPointer++];
//打印部分
System.out.print("[ ");
for (int counter1 = 0;counter1 < arrayLength;counter1++) {
if ((counter1 + 1) % stepWidth == 0 && counter1 + 1 != arrayLength)
System.out.print(sourceArray[counter1] + " | ");
else System.out.print(sourceArray[counter1] + " ");
}
System.out.print("]");
System.out.println("归并 " + stepWidth / 2 + " 步长的一小趟结束了");
}
for (int element:sourceArray) {
System.out.print(element + " ");
}
System.out.println("第 " + ++printCounter + " 趟结束了");
}
}
/**
* 我决定精简一下上面的实现代码
* @param sourceArray
*/
static public void mergeSort2(int[] sourceArray) {
int arrayLength = sourceArray.length;
//用于打印第几趟归并
int printCounter = 0;
//现在这个其实是每一趟的middleindex
for (int stepWidth = 1;stepWidth < arrayLength;stepWidth *= 2) {
//只有这样才能合并当前步长
//所以必须要把步长×2
int doubleStepWidth = 2 * stepWidth;
for (int counter = 0;counter < arrayLength;counter += doubleStepWidth) {
//中间的分界点的index
//它也有可能越界。
int middleIndex = counter + stepWidth;
//右边界指针可能越界
int rightIndex = middleIndex + stepWidth;
//生成一个临时数组用于存储排好序的元素
//它的元素个数可能比实际数组元素个数多
//所以可能发生越界错误
//虽然申请的数组大小可能比实际容纳的元素个数要多
//但是这样可以完美地解决不足一个步长的余数问题
int[] tempArray = new int[doubleStepWidth];
int leftPointer = counter;
//正因为rightIndex可能越界，所以rightPointer也可能越界。
int rightPointer = middleIndex;
int tempPointer = 0;
//只要两个分组之一没遍历完就把元素放入临时数组中
//此时2个分组都没有被遍历完
//并且前半段的index肯定比后半段的index要小
//所以此时只需要让有指针不要越界即可
while (leftPointer < middleIndex && rightPointer < rightIndex && rightPointer < arrayLength) {
//此处界定了结果是正向有序还是逆向有序
if (sourceArray[leftPointer] > sourceArray[rightPointer])
tempArray[tempPointer++] = sourceArray[leftPointer++];
else tempArray[tempPointer++] = sourceArray[rightPointer++];
}
//如果前半段没遍历完
//假如分组中的元素个数不到doubleStepWidth的一半的时候
//leftPointer就有可能越界。
while (leftPointer < middleIndex && leftPointer < arrayLength)
tempArray[tempPointer++] = sourceArray[leftPointer++];
//如果后半段没遍历完
//假如分组中的元素个数超过doubleStepWidth的一半并且不到doubleStepWidth的时候
//rightPointer就有可能越界。
while (rightPointer < rightIndex && rightPointer < arrayLength)
tempArray[tempPointer++] = sourceArray[rightPointer++];
//把临时数组中的元素赋值给原数组
//此时rightPointer已经是指向了双倍步长分组的最后一个位置
//但是这个位置可能早就已经越界了
//所以还要让它小于数组长度
leftPointer = counter;
tempPointer = 0;
while (leftPointer < rightPointer && leftPointer < arrayLength)
sourceArray[leftPointer++] = tempArray[tempPointer++];
//打印部分
System.out.print("[ ");
for (int counter1 = 0;counter1 < arrayLength;counter1++) {
if ((counter1 + 1) % stepWidth == 0 && counter1 + 1 != arrayLength)
System.out.print(sourceArray[counter1] + " | ");
else System.out.print(sourceArray[counter1] + " ");
}
System.out.print("]");
System.out.println("归并 " + stepWidth + " 步长的一小趟结束了");
}
for (int element:sourceArray) {
System.out.print(element + " ");
}
System.out.println("第 " + ++printCounter + " 趟结束了");
}
}
/**
* 下面这个是归并排序的递归实现
* 递归实现看起来简单明了
* 这个方法其实是整个算法的入口
* @param sourceArray
*/
static public void mergeSort1(int[] sourceArray) {
int arrayLength = sourceArray.length;
MergeSort.divideIndex(sourceArray,0,arrayLength - 1);
for (int element:sourceArray) {
System.out.print(element + " ");
}
System.out.println("归并排序递归算法实现结束了");
}
/**
* 下面这个方法是
* 分而治之
* 思想中的分部分
* @param sourceArray
* @param leftIndex
* @param rightIndex
*/
static private void divideIndex(int[] sourceArray,int leftIndex,int rightIndex) {
//这是递归的终止条件
//这里的条件不能是小于等于
//1、从道理上讲如果是相等，那其实没有意义。
//2、从程序来讲等于号会导致死循环。
//因为当步长为1的时候leftIndex和rightIndex会相等
//但是这并不是递归结束的条件。
if (leftIndex < rightIndex) {
int middleIndex = (leftIndex + rightIndex) / 2;
//已经排好序的前半段
MergeSort.divideIndex(sourceArray,leftIndex,middleIndex);
//已经排好序的后半段
MergeSort.divideIndex(sourceArray,middleIndex + 1,rightIndex);
//合并前半段和后半段
MergeSort.mergeStep(sourceArray,leftIndex,middleIndex,rightIndex);
}
}
/**
* 这是分而治之策略中的
* 治部分
* 说得通俗一点就是合并
* 每一趟
* @param sourceArray
* @param leftIndex
* @param middleIndex
* @param rightIndex
*/
static private void mergeStep(int[] sourceArray,int leftIndex,int middleIndex,int rightIndex) {
int leftPointer = leftIndex;
int rightPointer = middleIndex + 1;
int[] tempArray = new int[rightIndex - leftIndex + 1];
int tempPointer = 0;
while (leftPointer <= middleIndex && rightPointer <= rightIndex) {
if (sourceArray[leftPointer] > sourceArray[rightPointer])
tempArray[tempPointer++] = sourceArray[leftPointer++];
else tempArray[tempPointer++] = sourceArray[rightPointer++];
}
while (leftPointer <= middleIndex)
tempArray[tempPointer++] = sourceArray[leftPointer++];
while (rightPointer <= rightIndex)
tempArray[tempPointer++] = sourceArray[rightPointer++];
leftPointer = rightIndex;
while (--tempPointer > -1)
sourceArray[leftPointer--] = tempArray[tempPointer];
}
/**
* 其实只要是递归的实现都
* 可以用栈来转化成非递归
* 的实现，根据这一原理可
* 以给出归并排序的另一种
* 非递归实现——栈实现。
* 思路为只要分栈中栈顶的
* 2个元素值不相等就二分
* 然后把分好的下标入栈，
* 直到相等为止停止入栈操
* 作，然后把相等的2个下
* 标推入并栈中去。
* 如果分栈中栈顶的2个下
* 标不等，并且小于并栈中
* 的栈顶值就代表分栈中栈
* 顶的2个值并没有被分组
* 于是要把它们二分入栈，
* 不小于的话就代表分栈栈
* 顶的两个值是需要被合并
* 的，已经排好序的2个分
* 组的首尾下标，此时应该
* 用于合并。
* 应该根据这两个值对并栈
* 中的栈顶方向的一对或者
* 2对值进行合并，然后分
* 栈pop2.
* 如此往复，直到分栈栈顶为-1.
* 这就是算法的思想。
* @param sourceArray
*/
static public void mergeSort3(int[] sourceArray) {
int arrayLength = sourceArray.length;
//需要创建2个数组，一个用
// 来充当2分下标的栈，它的
// 容量顶多是2倍的数组长度。
// 另一个是用来合并的栈，它
// 的容量也顶多是2被数组长度。
//分栈
//经过推算发现分栈所需要的空间最多是
// 2×⌈log2n⌉(这里是以2为底n的对数的上取整的意思)+1，
// 并栈最多需要⌈log2n⌉(这里是以2为底n的对数的上取整的意思)+1
// 个存储空间，但是经过用数学归纳法证明发现
// 2×⌈log2n⌉(这里是以2为底n的对数的上取整的意思)+1
// 肯定是小于2n的，所以出于省时省力的角度讲就把这两个
// 栈的长度都设置为2倍的数组长度。
int[] divideStack = new int[2 * arrayLength];
//分栈栈顶指针
int divideStackTop = -1;
//并栈
int[] mergeStack = new int[2 * arrayLength];
//并栈栈顶指针
int mergeStackTop = -1;
//先把整个数组的首尾入栈
divideStack[++divideStackTop] = 0;
divideStack[++divideStackTop] = arrayLength - 1;
while (divideStackTop > -1) {
if (mergeStackTop == -1 || mergeStack[mergeStackTop] > divideStack[divideStackTop]) {
while (divideStack[divideStackTop] > divideStack[divideStackTop - 1]) {
int headIndex = divideStack[divideStackTop - 1];
int endIndex = divideStack[divideStackTop];
int middleIndex = (headIndex + endIndex) / 2;
divideStack[++divideStackTop] = headIndex;
divideStack[++divideStackTop] = middleIndex;
divideStack[++divideStackTop] = middleIndex + 1;
divideStack[++divideStackTop] = endIndex;
}
while (divideStack[divideStackTop] == divideStack[divideStackTop - 1]) {
mergeStack[++mergeStackTop] = divideStack[divideStackTop];
mergeStack[++mergeStackTop] = divideStack[divideStackTop];
divideStackTop -= 2;
}
} else {
if (mergeStackTop > 2 && mergeStack[mergeStackTop - 3] == divideStack[divideStackTop]) {
int headIndex = mergeStack[mergeStackTop];
mergeStackTop -= 2;
mergeStack[mergeStackTop] = headIndex;
}
divideStackTop -= 2;
int headPointer = mergeStack[mergeStackTop];
int endPointer = mergeStack[mergeStackTop - 1];
int middlePointer = (headPointer + endPointer) / 2;
mergeStep(sourceArray,headPointer,middlePointer,endPointer);
}
for (int counter = 0;counter <= divideStackTop;counter++) {
System.out.print(divideStack[counter] + " ");
}
System.out.println("divideStack状态");
for (int counter = mergeStackTop;counter >= 0;counter--) {
System.out.print(mergeStack[counter] + " ");
}
System.out.println("mergeStack状态");
for (int element:sourceArray) {
System.out.print(element + " ");
}
System.out.println("当前数组状态\n");
}
}
/**
* 现在我要用把递归转换成非递归的通用方法把归并排序
* 转换成非递归的实现
* 这个通用方法可以解决这类问题
* 而这类问题就是如何把把递归转换成非递归
* @param sourceArray
*/
static public void mergeSort4(int[] sourceArray) {
int arrayLength = sourceArray.length;
MergeSort.divideIndex0(sourceArray,0,arrayLength - 1);
for (int element:sourceArray) {
System.out.print(element + " ");
}
System.out.println("归并排序递归算法实现结束了");
}
static private void divideIndex0(int[] sourceArray,int leftIndex,int rightIndex) {
IndexPair[] pairStack = new IndexPair[sourceArray.length];
int pairStackPointer = -1;
pairStack[++pairStackPointer] = new IndexPair(leftIndex,rightIndex);
while (pairStackPointer > -1) {
IndexPair topPair = pairStack[pairStackPointer--];
if (topPair.getHeadIndex() < topPair.getEndIndex()) {
//逆序入栈
int headIndex = topPair.getHeadIndex();
int endIndex = topPair.getEndIndex();
int middleIndex = (headIndex + endIndex) / 2;
MergeSort.mergeStep(sourceArray,leftIndex,middleIndex,rightIndex);
pairStack[++pairStackPointer] = new IndexPair(middleIndex + 1,endIndex);
pairStack[++pairStackPointer] = new IndexPair(headIndex,middleIndex);
}
}
}
}
public class IndexPair {
private int headIndex;
private int endIndex;
public IndexPair(int headIndex, int endIndex) {
this.headIndex = headIndex;
this.endIndex = endIndex;
}
public int getHeadIndex() {
return headIndex;
}
public int getEndIndex() {
return endIndex;
}
}
