【数据结构和算法】各种基本的排序算法原理

2022-11-10 263

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构和算法】各种基本的排序算法原理

排序的概述

排序方法的分类

按存储介质分类：（内部排序和外部排序）

按比较器个数分类：（串行排序和并行排序）

按主要操作分类

按辅助空间分类

按稳定性分类

稳定排序的例子（相同的数值排序后相对位置没有发生改变）

非稳定排序的例子（相同的数值排序后相对位置发生了改变）

记录序列顺序表的存储结构

#define MAXSIZE 20  //设记录不超过20个
typedef int KeyType;  //设关键字为整形量（int 型）
Typedef struct{   //定义每个记录(数据元素)的结构
  KeyType key;  //关键字
  InfoType otherinfo; //其他数据项
}RedType;
Typedef struct{   //定义顺序表的结构
  RedType r[MAXSIZE + 1]; //存储顺序表的向量，其中r[0]一般作为哨兵，可以减少比较的次数
  int length;   //顺序表的长度
}SqList;

直接插入排序

实现思路

（缺点是每一次循环都要进行两次的比较，可以设置一个哨兵减少比较的次数，在0号的位置插入一个哨兵）

增加一个哨兵的实现思路

代码实现

//增加哨兵代码
void InsertSort(SqList &L){
  int i,j;
  for(i = 2; i <= L.length; i++){
  if(L.r[i].key < L.r[i - 1].key){
    L.r[0] = L.r[i];
    for(j = i-1; L.r[0].key < L.r[j].key; j--){
    L.r[j+1] = L.r[j];
    }
    L.r[j+1] = L.r[0];
  }
  }
}
//无哨兵代码（增加了时间复杂度）
void InsertSort(SqList &L){
  int i,j,temp;
  for(j = 1; j < L.length; j++){  //从第二个元素开始不断的整理这个数组
  temp = L.r[j];
  for(i = j -1; i >=0 && L.r[i] < temp; i--){ //如果要插入的值比此时的数据大，不断后移
    L.r[i + 1] = L.r[i];
  }
  L.r[i + 1] = temp;  //直到某一个数据比插入的值小，就插入在该数据后面
  }
}

直接插入排序的性能分析

折半插入排序

思路分析

（由于在插入的元素前面的元素已经是拍好戏的元素，所以对这些元素可以进行二分查找，一次查找排除了一半的元素所以查找得更快）

代码实现

void BInsertSort(SqList &L){
  int i,j,low,high;
  for(i = 2; i <= L.length; ++i){ //依次插入第1~第n个元素
  L.r[0] = L.r[i];    //当前插入元素存到“哨兵”位置
  low = 1;
  high = i - 1;
  while(low <= high){   //二分法查找插入位置
    mid = (low + high)/2;
    if(L.r[0].key < L.r[mid].key) //如果比中间小。则查找前一半
    high = mid - 1;
    else      //如果比中间大。则查找后一半
    low = mid + 1;
  } 
  //循环结束，此时high+1则为插入的位置，因为此时low = mid。
  //而high必须为low-1才能结束循环，也可以说mid位置就是插入元素的为位置
  for(j = i - 1; j >= high + 1; j--){ //移动元素
    L.r[j+1] = L.r[j];
  }
  L.r[high + 1] = L.r[0];  //插入到正取的位置
  //  L.r[mid] = L.r[0];
  }
}

折半插入排序的性能分析（平均性能优于直接插入排序）

希尔排序

基本思路

首先选择一个增量序列，这个增量序列一次比一次小，按照这个增量实现间隔的插入排序，比如设定一开始的增量为5，则对序列进行5增量的间隔插入排序。增量序列是递减的，且最后的一步，必须增量为1，也就是进行一次直接的插入排序。（最后的一次序列已经基本有序了，所以只需要很少的移动就可实现）

希尔排序实现的例子

希尔排序的特点

大致的代码实现

void Shellsort(SqList &L,int dk){
  //对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子
  for(i = dk + 1; i <= L.elngth; i++){
  if(r[i].key < r[i-dk].key){
    r[0] = r[i];
    for(j = i - dk; j>0 && (r[0].key < r[j].key); j = j - dk){
    r[j + dk] = r[j];
    }
    r[j + dk] = r[0];
  }
  }
}
void SellSort(SqList &L,int dlat[],int t){
  //dk的值依次存储在dlat[t]中，按增量序列dlta[0..t-1]对顺序表L作希尔排序
  for(k = 0; k < t; k++)
  Selllnsert(L,dlta[k]);  //一趟增量为dlta[k]的插入排序
}
//与插入排序进行比较，就是将+1，-1的值换成增量dk
void InsertSort(SqList &L){
  int i,j;
  for(i = 2; i <= L.length; i++){
  if(L.r[i].key < L.r[i - 1].key){
    L.r[0] = L.r[i];
    for(j = i-1; L.r[0].key < L.r[j].key; j--){
    L.r[j+1] = L.r[j];
    }
    L.r[j+1] = L.r[0];
  }
  }
}

希尔排序的时间复杂度

（与增量序列的取值有关）

希尔排序是不稳定，例子如下：

希尔排序算法分析

冒泡排序

（数值大的不断的靠后，数值小的不断地冒前，每一趟增加一个有序的元素，而此时序列靠后的元素就是有序的）

冒泡排序的示例

（规律：每次需要比较的次数 = n个记录 - 第几趟的数值）

冒泡排序的代码实现

