选择排序 是时间复杂度为O(n^2)的排序算法，它是不稳定的算法，基本想法是每次选择剩余数据中的最值插入，具体流程如下：
初始数据为 1, -1, 2, 5, -4, 0, -2, -3, 3, 4(升序排列)
第一次选择：
从第 1 个位置到最后一个位置找出最小值与第 1 个位置 的数交换得 -4, -1, 2, 5, 1, 0, -2, -3, 3, 4 (-4 与 1 交换)
接下来从第二个位置开始依次寻找
第二次选择：
-4, -3, 2, 5, 1, 0, -2, -1, 3, 4 (-3 与 -1 交换)
第三次选择：
-4, -3, -2, 5, 1, 0, 2, -1, 3, 4 (-2 与 2 交换)
… … 直到最后一次交换就完成了排序
由以上过程可写出升序算法的程序：
void selectUpSort(int nums
[], int numsSize
) {
for(int i
= 0; i
< numsSize
-1; ++i
) {
int min
= i
;
for(int j
= i
+1; j
< numsSize
; ++j
) {
min
= nums
[j
]<nums
[min
] ? j
: min
;
}
if(min
!= i
) {
int tmp
= nums
[i
];
nums
[i
] = nums
[min
];
nums
[min
] = tmp
;
}
}
}
对于降序来说，只需要每一次找最大值即可
源代码
#include <stdio.h>
void selectUpSort(int nums
[], int numsSize
) {
for(int i
= 0; i
< numsSize
-1; ++i
) {
int min
= i
;
for(int j
= i
+1; j
< numsSize
; ++j
) {
min
= nums
[j
]<nums
[min
] ? j
: min
;
}
if(min
!= i
) {
int tmp
= nums
[i
];
nums
[i
] = nums
[min
];
nums
[min
] = tmp
;
}
}
}
void selectDownSort(int nums
[], int numsSize
) {
for(int i
= 0; i
< numsSize
-1; ++i
) {
int max
= i
;
for(int j
= i
+1; j
< numsSize
; ++j
) {
max
= nums
[j
]>nums
[max
] ? j
: max
;
}
if(max
!= i
) {
int tmp
= nums
[i
];
nums
[i
] = nums
[max
];
nums
[max
] = tmp
;
}
}
}
int main() {
int arr1
[] = {1, -1, 2, 5, -4, 0, -2, -3, 3, 4};
int len1
= sizeof(arr1
) / sizeof(arr1
[0]);
selectUpSort(arr1
, len1
);
int arr2
[] = {1, -1, 2, 5, -4, 0, -2, -3, 3, 4};
int len2
= sizeof(arr2
) / sizeof(arr2
[0]);
selectDownSort(arr2
, len2
);
printf("UP:\t");
for(int i
= 0; i
< len1
; ++i
) printf("%d ", arr1
[i
]);
printf("\nDOWN:\t");
for(int i
= 0; i
< len2
; ++i
) printf("%d ", arr2
[i
]);
return 0;
}
结果
