数据结构七种排序算法详解

72 阅读 0 评论 48 点赞

我是靠谱客的博主激动猫咪，最近开发中收集的这篇文章主要介绍数据结构七种排序算法详解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

　　排序算法大体可分为两种：

　　　　一种是比较排序，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

　　　　另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

代码书写的排序法有：

一、冒泡（Bubble）排序——相邻交换

冒泡排序是一种极其简单的排序算法，也是我所学的第一个排序算法。它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

　　冒泡排序算法的运作如下：

比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行冒泡排序的实现过程如下

尽管冒泡排序是最容易了解和实现的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。

二、插入排序——将下一个插入已排好的序列中

　插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌

　　对于未排序数据(右手抓到的牌)，在已排序序列(左手已经排好序的手牌)中从后向前扫描，找到相应位置并插入。

　　插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

　　具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行插入排序的实现过程如下

三、希尔（Shell）排序——缩小增量

　希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。

　　希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

　　希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
　　假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n^2)的排序（冒泡排序或直接插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。

　希尔排序是不稳定的排序算法，虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。

　　比如序列：{ 3, 5, 10, 8, 7, 2, 8, 1, 20, 6 }，h=2时分成两个子序列 { 3, 10, 7, 8, 20 } 和 { 5, 8, 2, 1, 6 } ，未排序之前第二个子序列中的8在前面，现在对两个子序列进行插入排序，得到 { 3, 7, 8, 10, 20 } 和 { 1, 2, 5, 6, 8 } ，即 { 3, 1, 7, 2, 8, 5, 10, 6, 20, 8 } ，两个8的相对次序发生了改变。

四、选择排序——每次最小/大排在相应的位置

　选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

　　注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

对序列{ 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }进行选择排序的实现过程如图

选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。比如序列：{ 5, 8, 5, 2, 9 }，一次选择的最小元素是2，然后把2和第一个5进行交换，从而改变了两个元素5的相对次序。

五、堆排序

　堆排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。

　　我们可以很容易的定义堆排序的过程：

由输入的无序数组构造一个最大堆，作为初始的无序区
把堆顶元素（最大值）和堆尾元素互换
把堆（无序区）的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
重复步骤2，直到堆的尺寸为1

　　堆排序是不稳定的排序算法，不稳定发生在堆顶元素与A[i]交换的时刻。

　　比如序列：{ 9, 5, 7, 5 }，堆顶元素是9，堆排序下一步将9和第二个5进行交换，得到序列 { 5, 5, 7, 9 }，再进行堆调整得到{ 7, 5, 5, 9 }，重复之前的操作最后得到{ 5, 5, 7, 9 }从而改变了两个5的相对次序。

六、归并排序

归并排序是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)，1945年由冯·诺伊曼首次提出。

　　归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。

　　归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作，归并操作步骤如下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

　上述代码对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行归并排序的实例如下　

七、快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

　　快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：

从序列中挑出一个元素，作为"基准"(pivot).
把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

　快速排序是不稳定的排序算法，不稳定发生在基准元素与A[tail+1]交换的时刻。

　　比如序列：{ 1, 3, 4, 2, 8, 9, 8, 7, 5 }，基准元素是5，一次划分操作后5要和第一个8进行交换，从而改变了两个元素8的相对次序。

注：本文代码是自己写的，算法过程是从网上找的，原文链接：https://www.cnblogs.com/eniac12/p/5329396.html

