七大排序算法简介与C++实现

1.冒泡排序2.选择排序3.插入排序4.希尔排序5.堆排序6.归并排序7.快速排序

1.冒泡排序

冒泡排序的基本思想：从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大（小）的数据元素放到队尾。 时间复杂度的平均情况为O(n^2),辅助空间复杂度为O(1),是一种稳定排序算法。 代码实现：

#include<vector> using namespace std; template<typename T> void Bubble_sort(vector<T>& vec) { T temp; int space = vec.size(); //需要交换元素的空间大小 int change = 1; //定义标志位，如果为0，则不需要继续循环 while (space!=1&&change) { change = 0; for (size_t i = 1; i < space; i++) { if (vec[i] < vec[i-1]) { change = 1; std::swap(vec[i-1], vec[i]); //保证两两之间的序列性 } } space--; } }

2.选择排序

选择排序的基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 时间复杂度的平均情况为O(n^2),辅助空间复杂度为O(1),是一种不稳定排序算法。 代码实现：

#include<vector> using namespace std; template<typename T> void Selection_sort(vector<T>& vec) { T min; int s_end = 0; int n_begin = 0; while (n_begin!=vec.size()) { min = vec[n_begin]; for (size_t i = n_begin; i < vec.size(); i++) { if (vec[i] < min) { std::swap(min, vec[i]); //找出剩余序列中的最小值 } } vec[s_end++] = min; //将最小值依次赋值给原始数组 n_begin++; } }

3.插入排序

插入排序原理很简单，将一组数据分成两组，分别将其称为有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。当然，插入过程中涉及到了元素的移动。 时间复杂度的平均情况为O(n^2),辅助空间复杂度为O(1),是一种稳定排序算法。 代码实现：

#include<vector> using namespace std; template<typename T> void Insert_sort(vector<T>& vec) { int s_end = 0; //有序组末尾元素 int n_begin = 0; //无序组首元素 T temp; while (n_begin!=vec.size()) { temp = vec[n_begin]; //从无序组获取元素 for (int i = s_end; i >= 0; i--) { if (temp < vec[i]) //将无序组获取元素与有序组比较 { vec[i + 1] = vec[i]; vec[i] = temp; } } n_begin++; //无序组首元素增加 s_end++; //有序组尾元素增加 } }

4.希尔排序

希尔排序的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。 时间复杂度的平均情况为O(n*logn)~O(n^2),辅助空间复杂度为O(1),是一种不稳定排序算法。 代码实现：

#include<vector> using namespace std; template<typename T> void Shell_sort(vector<T>& vec) { for(int gap = vec.size()/2; gap > 0; gap/=2) //增量缩减的循环 { for(int i = gap; i < vec.size();++i) //按gap执行的插入排序 { T temp = vec[i]; int j = i; for(; j >= gap && temp < vec[j - gap]; j-= gap) { vec[j] = vec[j - gap]; } vec[j] = temp; } } }

5.堆排序

在得到最大（小）堆的基础上，将根节点移到数组，然后将剩余的序列重新构造成堆，反复上述操作即可得到一个有序序列。 时间复杂度的平均情况为O(n*logn),辅助空间复杂度为O(1),是一种不稳定排序算法。 代码实现：

#include<vector> using namespace std; //堆的下滤 template<typename T> void percolateDown(int hole,int currentsize,vector<T>* vec) { int child; //定义孩子节点 T temp = (*vec)[hole]; //空洞所在原始位置元素值 for (;hole*2<=currentsize;hole = child) { child = hole * 2; //下一层 if (child!=currentsize&& (*vec)[child+1]< (*vec)[child]) //首先判断是否为最后一层，不为最后一层则比较左右节点大小，为最后一层测首先判断是否有右节点 { ++child; } if ((*vec)[child]<temp) //比较孩子节点元素与空洞所在初始位置元素大小 { (*vec)[hole] = (*vec)[child]; } else { break; } } (*vec)[hole] = temp; //确定空顶最终位置，将原始元素赋值 } //建立堆 template<typename T> void BuildHeap(vector<T>& vec, vector<T>* temp) { int currentsize = vec.size(); //获得原始数组大小 for (size_t i = 0; i < vec.size(); i++) //将原始数组放入堆化数组 { (*temp)[i + 1] = vec[i]; } for (size_t j = currentsize / 2; j > 0; j--) //使堆满足堆序性质 { percolateDown(j, currentsize, temp); } } //取出堆中最小元素并按位置传给原始数组 template<typename T> void deleteMin(vector<T>* temp,vector<T>& vec) { T min; int currentsize = vec.size(); int i = 0; while(currentsize!=0) { min = (*temp)[1]; vec[i] = min; //将最小元素传入原始待排序数组 i++; (*temp)[1] = (*temp)[currentsize--]; percolateDown(1, currentsize, temp); //下滤使得删除元素后，堆依然满足堆序性质 } } //堆排序总体操作 template<typename T> bool Heap_sort(vector<T>& vec) { vector<T>* temp = new vector<T>(vec.size() + 1, 0); //动态分配数组，并且初始化为0以满足下标操作 if (temp == NULL) //判断是否分配成功 { return false; } BuildHeap(vec, temp); //建立堆 deleteMin(temp,vec); //堆排序传给原始数组 delete temp; //释放数组内存 }

