本文共 1487 字,大约阅读时间需要 4 分钟。
每一趟都从待排序的数列中选择一个最大(最小)的,放在数列的最后一个位置(或起始位置)直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
例:9 5 3 4 6 2 8 1 7 0
#include#include void Swap(int *p1, int *p2){ int tmp = *p1; *p1 = *p2; *p2 = tmp;}void select_sort(int arr[], int len){ for (int i = 0; i < len - 1; i++) //表示趟数 { int maxPos = 0; for (int j = 1; j < len - i; j++) { if (arr[j] > arr[maxPos]) { maxPos = j; } } if (maxPos != len - 1 - i) //如果最大的元素就是在最后位置,就不用交换 { Swap(arr + maxPos, arr + (len - 1 - i)); } }}int main(){ int arr[] = { 9,5,3,4,6,2,8,1,7,0 }; int len = sizeof(arr) / sizeof(arr[0]); select_sort(arr, len); for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } system("pause"); return 0;}
选择排序的每一趟记录最大值,我们是不是可以在一趟中,把最小值和最大值都记录下来,这样就可以只完成一半的工作
void Swap(int *p1, int *p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void select_sort(int arr[], int len) { int left = 0; int right = len - 1; while (left < right) { int minPos = left; int maxPos = left; for (int i = left; i < len - left; i++) { if (arr[i] < arr[minPos]) { minPos = i; } if (arr[i] > arr[maxPos]) { maxPos = i; } } //这个if是为了判断第一个元素是不是最大的,因为如果第一个元素是最大的,会将最大的元素换位置 //比如,上述中的第一步,9是最大的,如果9和0换位置,但maxPos仍然是0,这是第一个元素就变为了0, //maxPos却没有发生变化,再将最大的元素和最后一个元素换位置,就会是0和最后一个元素换位置,而不是最大的元素 //所以这种情况就要先将换后的位置赋值给maxPos Swap(arr + minPos, arr + left); if (maxPos == left) { maxPos = minPos; } Swap(arr + maxPos, arr + right); left++; right--; } }