插入排序

直接插入排序

• 第一个元素就认为是有序的
• 取第二个元素，判断是否大于第一个元素。若是大于，表示已经有序，不用移动，否则将已经有序的序列整体向后移动一个位置
• 依此类推，直到所有元素已经有序。

    func insertSort(insert arr:[Int]) -> [Int]{
      var arr = arr
        
        for i in 1 ..< arr.count {
           // 遇到不是有序的，才进入移动元素
            if arr[i] < arr[i - 1] {
                
                let target = arr[i]
                
                //移动前j-1元素，分别向后移动一个位置
                var j = i
                
                while j > 0 && arr[j-1] > target{
                    arr[j] = arr[j-1]
                    j -= 1
               
                }
                // 将目标元素放到目标位置，使之有序
                    arr[j] = target;
               
                print("i=\(i)--- j= \(j) --- \(arr) -----\(target)")
            }
            
        }
        return arr
    }

引入

        let arr = [9, 1, 5, 7, 4, 8, 6, 3]
        
        print("简单直接插入排序:\(insertSort(insert: arr))")

打印结果

屏幕快照 2017-05-09 上午11.18.42.png