选择排序

选择排序的核心思路

• 选择排序的实现思路类似插入排序。也是将整个数组划分为已排序区间和未排序区间。两者的不同点在于，选择排序每次从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

选择排序的操作流程

• 假设我们对一个数组a[6]进行排序。第一步就是遍历整个数组，找到数组中最小的元素，假设找到了最小的元素为a[3]，则将a[3]和a[0]交换位置，交换之后，这样数组中最小的元素就放在了数组的第一个。此时已排序区间中a[0],未排序区间为a[2]到a[5]。
• 我们再遍历a[2]到a[5]，取到其中最小的元素，比如取到的是a[4],则将a[4]与已排序区间的末尾的后一位数据进行交换，即a[0]的后面,即a[1]。a[4]与a[1]进行位置交换，交换之后，数组中第二小的元素就放在了a[1]的位置上了。此时已排序区间为a[0]到a[1]，未排序区间为a[2]到a[5]。
• 重复上述操作，直到未排序区间的元素为空，则排序结束。

选择排序的相关

• 选择排序是原地排序算法，不是稳定排序算法。
• 选择排序的平均时间复杂度为O(n²)。

代码的简单实现

- (void)selectionSort
{
    NSMutableArray *numberArray = [NSMutableArray arrayWithArray:@[@5,@1,@6,@2,@4,@3]];
    
    NSLog(@"排序之前的结果:%@",numberArray);
    
    for (int i = 0; i<numberArray.count-1; i++) {
        
        int minIndex = i;
        
        for (int j = i; j<numberArray.count; j++) {
            
            if ([numberArray[j] intValue] < [numberArray[minIndex] intValue]) {
                minIndex = j;
            }
            
        }
        
        NSNumber *minValue = numberArray[minIndex];
        
        numberArray[minIndex] = numberArray[i];
        
        numberArray[i] = minValue;
    }
    
    NSLog(@"排序之后的结果:%@",numberArray);
}