选择排序的核心思路
- 选择排序的实现思路类似插入排序。也是将整个数组划分为已排序区间和未排序区间。两者的不同点在于，选择排序每次从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
选择排序的操作流程
- 假设我们对一个数组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);
}
