网站建设get你,推广淘特一个新人多少钱,寒亭做网站,wordpress 博客页面思路
选择排序#xff08;Selection sort#xff09;的主要思路是#xff1a;在要排序的区间内找到一个最大的元素#xff0c;将它放到数组的最后一个位置#xff0c;然后在剩余的未排序区间内找到一个最大的元素#xff0c;将它放到数组的倒数第二个位置。以此类推Selection sort的主要思路是在要排序的区间内找到一个最大的元素将它放到数组的最后一个位置然后在剩余的未排序区间内找到一个最大的元素将它放到数组的倒数第二个位置。以此类推重复此操作直到区间中只有一个元素就排好序了。 代码
看了上图应该知道了选择排序的做法可以结合以下代码进行理解。
最需要注意的是未排序的区间可以根据实际的例子推算出为。
#include iostreamusing namespace std;void swap(int a, int b) //交换两个数
{int temp 0;temp a;a b;b temp;
}void SelectSort(int arr[], int len)
{for (int i 0; i len - 1; i) // n个元素n-1次选择排序{int max 0; //默认最大值的下标为 0 for (int j 1; j len - i; j) //在未排序过的区间内找到区间最大值的下标{if (arr[j] arr[max]){max j; //更新最大值的下标}}//如果最大值不是未排序过的区间最后一个数交换位置if (max ! len - i - 1){swap(arr[max], arr[len - i - 1]);}}
}//选择排序
int main(void)
{int arr[] { 10,9,8,7,6,5,4,3,2,1};int len sizeof(arr) / sizeof(arr[0]);SelectSort(arr, len);for (int i 0; i len; i){cout arr[i] ;}return 0;
}
运行图片 选择排序的优化
优化在每一次的选择中找出一个最大元素和一个最小元素然后放到数组的两端这样次数就减少一半了。
代码实现
void SelectSortBetter(int arr[], int len)
{int begin 0, end len - 1; //初始化待排序区间的两端while (begin end){int max begin;int min begin;//j的范围是[begin1,end]为什么要加一那是和我们之前的代码对应不加一也行for (int j begin 1; j end 1; j) {if (arr[j] arr[max]){max j;}if (arr[j] arr[min]){min j;}}swap(arr[max], arr[end]);/*如果min为end那最大值交换完后最小值应该为arr[max]而不是还是arr[end]*/if (min end){min max;}swap(arr[min], arr[begin]);begin;end--;}
}