6.归并排序

基本思路就是将数组分成二组A，B，如果这两组组内的数据都是有序的，那么就可以很方便的将这两组数据进行排序。可以将A，B组各自再分成两组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的两个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。 时间复杂度的平均情况为O(n*logn),辅助空间复杂度为O(n),是一种稳定排序算法。 代码实现：

#include<vector> using namespace std; //合并 template<typename T> void merge(int begin, int end, int mid,vector<T>& vec, vector<T>* temp) { int l_begin = begin; //定义左半数组开始位置 int r_begin = mid + 1; //定义右半数组开始位置 int m = mid, e = end; //获取左半数组结束位置，右半数组结束位置 int i = 0; //临时存放数组起始位置 while (l_begin <= m && r_begin <= e) //判定边界合法 { if (vec[l_begin] <= vec[r_begin]) //比较左半数组、右半数组大小 { (*temp)[i++]=vec[l_begin++]; } else { (*temp)[i++]=vec[r_begin++]; } } while (l_begin <= m) //其中一个数组结束后，将剩余数组赋值于临时数组 { (*temp)[i++] = vec[l_begin++]; } while (r_begin <= e) //其中一个数组结束后，将剩余数组赋值于临时数组 { (*temp)[i++] = vec[r_begin++]; } for (int k = 0; k < i; k++) //将临时数组赋值于原始数组 { vec[begin+k] = (*temp)[k]; //赋值于原数组特定位置 } } //分解 template<typename T> void Decomposition_merger(int begin, int end, vector<T>& vec,vector<T>* temp) { if (begin<end) { int mid = (begin + end) / 2; Decomposition_merger(begin, mid, vec, temp); //左分解为有序数列 Decomposition_merger(mid + 1, end, vec, temp);//右分解为有序数列 merge(begin, end,mid, vec, temp);//合并两个有序数列 } } //汇总 template<typename T> bool Merge_sort(vector<T>& vec) { int v_begin = 0; //数组开始位置 int v_end = vec.size() - 1; //数组末尾位置 vector<T>* temp; temp = new vector<T>(vec.size(),0); //动态分配数组 if (temp == NULL) //判断是否分配成功 { return false; } Decomposition_merger(v_begin, v_end, vec, temp); //分解合并数组 return true; }

7.快速排序

该方法的基本思想是： 1．先从数列中取出一个数作为基准数。 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。 时间复杂度的平均情况为O(nlogn),辅助空间复杂度为O(nlogn)~O(n),是一种不稳定排序算法。 代码实现：

#include<vector> using namespace std; //插入排序处理小于10个元素的数组 (传入要排序数组的起始点) template<typename T> void insertionSort(vector<T>& vec,int left,int right) { int s_end = left; //有序组末尾元素 int n_begin = left; //无序组首元素 T temp; //临时变量 while (n_begin <= right) { temp = vec[n_begin]; //获取无序组首元素 for (int i = s_end; i >= left; i--) //无序组元素与有序组比较 { if (temp < vec[i]) { vec[i + 1] = vec[i]; vec[i] = temp; } } n_begin++; //位移无序组下标 s_end++; //位移有序组下标 } } //三数中值分割选取枢纽点 template<typename T> const T& median3(vector<T>& a, int left, int right) { int center = (left + right) / 2; //获取中间位置索引 if (a[center]<a[left]) //使得中间索引元素大于首元素 { std::swap(a[left], a[center]); } if (a[right]<a[left]) //使得尾元素大于首元素 { std::swap(a[left], a[right]); } if (a[right]<a[center]) //使得尾元素大于中间索引元素 { std::swap(a[center], a[right]); } std::swap(a[center], a[left]); //将枢纽点即三数元素中值调整至数组第一个位置 return a[left]; } //分治 template<typename T> void quick_sort_diverge(vector<T>& s, int l, int r) { if (l+10<=r) //判断元素个数是否小于或等于10个 { T x = median3(s, l, r); //获取枢纽点元素，此时的枢纽点已经调整至最左边 int i = l, j = r; while (i < j) //判断左向右寻值和右向左寻值的下标是否相互交叉 { while (i < j && s[j] >= x) // 从右向左找第一个小于x的数 j--; if (i < j) s[i++] = s[j]; while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数 i++; if (i < j) s[j--] = s[i]; } s[i] = x; //最后的位置放置枢纽点元素 quick_sort_diverge(s, l, i - 1); // 左部分数组递归调用 quick_sort_diverge(s, i + 1, r); //右部分数组递归调用 } else { insertionSort(s, l, r); //小于等于10个元素使用直接插入排序 } } //数组传递 template<typename T> void Quick_sort(vector<T>& vec) { quick_sort_diverge(vec,0, vec.size()-1); //将原始数组进行传递 }

以上就是七大排序算法的简单介绍和c++实现。 转载请注明出处，原文地址：https://blog.csdn.net/NEUChords/article/details/90451178