//冒泡排序
void bubble_sort(SqList &L){    
  int i,j;
  for(i = 0; i < L.length-1; i++){  //比较 L.length-1轮
  for( j = 0; j < length - i - 1; i++){ //每轮比较 length - i - 1次
    if(L.r[j] < L.r[j+1]){    //两个数值交换
    L.r[j] = L.r[j+1] + L.r[j];
    L.r[j+1] = L.r[j] - L.r[j+1];
    L.r[j] = L.r[j] - L.r[j+1];
    }
  }
  }
}
//冒泡排序的改进
//如果后面的比较之中一直都没有进行数据的交换，则表示后面的数据已经是有序，已经冒泡排序已经无需进行
//也就是如果某一趟比较时不出现交换，说明已排好序
//实现，增加一个标志flag，如果一直没有进行交换flag==0，退出循环
void bubble_sort(SqList &L){
  int i,j,flag = 1;
  for(i = 0; i < L.length-1 && flag==1 ; i++){//比较 L.length-1轮
  flag = 0;   //每次循环重新置标志
  for( j = 0; j < length - i - 1; i++){ //每轮比较 length - i - 1次
    if(L.r[j] < L.r[j+1]){    //两个数值交换
    L.r[j] = L.r[j+1] + L.r[j];
    L.r[j+1] = L.r[j] - L.r[j+1];
    L.r[j] = L.r[j] - L.r[j+1];
    flag = 1； //发生交换，flag置为1，若本趟没有发生交换，flag保持0，退出循环
    }
  }
  }
}

冒泡排序的算法分析

快速排序

快速排序的基本思想（递归实现）

快速排序的例子

（只需要一个多余的位置）

将1号元素49搬到0号元素中存储，此时1号位置就多出来了一个空间。

从后面找出一个比此时的0号元素49小的元素，high不断的向前推进。49和49相等，不符合，27比49小，符合条件，所以将27搬到1号元素中。

此时后面空出来了一个元素，所以此时从前面的low指针向后移直到找到了一个比0号元素49大的元素，直到65，所以将65搬到后面，此时65所在的位置为空。

所以此时前面又空了，所以又轮到了high指针向前找一个比49小的数据搬到前面去，找到了13，将13班到前面空白的位置，而原本131的位置为空。

此时再从前面找一个大的搬过去，直到low指针和high指针相遇。

然后将0号元素搬回到此时指针相遇的地方。

同样的，对此时左右字表的元素又进行同样的方法，直到每个字表剩下一个元素。

ps：

1、字表的形成是采用从两头向中间交替式逼近法

2、趟中对个子表的操作都相识，可采用递归算法

快速排序代码实现

void QSort(SqList &L,int low,int high){ //对顺序表L快速排序
  if(low < high){      //长度大于1
  pivotloc = Partition(L,low,high); //将顺序表一分为2，oivotloc为枢轴元素拍好序的位置
  QSort(L,low,pivotloc - 1);  //对低子表递归排序
  QSort(L,oivoloc + 1,high);  //对高子表递归排序
  }
}
int Partition(SqList &L,int low,int high){
  L.r[0] = L.r[low];  
  pivotkey = L.r[low].key;//每次设置从表中左边第一个元素开始
  while(low < high){
  while(low < high && L.r[high].key >= pivotkey)  
    --high;   //右边不断向后移直到找到了一个比0号数据小的元素
  L.r[low] = L.r[high];
  while(low < high && L.r[low],key <= pivotkey) 
    ++low;    //左边不断向前移直到找到了一个比0号数据大的元素
  L.r[high] = L.r[low];
  }
  L.r[low] = L.r[0];  //填补两个指针共同所指向的位置
  return low;    //此时low和high是指向相同的位置
}

快速排序的时间复杂符

快速排序的空间复杂度

快速排序的稳定性

ps：如果对一个逆序的数组进行快速排序使其为正序的数组，快速排序每一次只能排好一个子表，此时快速排序退化成冒泡排序。所以快速排序不适用于原本或基本有序的记录序列进行排序。

选择排序

选择排序的思路

（选择排序总共需要n-1趟就可以了）

选择排序的例子

（每一趟找到一个最小值，只是这个最小值的范围不一样，第一趟从第一个位置开始，第n趟从第n个位置开始）

选择排序的代码实现

void SelectSort(SqList &K){
  for(i = 1; i < L.length; ++i){
  for(j = i + 1; j <= L.length; j--){
    if(L.r[j].key < L.r[i].key) //交换两个值
    L.r[i].key = L.r[i].key + L.r[j].key;
    L.r[j].key = L.r[i].key - L.r[j].key;
    L.r[i].key = L.r[i].key - L.r[j].key;
  }
  }
}

选择排序的稳定性

简单的选择排序是不稳定的排序，例子如下：

堆排序

堆的定义（小根堆与大根堆）

小根堆与大跟堆的例子

堆排序的思路

实现堆排序需要解决掉两个问题：

如何有一个无序序列建成一个堆
如何在输出堆顶元素后，调整剩余元素为一个新的堆

堆的调整（以小根堆为例）

堆排序的算法实现

void HeapAdjust(elem R[],int s,int m){
  /*已知R[s..m]中记录的关键字除了R[s]之外均满足堆的定义
  *本函数调整R[s]的关键字，使R[s..m]成为一个大根堆
  */
  rc = R[s];
  for(j = 2*s; j <= m; j *= 2){ //沿key较大的孩子结点向下筛选
  if(j < m && R[j] < R[j+1])
    ++j;  //j为key较大的记录的下标
  if(rc >= R[j])
    break;
  R[s] = R[j];
  s = j;
  }
  R[s] = rc;
}
void HeapSort(elem R[]){  //对R[1]到R[n]进行排序
  int i;
  for(i = n/2; i >= 1; i--)
  HeapAdjust(R,i,n);  //建初始堆
  for(i = n; i > 1; i--){ //进行n-1趟排序
  Swap(R[1],R[i]);  //根与最后一个元素交换
  HeapAdjust(R,1,i-1);//对R[1]到R[i-1]重新建堆
  }
}