数组-插入排序

采用插入方式对数组进行排序

插入排序百科:插入排序(insertion Sort),一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法插入排序是一种最简单的排序方法.

摘一个示例做个说明.
示例 1：
输入: [0,5,9,3,12,7]
输出: [0,3,5,7,9,12]

基本思想:

将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表.在其实现过程使用双层循环,外层循环对除了第一个元素外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动.
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序 。

算法分析:

1. 时间复杂度
   在插入排序中,当待排序数组是有序时,是最优的情况,只需当前跟前一个数比较一次,时间复杂度为O(N).
   最坏的情况是待排序的数组是逆序的,此时需要比较次数最多,总次数为1+2+3+…+N-1.时间复杂度为O(N²).
2. 空间复杂度
   插入排序的空间复杂度为常数阶O(1).
3. 算法稳定性
   如果待排序的序列中存在两个或者两个以上具有相同关键词的数据,排序后这些数据的相对次序保持不变,即它们的位置保持不变.
   综上,插入排序是一种稳定排序算法.
4. 应用分析
   插入排序适用于已经有部分数据已经排好，并且排好的部分越大越好。一般在输入规模大于1000的场合下不建议使用插入排序.

代码实现-Swift版本:

func insertionSort(nums: inout [Int]){
    for i in 0 ..< nums.count {
        for j in 0 ..< i {//将i插入到i-1中
            if nums[i] < nums[j]{
                nums.swapAt(i, j)//交换,j的位置一直在变
            }
        }
    }
}

测试用例:

var nums = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

参考:

• 插入排序百科

考察要点:

• 数组
• 排序