辽宁朝阳网站建设公司,wordpress自己写页面,网站发布,免费行情软件网站大全选择排序#xff08;select sort#xff09;在无序列表中#xff0c;把无序列表分成有序区#xff08;刚开始有序区元素个数为0#xff09;和无序区#xff08;刚开始无序区元素个数为n#xff09;#xff0c;循环n-1趟#xff0c;每一趟找到最小或最大的那个元素select sort在无序列表中把无序列表分成有序区刚开始有序区元素个数为0和无序区刚开始无序区元素个数为n循环n-1趟每一趟找到最小或最大的那个元素并把最小或最大的那个元素放在有序区此时有序区元素个数加1无序区元素个数减1直到循环n-1趟后列表都已排序好此时有序区的元素个数为n无序区元素个数为0。代码关键点分析总趟数n-1无序列表arr[n] {val0, val1, ..., val(n-1)};n 1时即无序列表只有1个元素只要进行比较0趟n 2 时即无序列表有2个元素只要进行比较1趟n 3 时即无序列表有3个元素只要进行比较2趟n n 时即无序列表有n个元素只要进行比较 n - 1 趟每一趟下标最大值为(n-1)代码#include iostreamusing namespace std;templatetypename T
void select_sort(T *arr, int n)
{int min_key;T temp;for (int i 0; i n-1; i) //总趟数n-1{min_key i; for (int j i1; j n; j) //每一趟下标的最大值为n-1{if (arr[j] arr[min_key])min_key j;}if (min_key ! i){temp arr[i];arr[i] arr[min_key];arr[min_key] temp;}}
}int main(int argc, char *argv[])
{int arr[] {3,5,2,1,4};int n sizeof(arr)/sizeof(*arr);cout ---before select sort--- endl;for (int i 0; i n; i){cout arr[i] ;}cout endl;select_sort(arr, n);cout ---after select sort--- endl;for (int i 0; i n; i){cout arr[i] ;}cout endl;return 0;
}结果时间复杂度O()选择排序算法外循环对总趟数进行循环内循环对每一趟进行循环所以算法时间复杂度为O()算法稳定性不稳定选择排序算法是不稳定的排序算法因为每次都是在未排序的元素列中找到最小的那个元素放到已排序的元素列的末尾可能会调换两个相等元素的先后位置那么原序列中两个相等元素的先后顺序就破坏了所以选择排序算法是不稳定的排序算法。比如{3,3,1,2}第一趟排序中首位置的3和第3个位置的1进行互换得到的{1,3,3,2}最开始的首位置的3和第2位置的3的先后位置就破坏了。
