iOS_基本算法总结-选择排序

1.在viewDidLoad 里面加入以下两行代码，就可以得到结果

NSMutableArray*arr = [[NSMutableArrayalloc]initWithArray:@[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10]];

1.排序思想

第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；

第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；

以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

实际每一趟直接找到i对应数组下标的准确位置

所以他的时间复杂度为O(n2);

从选择排序的过程来看，它最大的特点就是交换移动数据次数相当少，节约了相应的时间。分析它的时间复杂度发现，无论最好最差情况，其比较次数是一样多的 n-1 + n-2 + ... + 1 = n(n-1)/2。而对于交换次数而言，最好的时候交换为0次，最差的时候，为n-1次，基于最终的排序时间是比较与交换的次数总和，因此，总的时间复杂度为O(n²)。