iOS算法总结-插入排序

刺骨的言语ヽ痛彻心扉 2023-10-17 16:38 47阅读 0赞

插入排序(Straight Insertion Sort)： 基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的，记录数增1的有序表。 
    
      
      
       代码如下： 
    
      
      
       - (void)logInsertionSortingArray {
        NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
        for (int i = 1; i < arr.count; i++) {
            int j = i;  /* j是一个坑， 确定坑的位置，再把数从坑里取出来，注意顺序*/
            id temp = arr[i];  /* temp 是从坑里取数*/
            if (arr[i] < arr[i-1]) {  /* j > 0 防止越界。写&&前面效率更高*/
                temp = arr[i];
                while (j > 0 && [temp intValue] < [arr[j-1] intValue]) {
                    arr[j] = arr[j-1];
                    j--;
                }
                arr[j] = temp;
            }
        }
    }
     
      
      
       效果图如下： 
      
      
       
      
      
       
    
      
      
       
       
       
        
       
       
        
    
       
       
        
      
      
       
      
      
       对上图解释如下： 
      
      
       
       
       
        从第二个开始，取出该位置的值为临时值temp，位置为j，此时j的位置为空，叫做坑，然后temp依次往前比较，直到找到比temp小，把temp插入该的位置，完成一次循环。 
      
      
       
      
      
       插入排序复杂度分析： 
      
      
       从空间上来看，它只需要一个记录的辅助空间，因此关键是看它的时间复杂度。当最好的情况，时间复杂度为O(n)。当最坏的情况，即待排序表示逆序的情况，如{6,5,4,3,2},此时需要比较(n+2)(n-1)/2次，记录的移动次数也达到(n+4)(n-1)/2次。如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为n²/4次，因此插入排序法的时间复杂度为O(n²)，该排序比冒泡和选择排序的性能要好一些。 
     
     
      
    
    作者：方圆一里
    链接：http://www.jianshu.com/p/d50eac247452
    來源：简书
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。