首页 > 代码库 > C++中的冒泡排序,选择排序,插入排序
C++中的冒泡排序,选择排序,插入排序
最简单的插入排序:思想,两两之间比较,时间复杂度o(n^2)
void bubblesort(vector<int>&vec, int n){ if (&vec==NULL) return; int temp; bool flag; for (int i = 0; i < n - 1; i++)//外层循环控制循环次数 { flag = false;//判断是否有序的标志 for (int j = 0; j < n - 1 - i; j++)//内层循环控制边界 { if (vec[j]>vec[j + 1]) { temp = vec[j]; vec[j] = vec[j + 1]; vec[j + 1] = temp; flag = true; } } if (!flag) break; } }
2.选择排序,思想:假定每轮循环的第一个元素为最值,然后从后面未排序的元素中挑选出最值,与之交换.
void selectsort(vector<int>&vec, int n){ if (&vec == NULL) return; int key; int min; int temp; for (int i = 0; i < n - 1; i++)//外层控制循环次数 { key = vec[i]; min = i; for (int j = i + 1; j < n; j++)//内层控制循环的边界 { if (vec[j] < key) { min = j;//记录最小值的索引值 key = vec[j];//记录最小值 } } if (min != i)//如果有变化,则交换 { temp = vec[i]; vec[i] = vec[min]; vec[min] = temp; } } }
3.插入排序,思想:每次都从未排序的集合中,取一个元素插入到已经排好序的数组中,注意用数组和用vector时判断条件的区别
void insertsort(vector<int>&vec, int n)//这里必须传递引用,因为这是一个类对象,不同于数组{ if (&vec == NULL) return; int key; for (int i = 1; i < n; i++) { key = vec[i];//暂存要插入的值 int j = i;//暂存要插入的下标 while (j>0&&key < vec[j - 1])//注意:换成 while(key<vec[j-1]&&j>0)则报错,而如果是数组则没问题,因为vector检查更严格,更安全,不允许vec[-1]的出现(下标越界). { vec[j] = vec[j - 1];//依次往后移动一位 j--; } if (i!=j)//如果下标有变化,说明插入位置有变,需要重新插入 vec[j] = key; }}
C++中的冒泡排序,选择排序,插入排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。