排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。
性质
稳定性
稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 R 和 S，且在原本的列表中 R 出现在 S 之前，在排序过的列表中 R 也将会是在 S 之前。
基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。
选择排序、堆排序、快速排序、希尔排序不是稳定排序。
选择排序
定义
选择排序（英语：Selection sort）是一种简单直观的排序算法。它的工作原理是每次找出第 i 小的元素（也就是A[i..n]中最小的元素），然后将这个元素与数组第 i 个位置上的元素交换。
时间复杂度
选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O(n2)。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
//打印数组
void print(int a[] ,int n){
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
//交换元素
void swap(int a[] ,int i,int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//选择排序
void selectSort(int a[],int n){
int minInd;
for (int i=0;i<n-1;i++){
minInd = i;
for(int j=i+1;j<n;j++){
if(a[j]<a[minInd]){
minInd = j;
}
}
swap(a,i,minInd);
}
}
int main()
{
//int a[10]={8,1,9,7,2,4,5,6,10,3};
int a[10]={8,1,9,7,2,4,5,6,10,3};
cout<<"初始序列：";
print(a,10);
selectSort(a,10);
cout<<"排序结果：" ;
print(a,10);
return 0;
}
冒泡排序
它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
经过 i 次扫描后，数列的末尾 i 项必然是最大的 i 项，因此冒泡排序最多需要扫描 n-1 遍数组就能完成排序。
冒泡排序是一种稳定的排序算法。
在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为O(n) 。
在最坏情况下，冒泡排序要执行
(n-1)*n/2
次交换操作，时间复杂度为O(n2) 。
冒泡排序的平均时间复杂度为 O(n2) 。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
//打印数组
void print(int a[] ,int n){
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
//交换元素
void swap(int a[] ,int i,int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void BubbleSort(int a[],int n){
for(int i = n-1;i>0;i--){
for (int j=0;j<i;j++){
if(a[j]>a[j+1]){
swap(a,j,j+1);
}
}
}
}
int main()
{
int a[10]={8,1,9,7,2,4,5,6,10,3};
cout<<"初始序列：";
print(a,10);
BubbleSort(a,10);
cout<<"排序结果：" ;
print(a,10);
return 0;
}
插入排序
插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
无序数组：
把数组的首元素5作为有序区，此时有序区只有这一个元素：
第一轮
让元素8和有序区的元素依次比较。
8>5，所以元素8和元素5无需交换。
此时有序区的元素增加到两个：
第二轮
让元素6和有序区的元素依次比较。
6<8，所以把元素6和元素8进行交换：
6>5，所以把元素6和元素5无需交换。
此时有序区的元素增加到三个：
第三轮
让元素3和有序区的元素依次比较。
3<8，所以把元素3和元素8进行交换：
3<6，所以把元素3和元素6进行交换：
3<5，所以把元素3和元素5进行交换：
此时有序区的元素增加到四个：
以此类推，插入排序一共会进行（数组长度-1）轮，每一轮的结果如下：
稳定性
插入排序是一种稳定的排序算法。
时间复杂度
插入排序的最优时间复杂度为O(n) ，在数列几乎有序时效率很高。
插入排序的最坏时间复杂度和平均时间复杂度都为O(n2) 。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
//打印数组
void print(int a[] ,int n){
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
//交换元素
void swap(int a[] ,int i,int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void insertSort(int a[],int n){
for(int i=1;i<n;i++){
for(int j=i;j>0;j--){
if(a[j]<a[j-1]){
swap(a,j,j-1);
}
}
}
}
int main()
{
int a[10]={8,1,9,7,2,4,5,6,10,3};
cout<<"初始序列：";
print(a,10);
insertSort(a,10);
cout<<"排序结果：" ;
print(a,10);
return 0;
}
其他写法
#include<iostream>
using namespace std;
int main()
{
int arr[]={12,45,13,88,79,11,52,66}; //定义数组
int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度
for(int i=1;i<len;i++){ //遍历无序部分，
int tmp=arr[i],j=i-1; //j为当前下标，tmp为无序部分第一个元素
while(j>=0&&tmp<arr[j]){ //找到k元素在有序部分的位置
arr[j+1]=arr[j]; //循环的时候直接右移有序数组，为tmp空出位置
j--; //不是tmp正确位置，继续循环往前
}
arr[j+1]=tmp; //出来的时候j多减1，要加回去
/*
for(int i=0;i<len;i++)
cout<<arr[i]<<" ";
cout<<endl;
*/
}
}
问题及改进
插入排序是将一个一个的元素单独进行插入，效率较慢，可以考虑把一个有序的序列直接插入到数组中，这样速度就比较快了。也就是希尔排序的思想。
希尔排序
也称为缩小增量排序法，是 插入排序 的一种改进版本。
过程
排序对不相邻的记录进行比较和移动：
1、将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
2、对这些子序列进行插入排序；
3、减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。
void Shell_sort(int arr[], int n)
{
int i,j,inc,key;
//初始增量：n/2 每一趟之后除以2
for(inc = n/2;inc>0;inc /=2){
//每一趟采用插入排序
for(i=inc ;i<n;i++){
key = arr[i];
for(j=i;j>=inc && key<arr[j-inc];j-=inc)
arr[j]=arr[j-inc];
arr[j]=key;
}
}
桶排序（Bucket sort）
工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。
#include<bits/stdc++.h>
#include <iostream> // cin cout的头文件 基本输入流
#include <iomanip> //cout输出时，保留小数fixed、setprecision的头文件 参数化输入／输出
#include <cstdio> //scanf、printf的头文件 定义输入／输出函数
#include <cmath> //sqrt()求平方根、定义数学函数
#include <algorithm> //STL通用算法
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
int b[101],n,i,j,k;
int main(){
cin>>n;
for(i=1;i<=n;i++){
cin>>k;
b[k]++;
}
for(i=0;i<=100;i++){
while(b[i]>0){
cout<<i<<" ";
b[i]--;
}
}
cout<<endl;
return 0;
}
堆排序
大根堆：所有父节点大于等于孩子节点
排序思想
1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
构造堆
首先我们给定一个无序的序列，将其看做一个堆结构，一个没有规则的二叉树，将序列里的值按照从上往下，从左到右依次填充到二叉树中。
对于一个完全二叉树，在填满的情况下（非叶子节点都有两个子节点），每一层的元素个数是上一层的二倍，根节点数量是1，所以最后一层的节点数量，一定是之前所有层节点总数+1，所以，我们能找到最后一层的第一个节点的索引，即节点总数/2（根节点索引为0），这也就是第一个叶子节点，所以第一个非叶子节点的索引就是第一个叶子结点的索引-1。那么对于填不满的二叉树呢？这个计算方式仍然适用，当我们从上往下，从左往右填充二叉树的过程中，第一个叶子节点，一定是序列长度/2，所以第最后一个非叶子节点的索引就是 arr.len / 2 -1，对于此图数组长度为5，最后一个非叶子节点为5/2-1=1，即为6这个节点
那么如何构建呢？ 我们找到了最后一个非叶子节点，即元素值为6的节点，比较它的左右节点中最大的一个的值，是否比他大，如果大就交换位置。
在这里5小于6,而9大于6，则交换6和9的位置
找到下一个非叶子节点4，用它和它的左右子节点进行比较，4大于3，而4小于9，交换4和9位置
此时发现4小于5和6这两个子节点，我们需要进行调整，左右节点5和6中，6大于5且6大于父节点4，因此交换4和6的位置
此时我们就构造出来一个大根堆,下来进行排序
首先将顶点元素9与末尾元素4交换位置，此时末尾数字为最大值。排除已经确定的最大元素，将剩下元素重新构建大根堆
一次交换重构如图:
此时元素9已经有序，末尾元素则为4(每调整一次，调整后的尾部元素在下次调整重构时都不能动)
二次交换重构如图:
最终排序结果:
void heapify(int arr[],int n,int i){//维护大根堆结构
int largest =i;
int lson = i*2+1;
int rson = i*2+2;
if(lson <n && arr[largest]<arr[lson])
largest = lson;
if(rson <n && arr[largest]<arr[rson])
largest = rson;
if(largest!=i){
swap(&arr[largest],&arr[i]);
heapify(arr,n,largest);
}
}
//堆排序入口
void heap_sort(int arr[], int n)
{
int i;
//建堆
for(i=n/2-1;i>=0;i--){//i的初始值 i=(n-1-1)/2
heapify(arr,n,i);
}
//排序
for(i=n-1;i>0;i--){
swap(&arr[i],&arr[0]);//最后一个元素与大顶堆第0个元素交换
heapify(arr,i,0);//重新维护剩余元素变成符合要求的大顶堆
}
快速排序
快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个，最后一个，也可以是中间任何一个)，习惯将其称为pivot。
将所有比枢轴元素小的放在其左边；
将所有比它大的放在其右边；
形成左右两个子表；
然后对左右两个子表再按照前面的算法进行排序，直到每个子表的元素只剩下一个。
可见快速排序用到了分而治之的思想。
将一个数组分成两个数组的方法为：
先从数组右边找到一个比枢轴元素小的元素，将数组的第一个位置赋值为该元素；
再从数组的左边找到一个比枢轴元素大的元素，将从上面取元素的位置赋值为该值；
依次进行，直到左右相遇，把枢轴元素赋值到相遇位置。
例子
输入数组
arr 为 [39 , 28 , 55 , 87 , 66 , 3 ,17 ,39*]
为了区别两个相同元素，将最后一个加上 * ；
初始状态如下图：
定义一枢轴元素pivot，初始化为第一个元素的值，即39；
查询左边的元素的变量为left，初始值为第一个元素的索引,0;
查询右边的元素的变量为right，初始值为第一个元素的索引,7。
演示第一轮排序过程
从右边开始，从右边找到一个比枢轴元素小的，如果没找到right一直自减1；
然后把当前left所在元素赋值为该值；
这里right所指元素并没有空，只是为了好演示，设置为空（下同）；
然后从左边开始找一个比枢轴元素pivot大的元素；如果没找到left一直自增1；
将当前right所指元素设为该值；
然后从右边找到一个比枢轴元素小的，如果没找到right一直自减1；
将当前left所指元素设为该值；
然后从左边开始找一个比枢轴元素pivot大的元素；如果没找到left一直自增1；
将当前right所指元素设为该值；
然后从右边找到一个比枢轴元素小的，如果没找到right一直自减1；
这时left和right相遇了，将枢轴元素赋值给当前位置。
第一轮排序动态过程：
然后将数组分成了
[17,28,3] 与 [66, 87, 55, 39*]两部分；
再对这两部分进行上述环节即可。
反反复复，直到只剩下一个元素。
代码
对每一个数组进行分化的代码如下：
初始化pivot为数组第一个元素；
只要left还小于right就进行循环；
外层循环内部如下：
先从右边找一个比枢轴元素小的元素；
将当前left所指元素赋值为找到的元素；
再从左边找一个比枢轴元素大的元素；
将当前right所指元素赋值为找到的元素；
当left和right相等将枢轴元素赋值在此。
最后返回中间元素的索引。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
//打印数组
void print(int a[] ,int n){
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
//快速排序
void quickSort(int arr[],int L,int R){
if(L>=R)
return ;
int left = L,right=R;
int pivot = arr[left];
while(left < right){
while(left<right && arr[right]>=pivot){
right--;
}
if(left<right){
arr[left]=arr[right];
}
while(left<right && arr[left]<=pivot){
left++;
}
if(left<right){
arr[right]=arr[left];
}
if(left>=right){
arr[left]=pivot;
}
}
quickSort(arr,L,right-1);
quickSort(arr,right+1,R);
}
int main()
{
int a[10]={8,1,9,7,2,4,5,6,10,3};
cout<<"初始序列：";
print(a,10);
quickSort(a,0,9);
cout<<"排序结果：" ;
print(a,10);
return 0;
}
归并排序
归并排序是一种分治的思想，将大问题拆解成为小问题，将一个大的数组先拆分成几个小的数组，然后再一点点的合并。最终将所有元素归并得到一个有序数组，所以这种排序方法称作为归并排序。
步骤
归并排序主要涉及两个部分：一个是递归问题；另一个就是有序数组进行归并。
** 实现1：拆解**
（1）首先，我们要将一个大的数组，拆分成为若干个小的数组，这里的“拆分”，是使用递归的方式来实现的。
拆分实现思路：
设定数组左右索引 L，R
void mergeSort(int L,int R){
if(L<R){
int mid = (L+R)/2;
mergeSort(L,mid);
mergeSort(mid+1,R);
}
}
实现2：合并
在这里，我们直接来看数组 5 9 和数组 4 8 的合并过程。
首先，我们设置一个 索引i 指向第一个数组 5 9 的左端，索引j 指向第二个数组 4 8 的左端，然后设置一个新的数组，用来保存最后合并后的结果。
第一步，我们比较 索引i 指向的值 5 和 索引j 指向的值 4，我们发现 4 比 5 小；
所以第二步，我们首先将 4 存入保存结果的那个新的数组，然后让 索引j 向后移一位，指向数值8；
第三步，再次比较 索引i 指向的值与 索引j 指向的值，依次添加进数组。
这样，我们的数组中存放的值，一定就是有序的了。
void merge(int l,int r,int mid){
int i,j,p;
i=l;
j=mid;
p=l;
while(i<mid && j<=r){
if(a[i]<a[j]){
temp[p++]=a[i++];
}else{
temp[p++]=a[j++];
}
}
while(i<mid){
temp[p++]=a[i++];
}
while(j<=r){
temp[p++]=a[j++];
}
p=l;i=l;
while(p<=r){
a[i++]=temp[p++];
}
}
归并完整代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 9;
int a[maxn]= {0,8,4,5,7,1,3,6,2};
int temp[maxn];
void merge(int l,int r,int mid){
int i,j,p;
i=l;
j=mid;
p=l;
while(i<mid && j<=r){
if(a[i]<a[j]){
temp[p++]=a[i++];
}else{
temp[p++]=a[j++];
}
}
while(i<mid){
temp[p++]=a[i++];
}
while(j<=r){
temp[p++]=a[j++];
}
p=l;i=l;
while(p<=r){
a[i++]=temp[p++];
}
}
void mergeSort(int L,int R){
if(L<R){
int mid = (L+R)/2;
mergeSort(L,mid);
mergeSort(mid+1,R);
merge(L,R,mid+1);
}
}
int main()
{
mergeSort(1,8);
for(int i =1 ;i<=8;i++){
cout<<a[i];
}
return 0;
}
sort()函数
头文件 #include <algorithm>
基本操作说明
** 调用格式：sort(first, last, comp)**
参数说明：
first : 待排序数组起始地址；
last : 待排序数组结束地址；
comp : 排序方式，该参数是可省参数，如果省略则以升序方式排序；
一维数组排序
如：sort(a,a+n) 表示对a[0] a[1] a[2] ... a[n-1] 排序，
sort(a+１,a+n+１) 表示对 a[1] a[2] ... a[n] 排序，
sort()排序范围是，第二个参数减第一个参数的差。
bool cmp(int a,int b){
return a>b;}
意思是当a > b时为true，就不交换，a < b时为false，交换。
假设结构体S有三个成员，对结构体进行排序的规则是：先以a进行升序排序，如果a相等则以b进行降序排序，如果b相等则以c进行降序排序；
```对于这类排序实际上与正常排序并没有不同，唯一需要改变的就是comp函数部分，以下是comp函数部分：
bool comp(S x, S y) {
if (x.a != y.a) return x.a < y.a;
if (x.b != y.b) return x.b > y.b;
return x.c > y.c;
}
**stable_sort() 稳定排序，用法与sort()相同。**
评论区