C 实现主流的几个排序算法
排序算法是笔试中常考的题目,很多面试者背了整个算法代码,过一段时间就又忘记了. 面试者在面试过程中往往处于一种比较紧张的状态, 若对代码不是很熟悉的话, 基本很难完整编写排序算法代码.
小编最近也在看工作机会,于是用C++实现了主流的几个排序算法.
包括:
冒泡排序
选择排序
插入排序
希尔排序
归并排序
快速排序
1. 冒泡排序
冒泡排序是每循环一次选择最大(最小)的值放在最右边,即重复地走访过要排序的数列,一次比较两个元素,如果它们顺序错误,就交换位置.
代码:
// 冒泡排序void BubbleSort(vector<int> &vec){ int l1 = vec.size(); for(int i =0;i<l1;i++) for(int j =0;j<l1-i-1;j++) { if(vec[j]>vec[j+1]) { int temp = vec[j+1]; vec[j+1] = vec[j]; vec[j] = temp; } }}2. 选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
// 选择排序void SelectionSort(vector<int> &vec){int l1 = vec.size();for(int i = 0;i < l1-1;i++){for(int j = i+1;j < l1;j++){// 找最小值if(vec[i] > vec[j]){int temp = vec[j];vec[j] = vec[i];vec[i] = temp;}}}}
3. 插入排序
插入排序(Insertion-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入.
// 插入排序,优化void InsertionSort(vector<int> &vec){ int l1 = vec.size(); for(int i=1;i<l1;i++) { int temp = vec[i]; int j = i-1; while(j>=0 && vec[j]>temp) { vec[j+1] = vec[j]; j = j-1; } vec[j+1] = temp; }}4. 希尔排序
希尔排序(Shell-sort)是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序
// 希尔排序,优化void ShellSort(vector<int> &vec){int l1 = vec.size();//增量逐渐减小for(int gap = l1/2;gap>=1;gap/=2){// 遍历for(int i =gap;i<l1;i++){//插入排序int temp = vec[i];int j = i -gap;while(j>=0 && vec[j]>temp){vec[j+gap] = vec[j];j = j -gap;}vec[j+gap] = temp;}}}
5. 归并排序
归并排序(Merge-sort)是是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案'修补'在一起，即分而治之)。
// 拆分void MySort(vector<int> &vec,const int &first,const int &last){ //// int middle = (first + last)/2; if(first < last) { int middle = (first + last)/2; MySort(vec,first,middle); MySort(vec,middle+1,last); // 并 MergeVector(vec,first,middle,last); }}
// 合并向量2,已知合并向量的长度void MergeVector(vector<int> &vec,const int &first,const int &middle,const int &last){ vector<int> vec3; int i = first; // 合并两个向量 int j = middle + 1; // 找到插入点 while(i<=middle && j<=last) { if(vec[i]>vec[j]){ vec3.push_back(vec[j]); j++; } else { vec3.push_back(vec[i]); i++; } } if(i==middle+1) { for(int k=j;k<=last;k++) vec3.push_back(vec[k]); } else { for(int k=i;k<=middle;k++) vec3.push_back(vec[k]); } // 赋值 for(int i=first;i<=last;i++) vec[i] = vec3[i-first];}6. 快速排序
快速排序(Quick-sort)的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
// 快速排序void QuickSort(vector<int> &vec,const int&first,const int&last){//if(first < last){//int middle = (first + last)/2;// 分QuickSort(vec,first,middle);QuickSort(vec,middle+1,last);QuickSortSupplement(vec,first,last);}}void QuickSortSupplement(vector<int> vec,const int&first,const int&last){int middle = first;int key = vec[middle];int i = first;int j = first + 1;while(j<=last){if(key>vec[j]){//放参考值左边int temp = key;vec[i] = vec[j];i++;vec[i] = temp;}j++;}}