排序算法是最基本最常用的算法，不同的排序算法在不同的场景或运用中会有不同的体现，咱们需求对各种排序算法娴熟才干将它们运用到实践傍边，才干更好地发挥它们的优势。今日，来总结下各种排序算法。

下面这个表格总结了各种排序算法的复杂度与稳定性：

各种排序算法复杂度比较.png

冒泡排序

冒泡排序可谓是最经典的排序算法了，它是根据比较的排序算法，时刻复杂度为O(n^2)，其长处是完结简略，n较小时功能较好。

• 算法原理
  相邻的数据进行两两比较，小数放在前面，大数放在后边，这样一趟下来，最小的数就被排在了***位，第二趟也是如此，如此类推，直到一切的数据排序完结

• c++代码完结

voidbubble_sort(intarr[],intlen)
{
for(inti=0;i<len-1;i++)
{
for(intj=len-1;j>=i;j--)
{
if(arr[j]<arr[j-1])
{
inttemp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
}
}

挑选排序

• 算法原理
  先在未排序序列中找到最小（大）元素，存放到排序序列的开始方位，然后，再从剩下未排序元素中持续寻觅最小（大）元素，然后放到已排序序列的结尾。以此类推，直到一切元素均排序结束。

• c++代码完结

voidselect_sort(intarr[],intlen)
{
for(inti=0;i<len;i++)
{
intindex=i;
for(intj=i+1;j<len;j++)
{
if(arr[j]<arr[index])
index=j;
}
if(index!=i)
{
inttemp=arr[i];
arr[i]=arr[index];
arr[index]=temp;
}
}
}

刺进排序

• 算法原理
  将数据分为两部分，有序部分与无序部分，一开始有序部分包括第1个元素，顺次将无序的元素刺进到有序部分，直到一切元素有序。刺进排序又分为直接刺进排序、二分刺进排序、链表刺进等，这儿只评论直接刺进排序。它是稳定的排序算法，时刻复杂度为O(n^2)

• c++代码完结

voidinsert_sort(intarr[],intlen)
{
for(inti=1;i<len;i++)
{
intj=i-1;
intk=arr[i];
while(j>-1&&k<arr[j])
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=k;
}
}

快速排序

• 算法原理
  快速排序是现在在实践中十分高效的一种排序算法，它不是稳定的排序算法，均匀时刻复杂度为O(nlogn)，最差情况下复杂度为O(n^2)。它的基本思想是：经过一趟排序即将排序的数据分割成独立的两部分，其间一部分的一切数据都比别的一部分的一切数据都要小，然后再按此办法对这两部分数据别离进行快速排序，整个排序进程能够递归进行，以此到达整个数据变成有序序列。

• c++代码完结

voidquick_sort(intarr[],intleft,intright)
{
if(left<right)
{
inti=left,j=right,target=arr[left];
while(i<j)
{
while(i<j&&arr[j]>target)
j--;
if(i<j)
arr[i++]=arr[j];
while(i<j&&arr[i]<target)
i++;
if(i<j)
arr[j]=arr[i];
}
arr[i]=target;
quick_sort(arr,left,i-1);
quick_sort(arr,i+1,right);
}
}

归并排序

• 算法原理
  归并排序具体工作原理如下（假定序列共有n个元素）：

  • 将序列每相邻两个数字进行归并操作（merge)，构成floor(n/2)个序列，排序后每个序列包括两个元素
  • 将上述序列再次归并，构成floor(n/4)个序列，每个序列包括四个元素

  • 重复过程2，直到一切元素排序结束

    归并排序是稳定的排序算法，其时刻复杂度为O(nlogn)，假如是运用链表的完结的话，空间复杂度能够到达O(1)，但假如是运用数组来存储数据的话，在归并的进程中，需求暂时空间来存储归并好的数据，所以空间复杂度为O(n)

• c++代码完结

voidmerge(intarr[],inttemp_arr[],intstart_index,intmid_index,intend_index)
{
inti=start_index,j=mid_index+1;
intk=0;
while(i<mid_index+1&&j<end_index+1)
{
if(arr[i]>arr[j])
temp_arr[k++]=arr[j++];
else
temp_arr[k++]=arr[i++];
}
while(i<mid_index+1)
{
temp_arr[k++]=arr[i++];
}
while(j<end_index+1)
temp_arr[k++]=arr[j++];
for(i=0,j=start_index;j<end_index+1;i++,j++)
arr[j]=temp_arr[i];
}
voidmerge_sort(intarr[],inttemp_arr[],intstart_index,intend_index)
{
if(start_index<end_index)
{
intmid_index=(start_index+end_index)/2;
merge_sort(arr,temp_arr,start_index,mid_index);
merge_sort(arr,temp_arr,mid_index+1,end_index);
merge(arr,temp_arr,start_index,mid_index,end_index);
}
}

堆排序

二叉堆

二叉堆是彻底二叉树或许近似彻底二叉树，满意两个特性

• 父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值
• 每个结点的左子树和右子树都是一个二叉堆

当父结点的键值总是大于或等于任何一个子节点的键值时为***堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。一般二叉树简称为堆。

堆的存储

一般都是数组来存储堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标别离为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标别离为1和2。存储结构如图所示：

堆结构.png

堆排序原理

堆排序的时刻复杂度为O(nlogn)

• 算法原理（以***堆为例）

  • 先将初始数据R[1..n]建成一个***堆，此堆为初始的无序区
  • 再将关键字***的记载R[1]（即堆顶）和无序区的***一个记载R[n]交流，由此得到新的无序区R[1..n-1]和有序区R[n]，且满意R[1..n-1].keys≤R[n].key
  • 因为交流后新的根R[1]或许违背堆性质，故应将当时无序区R[1..n-1]调整为堆。
  • 重复2、3过程，直到无序区只要一个元素停止。

• c++代码完结

/**
*将数组arr构建大根堆
*@paramarr待调整的数组
*@parami待调整的数组元素的下标
*@paramlen数组的长度
*/
voidheap_adjust(intarr[],inti,intlen)
{
intchild;
inttemp;
for(;2*i+1<len;i=child)
{
child=2*i+1;//子结点的方位=2*父结点的方位+1
//得到子结点中键值较大的结点
if(child<len-1&&arr[child+1]>arr[child])
child++;
//假如较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
if(arr[i]<arr[child])
{
temp=arr[i];
arr[i]=arr[child];
arr[child]=temp;
}
else
break;
}
}
/**
*堆排序算法
*/
voidheap_sort(intarr[],intlen)
{
inti;
//调整序列的前半部分元素，调整完之后***个元素是序列的***的元素
for(inti=len/2-1;i>=0;i--)
{
heap_adjust(arr,i,len);
}
for(i=len-1;i>0;i--)
{
//将第1个元素与当时***一个元素交流，确保当时的***一个方位的元素都是现在的这个序列中***的
inttemp=arr[0];
arr[0]=arr[i];
arr[i]=temp;
//不断缩小调整heap的规模，每一次调整结束确保***个元素是当时序列的***值
heap_adjust(arr,0,i);
}
}