package sort

/*

归并排序

是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)，1945年由冯·诺伊曼首次提出。

归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略

的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个

大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，

一直下去直到归并了整个数组。

归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个

序列的操作，归并操作步骤如下：

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4.重复步骤3直到某一指针到达序列尾

5.将另一序列剩下的所有元素直接复制到合并序列尾

*/

/*

分类:内部比较排序

数据结构:数组

最差时间复杂度:O(nlogn)

最优时间复杂度:O(nlogn)

平均时间复杂度:O(nlogn)

所需辅助空间:O(n)

稳定性:稳定

*/

fun merge(a: IntArray,left: Int,mid: Int, right: Int){//合并两个已排好序的数组

var l = left

var len = right - left + 1

var temp: Array<Int> = Array<Int>(len,{0})

var index = 0

var i = left

var j = mid + 1

while (i <= mid && j<= right){

if(a[i] <=a[j]){

temp[index++] = a[i++]

}else{

temp[index++] = a[j++]

}

}

while (i<=mid){

temp[index++] = a[i++]

}

while (j<=right){

temp[index++] = a[j++]

}

for (k in 0 until len){

a[l++] = temp[k]

}

}

//递归实现的归并排序(自顶向下)

fun mergeSortRecursion(a: IntArray, left: Int, right: Int){

if (left == right)

return

var mid = (left + right) / 2

mergeSortRecursion(a, left, mid)

mergeSortRecursion(a, mid+1, right)

merge(a,left,mid,right)

}

//迭代实现归并排序(自底向上)

fun mergeSortIteration(a: IntArray, len: Int){

var left: Int

var mid: Int

var right: Int

var i: Int = 1

while (i<len){

left = 0

while (left+i < len){ //后一个子数组存在

mid = left + i - 1

right = if (mid + i < len) mid + i else len - 1

merge(a,left,mid,right)

left = right + 1

}

i*=2

}

}

fun main(args: Array<String>) {

val array: IntArray = intArrayOf(3,5,1,8,6,6,9,8,7,6,2)

val n: Int = array.size

// mergeSortRecursion(array,0,n-1)

mergeSortIteration(array,n)

println("归并排序结果:")

for (i in 0 until n){

print(array[i].toString() + ",")

}

}