概述
排序
- 一.概念
- 二.内排序
- 1.插入排序
- a. 直接插入排序
- b.折半插入排序
- c.希尔排序（缩小增量排序）
- 2.交换排序
- a.冒泡排序（起泡排序）
- b.双向冒泡排序
- c.快速排序
- 3.选择排序
- a.简单选择排序方法
- b.堆排序
- 4.归并排序
- 5.基数排序
- 各种排序的比较总结
一.概念
内排序和外排序：
在排序过程中，若整个表都是放在内存中处理，排序时候不涉及数据的内外交换，称为内排序；反之为外排序
n个记录采用基于比较的排序方法:
最好的平均时间复杂度为O(nlog2m)。
最好情况是排序序列正序，此时的时间复杂度为O(n)。
内排序算法的稳定性：
如果待排序的表中，存在有多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的。
反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种
排序方法是不稳定的。
正序和反序
若待排序的表中元素已按关键字排好序，称此表中元素为正序;
反之，若待排序的表中元素的关键字顺序正好和排好序的顺序相反,
称此表中元素为反序。
内排序数据的组织
typedef int KeyType;// 关键字的类型
typedef struct{
KeyType key; //关键字项；
int data;
}RecType; //排序的记录类型定义
二.内排序
1.插入排序
a. 直接插入排序
算法思路: 每次从前向后找到顺序不对的元素，移动到合适位置
方法：从前往后，如果当前关键字比前一个小，一直向前比较，直到合适的位置。
时间复杂度：O(n2)
//直接插入排序
void InsertSort(RecType R[],int n){
int i,j;
RecType tmp;
for(i=1;i<n;i++){
if(R[i].key<R[i-1].key){
tmp=R[i];
j=i-1;//j是i前面一个，j的key大于i
do{
R[j+1]=R[j];
j--;
}while(j>=0&&R[j].key>tmp.key);//比tmp大的向后移位，直到R[j].key<tmp.key
R[j+1]=tmp; //在j+1处插入R[i]，因为j已经移动了所以要加一
}
}
}
b.折半插入排序
算法思路: 每次从前向后，找到顺序不对的元素，移动到合适位置
方法：从前往后，如果当前关键字比前一个小，对前面二分比较直到合适的位置插入。
时间复杂度：O(n2)
void BinInsertSort(RecType R[],int n){
int i ,j ,low ,high , mid;
RecType tmp;
for(i=1;i<n;i++){
if(R[i].key<R[i-1].key){
tmp=R[i];//tmp是需要插入排序的元素。
low =0;
high=i-1;
while(low<=high){
mid=(low+high)/2;
if(tmp.key<R[mid].key)
high=mid-1;
else
low =mid+1;
}//二分查找到
for(j=i-1;j>=high+1;j--)
R[j+1]=R[j]; //前面比tmp大的都向后移动。
R[high+1]=tmp; //跳出循环的时候，high已经移动过了，加一后才是要插入的位置
}
}
}//折半插入排序和直接插入排序的差别主要是改变了元素之间的比较次数。
c.希尔排序（缩小增量排序）
算法思路：先分组，再直接插入排序。
方法：
①d=n/2
②将排序序列分为d个组，在各组内进行直接插入排序
③递减d=d/2， 重复②，直到d=1
时间复杂度：O（n1.3）,是一个不稳定的排序方法
void ShellSort(RecType R[],int n){
int i,j,d;
d=n/2;
while(d>0){
for(i=d;i<n;i++){//间隔为D的元素直接插入排序
tmp=R[i];
j=i-d;
while(j>=0&&tmp.key<R[j].key){
R[j+d]=R[j];
j=j-d;
}
R[j+d]=tmp;
}
d=d/2; //改变增量
}
}
2.交换排序
a.冒泡排序（起泡排序）
算法思路： 依次比较两个相邻的元素,如果他们的顺序错误就把他们交换过来。
方法： 从前往后，每次把大的往后交换，这样一次过后，最大的就已经到位，再次从第一个开始，交换到倒数第二位，一次类推重复地进行，直到没有相邻元素需要交换,也就是说该元素列已经排序完成
最好的时间复杂度是O（n）,平均O（n2）
void BubbleSort(RecType R[],int n){//元素个数为n
int i,j;RecType temp;bool exchange;
for(i=0;i<n-1;i++){
exchange=false;//初始没有交换
for(j=n-1;j>i;j--)
if(R[j].key<R[j-1].key){
temp = R[j];
R[j]=R[j-1];
R[j-1]=temp;
exchange=true;
}
if(exchange==false) return;
//如果某一趟没有发生交换，那么已经排序完成了
}
}
b.双向冒泡排序
算法思路： 在基于冒泡排序的基础上，我们知道，无论是从前向后遍历交换，还是从后向前遍历交换，对程序的逻辑和性能的代价都是不影响的，那么我们就可以让一部分情况下从前向后遍历交换，另一部分情况从后向前遍历交换。
方法： 从前往后，每次把大的往后交换，从后往前把小的往前交换，这样一次过后，最大的和最小的就已经到位，再次从第二个开始，交换到倒数第二位，类推重复地进行，直到没有相邻元素需要交换,也就是说该元素列已经排序完成
最好的时间复杂度是O（n）,平均O（n2）
void BullerSort(RecType R[], int n)
{
RecType tmp;
bool exchang = false;
for (int i = 0; i < n;)
{ int j;
exchang = false;
for (j = n - 1 - i; j > i; j--) //从后往前，把小的移动到第一个
if (R[j].key < R[j - 1].key)
{
tmp = R[j];R[j] = R[j - 1];R[j-1] =tmp;
exchang = true;
}
i++;
for(j=i;j<n-i;j++){//从前往后把大的移动到最后。
if(R[j].key>R[j+1].key){
tmp = R[j];R[j]=R[j+1];R[j+1] = tmp;
exchang = true;
}
}
if(exchang==false) return;
}
}
c.快速排序
算法思路： 将待排序数据分割成独立的两个子序列，其中左边的子序列均比右边的子序列中的元素小，然后分别对左右两个子序列继续进行排序，达到整个序列有序的目的。
方法： 使用递归的方法，假设第一个是基准，从后往前找到比基准小的交换位置，从前往后，找到比基准大的交换位置。
平均时间复杂度O(nlog2n)，空间复杂度O(log2n)
void QuickSort(RecType R[],int s,int t){
int i=s,j=t;RecType tmp;
if(s<t){
tmp=R[s];
while(i!=j){ //两端交替扫描直到指向同一个
while(j>i&&R[j].key>=tmp.key)
j--;//从后往前找到比基准小的
R[i]=R[j];//交换位置
while(j>i&&R[i].key<=tmp.key)
i++;//从前往后找到比基准大的
R[j]=R[i];
}
R[i]=tmp;//基准放在中间
QuickSort(R,s,i-1);//对左子区间操作
QuickSort(R,i+1,t);//对右子区间操作
}
}
3.选择排序
a.简单选择排序方法
算法思路： 假设排序过程中，待排记录序列的状态为【全局有序序列】【无序序列】 且有序序列中所有记录的关键字均小于无序序列中记录 的关键字，则第i趟简单选择排序是，从无序序列R[i…n] 的n-i+1记录中选出关键字最小的记录加入有序序列。
方法： 每次从前往后假设当前无序列表第一个是当前最小的，在寻找当前这一趟最小的，如果不是无序列表里的第一个，无序列表的第一个就与最小的交换位置，看做是插入了有序表，下一趟从它后面开始找。
关键字比较次数是n(n-1)/2, 平均时间复杂度O(n2)，简单选择排序与初始序列的顺序无关
void SelectSort（RecType R[],int n){
int i,j,k;
RecType tmp;
for(i=0;i<n;i++){
k=i;//开始k=i，等最后看是否还等于i
for(j=i+1;j<n;j++)
if(R[j].key<R[k].key)
k=j;//改变k
if(k!=i)//如果i不是当前这一趟最小的，那么就交换
tmp=R[i],R[i]=R[k],R[k]=tmp;
}
}
b.堆排序
算法思路： 构造大根堆，每次把大根堆的根节点放入列表中。
方法： 大根堆对应的完全二叉树中，任意一个节点的关键字都大于或等于它的孩子节点的关键字。最小关键字的记录一定是某个叶子节点，每次筛选，把不是大根堆的边成大根堆，把大根堆的根放在列表里。
筛选时，仅仅处理从根节点开始到某个叶子节点的路径上的节点，
n个节点的完全二叉树高度为 log2(n+1) 取上界，所有筛选的时间复杂度为O（log2n)，对高度为h的堆一次筛选比较次数最多2（h-1），对n个关键字比较次数不超过4n
堆排序的时间复制度为O(nlogn),k空间复杂度为O(1) ，不稳定的排序
typedef int KeyType;// 关键字的类型
typedef struct{
KeyType key; //关键字项；
int data;
}RecType; //排序的记录类型定义
//筛选代码
void sift(RecType R[],int low ,int high ){
int i=low,j=2*i; //j是i的左孩子。
RecType tmp=R[i]; //现在i就是双亲。放在tmp里
while(j<=high){
if(j<high&R[j].key<R[j+1].key)
j++;//j 指向大的孩子 如果右边孩子大，++ 后 j就是右孩子如果
if(tmp.key<R[j].key){//双亲小
R[i]=R[j]; //j调整到双亲的位置
i=j;
j=2*i //修改i和j 继续向下。
}
else break; //如果双亲大，那么跳出循环。
}//如果中间没有跳出循环，那么到最后自动出来
R[i]=tmp;
}
//堆排序算法
void HeapSort(RecType R[],int n){
int i;RecType tmp;
for(i=n/2;i>=1;i--)//有n个节点，那么最后一个分支节点是 n/2
sift(R,i,n); //建立初始大根堆
for(i=n;i>=2;i--){ //n-1次循环，完成堆排序
tmp = R[1];
R[1]=R[i]; //R[i] 和 R[1] 换位置
R[i]=tmp;
sift(R,1;i-1); //筛选R[1]节点，得到i-1个节点的堆。这样以后R[1]一直是比较大的那个
}
}
4.归并排序
算法思想：将相邻两个或两个以上的有序子序列“归并”为一个新的有序序列。 在内部排序中，通常采用的是2-路归并排 序。即：将两个位置相邻的有序子序列合并
方法： 分别扫描相邻两段，对元素进行比较按大小顺序放入新的列表中，每次改分段的长度，直到排序完成。
每一趟归并的时间是O(n) 一共要 log2n 取上界趟，二路归并算法的时间复杂度是O(nlog2n)
空间复制度是O(n);
//一次二路归并排序
void Merge(RecType R[],int low,int mid,int high){
RecType *R1;
R1=(RecType *)malloc((high-low+1)*sizeof(RecType));//用来存放归并后的结果
int i=low,j=mid+1,k=0;//k是R1的下标，i 和 j 分别是 第一段和第二段的下标
while(i<=mid&&j<=high){
if(R[i].key<R[j].key)
R1[k]=R[i],i++,k++;
else
R1[k]=R[j],j++,k++;
}//当其中有一段扫描完后，跳出
while(i<=mid) R1[k]=R[i],i++,k++;//把没有扫描完的全放到R1中
while(j<=high) R1[k]=R[j],j++,k++;
for(k=0,i=low;i<=high;i++,k++)
R[i]=R1[k];//把R1再复制回R中
free(R1);
}
//一趟二路归并
void MergerPass(RecType R[],int lenth,int n){
int i;
for(i=0;i+lenth*2-1<n;i=i+lenth*2)
Merge(R,i,i+lenth-1,i+lenth*2-1);//归并length长度的两个相邻子表
if(i+lenth-1<n)
Merge(R,i,i+lenth-1,n-1);//剩下没有按lenth分的两个组
}
//二路归并排序算法
void MergeSort(RecType R[],int n){
int lenth;
for(lenth=1;lenth<n;lenth=lenth*2)
MergerPass(R,lenth,n);//一共需要log2n次
}
5.基数排序
基数r: 对于二进制数，r=2,对于10进制数，r=10 基数就时进制。
记录R[j]的关键字R[j].key： kjd-1, kjd-2, kjd-3,…, kj1, kj0, kj0就是最低位， kjd-1就是最高位，d 是数字的位数，
基数排序有两种，最低位优先（LSD）和最高位优先(MSD)，选择那种排序要根据数据的特点来定。例如：对整数序列递增排序，选择低位优先，越重要的位越后
最低位优先排序过程
对i=0,1…d-1，依次做一次分配和收集（使用r个队列 Q0,Q1,…Qr-1)，r是基数。
- 分配：开始时，把 Q0,Q1,…Qr-1 都弄成空队列，然后一次考察线性表中的每一个节点aj (j=0,1,…,n-1),如果aj 的关键字kji = k,就把aj 放在Qk里
- 收集：按Q0,Q1,Qr-1 的顺序把各个队列的节点首尾相连，得到新的节点序列，从而组成新的线性表。
#define MAXE 20 //线性表中最多元素个数
#define MAXR 10 //基数的最大取值
#define MAXD 8 //关键字位数的最大取值
typedef struct node{
char data[MAXD]; //记录关键字定义的字符串
struct nodr *rext;
}RecType1; //单链表中每个节点的类型
//开始排序
void RedixSort(RecType1*&P,int r,int d){
//p为待排序序列链表指针，r为基数，d为关键字位数
RecType *head[MAXR],*tail[MAXR],*t;//定义各链对的首位指针。
int i,j,k;
for(i=d-1;i>=0;i--){ //从低位到高位
for(j=0;j<r;j++)
head[j]=tail[j]=NULL; //初始化队列
while(p!=NULL){
k=p->data[i]-'0';
if(head[k]==NULL)
{head[k]=p;tail[k]=p;}
else
{tail[k]->next=p;ta}
p=p->next;
}
//收集
p=UNLL;
for(j=0;j<r;j++)
if(head[j]!=NULL){
if(p=NULL){
p=head[j];
t=tail[j];
}
else{
t->next=head[j];
t=tail[j];
}
}
t->next=NULL;
}
}
基数排序的过程通过收集和分配的过程来进行的，不需要比较
各种排序的比较总结
| 排序方法 | 平均时间复杂度 | 最坏时间 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
| 折半排序 | O(n2) | O(n2) | O(nlog2n) | O(1) | 稳定 |
| 希尔排序 | O(n1.3) | O(1) | 不稳定 | ||
| 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(log2n) | 不稳定 |
| 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
| 二路归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
| 基础排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O® | 稳定 |
按算法平均时间复杂度分类：
O(nlogn)的有：快速排序、堆排序和归并排序，其中以快速排序为最好；
O(n2 )的有：直接插入、 起泡排序、简单选择排序；直接插入最好，特别是关键字近似有序的序列；
O(n)的只有: 基数排序。
按空间复杂度
O(1):所有的简单排序方法(直接插入、起泡 和简单选择) 和 堆排序
O(logn):快速排序，为栈所需的辅助空间;
O(n):归并排序所需辅助空间最多
O(rd):链式基数排序需附设队列首尾指针
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
当待排记录序列按关键字顺序有序时， 直接插入排序和起泡排序能达到O(n)的 时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为 O(n2 )，因此是应该尽量避免的情况。
当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法、
希尔排序，简单选择排序，快速排序，堆排序是不稳定的排序方法。 其他各种排序方法的综合比较稳
这次有道了要赞的环节了，如果觉得可以学到些什么，点个赞再走吧，欢迎各位路过的大佬批评指正，欢迎大家留言，评论，私信。
最后
以上就是包容星月为你收集整理的数据结构——排序总结 （插入排序，交换排序，选择排序，归并排序，基数排序）一.概念二.内排序各种排序的比较总结的全部内容，希望文章能够帮你解决数据结构——排序总结 （插入排序，交换排序，选择排序，归并排序，基数排序）一.概念二.内排序各种排序的比较总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复