代码统一输入接口为数组及数组元素个数

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxsize=10;
void bubble_sort(int a[],int n)//冒泡排序
{
int flag;
for(int i=0;i<n-1;i++)
{
flag=0;
for(int j=0;j<n-i-1;j++)
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
flag=1;
}
if(!flag)
break;
}
}
void insert_sort(int a[],int n)//插入排序
{
int tmp,j;
for(int i=1;i<n;i++)
{
tmp=a[i];
for(j=i-1;a[j]>tmp&&j>=0;j--)
a[j+1]=a[j];
a[j+1]=tmp;
}
}
void shell_sort(int a[],int n)//希尔排序
{
int k,tmp,j;
int d[n];
for(k=0;pow(2.0,k+1)-1<n*1.0;k++)
d[k]=(int)(pow(2.0,k+1)-1);//选定增量序列
while(k--)
{
for(int i=d[k];i<n;i++)
{
tmp=a[i];
for(j=i;j>=d[k]&&a[j-d[k]]>tmp;j-=d[k])
a[j]=a[j-d[k]];
a[j]=tmp;
}
}
}
void select_sort(int a[],int n)//选择排序
{
int tmp;
for(int i=0;i<n;i++)
{
tmp=i;
for(int j=i+1;j<n;j++)
if(a[j]<a[tmp])
tmp=j;
swap(a[i],a[tmp]);
}
}
void percdown(int a[],int start,int end)//下滤
{
int ch;
for(int pa=start;pa*2+1<=end-1;pa=ch)
{
ch=pa*2+1;
if(ch!=end-1&&a[ch]<a[ch+1])
ch++;
if(a[ch]>a[pa])
swap(a[ch],a[pa]);
else
break;
}
}
void heap_sort(int a[],int n)//堆排序
{
for(int i=n/2;i>=0;i--)
percdown(a,i,n);
for(int i=n-1;i>=0;i--)
{
swap(a[0],a[i]);
percdown(a,0,i);
}
}
void merge(int a[],int tmp[],int ls,int rs,int re)
//归并ls表示要归并的第一个数组最左边元素序号，由于这里对数组a进行归并a分成两部分后第一部分末端与第二部分开始是连着的
//所以直接用rs就可以控制，re表示第二个数组最右边元素序号
{
int i=ls,j=rs,k=ls,num=re-ls+1;
while(i<=rs-1&&j<=re)//归并
if(a[i]<=a[j])
tmp[k++]=a[i++];
else
tmp[k++]=a[j++];
while(i<=rs-1)//剩余元素进去
tmp[k++]=a[i++];
while(j<=re)//剩余元素进去 ，两个while必只执行一个
tmp[k++]=a[j++];
for(int i=0;i<num;i++,re--)
a[re]=tmp[re];
}
void msort(int a[],int tmp[],int start,int end)//归并排序
{
if(start<end)
{
int mid=(start+end)/2;
msort(a,tmp,start,mid);
msort(a,tmp,mid+1,end);
merge(a,tmp,start,mid+1,end);
}
}
void merge_sort(int a[],int n)//统一接口
{
int *tmp=new int[10];
if(tmp)
{
msort(a,tmp,0,n-1);
delete [] tmp;
}
else
return;
}
int median3(int a[],int left,int right)//快速排序选前中末中位数轴，当然也可以不用这个，直接选数组第一个数为轴
{
int mid=(left+right)/2;
if(a[left]>a[mid])
swap(a[left],a[mid]);
if(a[left]>a[right])
swap(a[left],a[right]);
if(a[mid]>a[right])
swap(a[mid],a[right]);
swap(a[mid],a[right-1]);
return a[right-1];
}
void Qsort(int a[],int left,int right)//浙大版快排
{
int i,j,pivot;
if(left<right)
{
pivot=median3(a,left,right);//也可以直接写pivot=a[left]
i=left,j=right-1;
while(1)
{
while(a[++i]<pivot);
while(a[--j]>pivot);
if(i<j)
swap(a[i],a[j]);
else
break;
}
swap(a[i],a[right-1]);
Qsort(a,left,i-1);
Qsort(a,i+1,right);
}
}
void quick_sort(int a[],int n)//快排统一接口
{
Qsort(a,0,n-1);
}
void Qsort2(int a[],int left,int right)//严蔚敏版快排
{
if(left<right)
{
int i=left,j=right;
int tmp=a[left];
while(i<j)
{
while(i<j&&a[j]>=tmp)
j--;
a[i]=a[j];
while(i<j&&a[i]<=tmp)
i++;
a[j]=a[i];
}
a[i]=tmp;
Qsort2(a,left,i-1);
Qsort2(a,i+1,right);
}
}
void quick_sort2(int a[],int n)//快排统一接口
{
Qsort2(a,0,n-1);
}
int main()
{
int a[10]={3,4,5,7,8,0,2,1,9,6};
//bubble_sort(a,10);
//insertsort(a,10);
//shell_sort(a,10);
//select_sort(a,10);
heap_sort(a,10);
//merge_sort(a,10);
for(int i=0;i<10;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}