首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第六章“排序”——选择排序
《数据结构与算法分析：C语言描述》复习——第六章“排序”——选择排序
2014.06.17 01:17
简介：
选择排序是一种O(n^2)级别的交换排序算法，属于新手必学算法。
描述：
个人觉得选择排序的代码是所有排序中最直观，最符合人类大脑思维的了。当我第一次有排序的需求时（初中时自学了一点C语言，算是人生第一次写代码），我自己试着写下的代码就是选择排序，当然我上了大学才知道“选择排序”是什么。很显然，直观且容易实现的算法基本都是最鹾的，而不直观且容易实现的算法基本都是最神的。很显然，选择排序很差劲。除了学习之外，基本不可能带到工作里了。分析worst case，average case和best case之后，选择排序的缺点显而易见——交换次数与逆序数成正比，比较次数始终是O(n^2)。
实现：
1 // My implementation for selection sort. 2 #include <iostream> 3 #include <vector> 4 using namespace std; 5 6 void selectionSort(vector<int> &v) 7 { 8 int n, i, j; 9 int val;10 11 n = (int)v.size();12 for (i = 0; i < n; ++i) {13 for (j = i + 1; j < n; ++j) {14 if (v[i] > v[j]) {15 val = v[i];16 v[i] = v[j];17 v[j] = val;18 }19 }20 }21 }22 23 int main()24 {25 vector<int> v;26 int n, i;27 28 while (cin >> n && n > 0) {29 v.resize(n);30 for (i = 0; i < n; ++i) {31 cin >> v[i];32 }33 selectionSort(v);34 for (i = 0; i < n; ++i) {35 cout << v[i] << ‘ ‘;36 }37 cout << endl;38 }39 40 return 0;41 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。