排序学习 - 为了面对算法面试(2)

排序学习 - 为了面对算法面试(1) - 选择排序/冒泡排序/插入排序

• 4.归并排序:归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

  方法原理:

  • 1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  • 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  • 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  • 4. 重复步骤 3 直到某一指针达到序列尾；
  • 5. 将另一序列剩下的所有元素直接复制到合并序列尾。

//归并排序 - 分
func mergeSort(arr: inout [Int],startIndex: Int,endIndex: Int){
    var midIndex:Int
    if startIndex < endIndex {
        midIndex = (startIndex + endIndex) / 2
        mergeSort(arr: &arr, startIndex: startIndex, endIndex: midIndex)
        mergeSort(arr: &arr, startIndex: midIndex+1, endIndex: endIndex)
        //递归 分完 然后排序
        mergeSort(arr: &arr, startIndex: startIndex, midIndex: midIndex, endIndex: endIndex)
    }
}

/// 归并排序 - 治
func mergeSort(arr:inout [Int],startIndex: Int,midIndex: Int,endIndex: Int){
    //开辟空间 存储排序后序列
    var temp = [Int](repeating: 0, count: endIndex-startIndex+1)
    var i = startIndex,j = midIndex + 1
    //i,j同时走,比较小的值放在temp数组中
    while i <= midIndex && j <= endIndex {
        if arr[i] <= arr[j] {
            temp[i+j-startIndex-midIndex-1] = arr[i]
            i += 1
        }else{
            temp[i+j-startIndex-midIndex-1] = arr[j]
            j += 1
        }
    }
    //i或j已经有一个走完 那么把剩下的填到temp末尾
    while i <= midIndex {
        temp[i+j-startIndex-midIndex-1] = arr[i]
        i += 1
    }
    while j <= endIndex {
        temp[i+j-startIndex-midIndex-1] = arr[j]
        j += 1
    }
    //处理完毕 赋会原数组
    for i in startIndex...endIndex{
        arr[i] = temp[i-startIndex]
    }
}

to be continue!