iOS算法总结-选择排序

深藏阁楼爱情的钟 2023-10-17 16:38 41阅读 0赞

选择排序法(Simple Selection Sort) ： 通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1≤i≤n)个记录交换之。 
    
      
      
       代码如下： 
    
      
      
       - (void)logChooseArray {
        NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
        int min = 0, arrCount = (int)arr.count;
        for (int i = 0; i < arrCount-1; i++) {
            min = i;  
            for (int j = i + 1; j < arrCount; j++) {  
                if (arr[min] > arr[j]) {  /*如果有小于当前的最小值的关键字*/
                    min = j;  /*将此关键字的下标赋值给min*/
                }
            }
            if (i != min) {  /*若min不等于i，说明找到最小值，交换*/
                [arr exchangeObjectAtIndex:i withObjectAtIndex:min];
            }
        }
    }
    //每次循环打印结果如下
    1 16 2 9 7 12 5 3 8 13 10
    1 2 16 9 7 12 5 3 8 13 10
    1 2 3 9 7 12 5 16 8 13 10
    1 2 3 5 7 12 9 16 8 13 10
    1 2 3 5 7 12 9 16 8 13 10
    1 2 3 5 7 8 9 16 12 13 10
    1 2 3 5 7 8 9 16 12 13 10
    1 2 3 5 7 8 9 10 12 13 16
    1 2 3 5 7 8 9 10 12 13 16
    1 2 3 5 7 8 9 10 12 13 16
    1 2 3 5 7 8 9 10 12 13 16
     
      
      
       复杂度分析： 
      
      
       从选择排序的过程来看，它最大的特点就是交换移动数据次数相当少，节约了相应的时间。分析它的时间复杂度发现，无论最好最差情况，其比较次数是一样多的 n-1 + n-2 + ... + 1 = n(n-1)/2。而对于交换次数而言，最好的时候交换为0次，最差的时候，为n-1次，基于最终的排序时间是比较与交换的次数总和，因此，总的时间复杂度为O(n²) 
      
      
       尽管与冒泡排序同为O(n²)，但选择排序的性能上还是要略优于冒泡排序。 
     
     
      
    
    作者：方圆一里
    链接：http://www.jianshu.com/p/ec58c2794daf
    來源：简书
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。