算法周周练,一天一天努力,一点一点积累
期限:3天;题目:1道;类型:基础、排序算法
1、完成三种排序算法:冒泡排序、选择排序、插入排序
2、研究并理解透各个算法特点
排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
希尔排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
1、冒泡排序
算法思想:两两比较待排序的数据,如果反序则交换,直到没有反序的记录为止。原则把小的数交换到最前面。
void bubbleSort(vector<int> &A){ for(int i=0;i<A.size();i++){ for(int j=i+1;j<A.size();j++){ if(A[i]>A[j]) swap(A[i],A[j]); } } }
2、选择排序
算法思想:每次在n-i+1(i=1,2,…,n-1) 个记录中选取关键字最小的记录作为有序序列的第i个记录,即从剩余数据中依次选择最小的。
void quickSort(vector<int> &A){ for(int i=0;i<A.size();i++){ //默认当前i位置最小 int k=i; //依次遍历i之后的数据,将最小的记录到k for(int j=i+1;j<A.size();j++){ if(A[j]<A[k]) k=j; } //如果最小的是A[i]不用变,若不是则将最小的交换到A[i] if(k!=i){ swap(A[i],A[k]); } } }
3、插入排序
算法思想:每次从待插入组中取出一个元素,与有序组的元素进行比较,并找到合适的位置,将该元素插到有序组当中。
//插入排序 //将一个记录插入到已经排好序的有序表。 void insertionSort(vector<int> &A) { if(A.size()==0) return; //从1开始:假设A[0]已放好。 for(int i=1;i<A.size();i++){ //A[i]与前面有序数列的最大一个比较,若小于则插入,若大于则继续下一个数 if(A[i]<A[i-1]){ int temp=A[i];//记录A[i] int j=i; //后移 while(j>0&&temp<A[j-1]){ A[j]=A[j-1]; j--; } //插入 A[j]=temp; } } }
编辑:孙小北
本文地址: https://www.xiaowangyun.com/wyblog/detail/?id=177
版权归属: www.xiaowangyun.com 转载时请以链接形式注明出处
0 条评论