排序是数据处理中十分常见且核心的操作,虽说实际项目开发中很小几率会需要我们手动实现,毕竟每种语言的类库中都有n多种关于排序算法的实现。但是了解这些精妙的思想对我们还是大有裨益的。本文简单温习下最基础的三类算法之一:简单选择排序。
先定义个交换数组元素的函数,供排序时调用
OC:
// 交换数组元素
- (void)swap:(NSMutableArray *)arr from:(int)a to:(int)b{
arr[a] = @([arr[a] intValue]+[arr[b] intValue]);
arr[b] = @([arr[a] intValue]-[arr[b] intValue]);
arr[a] = @([arr[a] intValue]-[arr[b] intValue]);
}
swift:
func swap(arr:inout Array<Int>,a:Int,b:Int) {
arr[a] = arr[a]+arr[b]
arr[b] = arr[a]-arr[b]
arr[a] = arr[a]-arr[b]
}
简单选择排序
简单选择排序是最简单直观的一种算法,基本思想为每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,直到所有元素排完为止,简单选择排序是不稳定排序。
在算法实现时,每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小,交换是个比较耗时的操作。其实我们很容易发现,在还未完全确定当前最小元素之前,这些交换都是无意义的。我们可以通过设置一个变量min,每一次比较仅存储较小元素的数组下标,当轮循环结束之后,那这个变量存储的就是当前最小元素的下标,此时再执行交换操作即可。代码实现很简单,一起来看下。
代码实现
OC:
- (void)selectSort:(NSMutableArray *)arr{
for (int i = 0;i<arr.count-1;i++){
int min = i;//每一趟循环比较时,min用于存放较小元素的数组下标,这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标,避免每次遇到较小元素都要进行交换。
for (int j = i + 1; j < arr.count; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
//进行交换,如果min发生变化,则进行交换
if (min != i) {
[self swap:arr from:min to:i];
}
}
}
swift:
func selectSort(arr:inout Array<Int>) {
for i in 0..<(arr.count-1){
var min:Int = i//每一趟循环比较时,min用于存放较小元素的数组下标,这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标,避免每次遇到较小元素都要进行交换。
let j = i+1
for j in j ..< arr.count {
if (arr[j] < arr[min]) {
min = j
}
}
//进行交换,如果min发生变化,则进行交换
if (min != i) {
self.swap(arr: &arr, a: min, b: i)
}
}
}
简单选择排序通过上面优化之后,无论数组原始排列如何,比较次数是不变的;对于交换操作,在最好情况下也就是数组完全有序的时候,无需任何交换移动,在最差情况下,也就是数组倒序的时候,交换次数为n-1次。综合下来,时间复杂度为O(n2)