开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 考研数据结构排序算法详细总结 -> 正文阅读

[数据结构与算法]考研数据结构排序算法详细总结

我自己认为比较难得排序算法都完成了代码，包含插入排序、快速排序、堆排序、归并排序

希尔排序、冒泡排序、简单选择排序的原理都很简单，代码暂时留着到有时间的时候补回来。

基数排序中涉及链表比较麻烦，补代码的可能性不大（笑哭）

对于外部排序应该是没有办法写代码吧，主要应该就是理解败者树和置换—选择排序，个人感觉

内部排序
- 稳定排序算法
  - 插入排序：时间复杂度：O(N*N)
  - 冒泡排序：时间复杂度：O(N*N)
  - 归并排序：时间复杂度：O(N*log2(N))
  - 基数排序：时间复杂度：O(d(n+r))
- 不稳定排序算法
  - 希尔排序：时间复杂度：O(n的1.3次方)->O(N*N)
  - 快速排序：时间复杂度：O(N*log2(N))
  - 简单选择排序：时间复杂度：O(N*N)
  - 堆排序：时间复杂度：O(N*log2(N))
外部排序
- 优化方法：
  - 多路归并——败者树
  - 减少初始归并段数量——置换—选择排序

1、插入排序

1.1 算法思想

没次将一个待排序的记录按其关键字大小插入到前面已经排好了的子序列中，直到全部记录插入完成

1.2 算法性能

空间复杂度：O（1）
时间复杂度：O(n*n）
稳定排序

1.3 算法代码

?#include<stdio.h>
?#include<stdlib.h>
?#include<time.h>
??
?void PrintSort(int a[],int n){  //打印当前的数组序列 
?    for(int i=0;i<n;i++)
?        printf("%d ",a[i]);
?    printf("\n");
?}
??
?void InsertSort(int a[],int n){ //插入排序 
?    int j; 
?    for(int i=1;i<n;++i) //从第二个元素开始往下寻找左边有比自己小的元素 
?    {
?        int temp = a[i];    //保存当前的元素值，以防移动中被覆盖掉 
?        for(j=i-1;j>=0 && a[j]>temp;j--)    
?            a[j+1]=a[j];    //将左边的元素右移 
?        a[j+1]=temp;        //移动元素归位 
?        if(i<n-1) printf("第%d个元素排序后的结果：",i);
?        else if(i==n-1) printf("最终的排序结果为："); ?
?        PrintSort(a,n);
?    }
?}
?int main(){
?    
?    srand((unsigned)(time(NULL)));  //调用srand函数，让rand函数没次使用不同的随机数种子，保证每次产生的随机数不相同。 
?    int a[100];
?    int n;
?    
?    printf("请输入需要产生随机数的个数:"); 
?    scanf("%d",&n); //n<100 
?    
?    for(int i=0;i<n;i++) //产生n个随机数在数组a内 
?        a[i]=rand()%100;    //保证数组元素大小在0到99以内 
?    printf("产生的随机数组为："); 
?    PrintSort(a,n);     //打印初始数组元素 
?        
?    InsertSort(a,n); //插入排序 
?    
?    return 0; 
?}

2 希尔排序

2.1 算法思想

先将待排序表分割成若干形如L[i,i+d,i+2d ...... i+kd]的“特殊“子表，对各个子表分别进行直接插入排序缩小增量d，重复上述过程，直到d=1为止

2.2 算法性能

空间复杂度：O(1)
时间复杂度：O(n的1.3次方)
不稳定排序

2.3 算法代码

3 冒泡排序

3.1 算法思想

从后往前（或者从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]）则交换他们，直到序列比较完

3.2 算法性能

时间复杂度：O(n*n)
空间复杂度：O(1)
稳定排序

3.3 算法代码

4 快速排序

4.1 算法思想

快速排序算法思想：算法思想:在待排序表L1..n]中任取一个元素pivot作为枢轴(或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分L[1..k-1]和L[k+1...n]，使得L1...k-1]中的所有元素小于pivot，Llk+1..n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

4.2 算法性能

时间复杂度：最好O（nlogn）最坏O(n*n)
空间复杂度：最好O（nlogn）最坏O(n*n)
当待排序序列正序或逆序，空间和时间复杂度最高
不稳定排序

4.3 算法代码

?#include<stdio.h>
?#include<stdlib.h>
?#include<time.h>
??
?int NQuickSort; ?//快速排序的数组元素数量 
??
?void PrintSort(int a[],int n){  //打印当前的数组序列 
?    for(int i=0;i<n;i++)
?        printf("%d ",a[i]);
?    printf("\n");
?}
??
?void QuickSort(int a[],int l,int r) {
?    
?    if(r<=l) return;    //如果当前数组不需要进行排序 
?    else printf("%d %d\n",l,r);
?    int left=l,right=r;
?    int first=a[left];
?    while(left < right){
?        while(left < right && a[right] >= first) right--;
?        a[left]=a[right];
?        while(left < right && a[left] <= first) left++;
?        a[right]=a[left];
?    }
?    a[left]=first;
?    
?    PrintSort(a,NQuickSort);
?    
?    int mid = left;
?    PrintSort(a,NQuickSort);
?    QuickSort(a,l,mid-1);
?    QuickSort(a,mid+1,r);
?}
?int main(){
?    
?    srand((unsigned)(time(NULL)));  //调用srand函数，让rand函数没次使用不同的随机数种子，保证每次产生的随机数不相同。 
?    int a[100];
?    int n;
?    
?    printf("请输入需要产生随机数的个数:"); 
?    scanf("%d",&NQuickSort); //n<100 
?    
?    for(int i=0;i<NQuickSort;i++) //产生n个随机数在数组a内 
?        a[i]=rand()%100;    //保证数组元素大小在0到99以内 
?    printf("产生的随机数组为："); 
?    PrintSort(a,NQuickSort);        //打印初始数组元素 
?        
?    QuickSort(a,0,NQuickSort-1);
?    
?    return 0; 
?}

5 简单选择排序

5.1 算法思想

每一趟再待排序元素中选取关键字最小的元素加入有序子列

5.2 算法性能

空间复杂度：O（1）
时间复杂度：O（n*n）
不稳定排序

5.3 算法代码

5 简单选择排序

6 堆排序

6.1 算法思想

若满足任意根节点元素值大于左右节点——大根堆
若满足任意根节点元素值小于左右节点——小根堆

6.2 算法性能

空间复杂度：O（1）
时间复杂度：O（n*n）
不稳定排序

6.3 算法代码

大根堆创建代码

?#include<stdio.h>
?#include<stdlib.h>
?#include<time.h>
?int a[100];
??
?void PrintSort(int n){  //打印当前的数组序列 
?    for(int i=1;i<=n;i++)
?        printf("%d ",a[i]);
?    printf("\n");
?}
?void swap(int i,int n){
?    if(i*2>n) return;
?    //printf("%d**\n",i);
?    int j;
?    if(a[i]<a[2*i] && a[i]<a[2*i+1] && 2*i+1<=n){   //如果左右孩子都大于根节点 
?        if(a[2*i]>a[2*i+1]) j=2*i;  //为根节点找到左右孩子中较大下标 
?        else j=2*i+1;
?        a[0]=a[i];a[i]=a[j];a[j]=a[0];
?        swap (j,n); //递归修复刚刚交换过的节点，防止交换改变结构 
?    }
?    else if(a[i]<a[2*i]){   //如果左孩子大于根节点 
?        a[0]=a[i];a[i]=a[2*i];a[2*i]=a[0];
?        swap(2*i,n);
?    }
?    else if(a[i]<a[2*i+1] && 2*i+1<=n){ //如果右孩子大于根节点 
?        a[0]=a[i];a[i]=a[2*i+1];a[2*i+1]=a[0];
?        swap(2*i+1,n);
?    }
?    //PrintSort(n); //打印没次变动后的序列 
?    
?}
?void SetMaxHeap(int n){
?    for(int i=n/2;i>0;i--){
?        swap(i,n);
?    }
?} 
?void HeapSort(int n){
?    for(int i=1;i<n;i++){
?        int temp=a[1];a[1]=a[n-i+1];a[n-i+1]=temp;//将堆顶元素与堆尾元素交换 
?        printf("找到%d个顶：",i); 
?        PrintSort(n);
?        swap(1,n-i);    //重新构建大顶堆 
?    }
?} 
??
?int main(){
?    
?    srand((unsigned)(time(NULL)));  //调用srand函数，让rand函数没次使用不同的随机数种子，保证每次产生的随机数不相同。 
?    int n;
?    printf("请输入需要产生随机数的个数:"); 
?    scanf("%d",&n); //n<100 
?    
?    for(int i=1;i<=n;i++) //产生n个随机数在数组a内 
?        a[i]=rand()%100;    //保证数组元素大小在0到99以内
?        
?//  for(int i=1;i<=n;i++)   //测试错误样例 
?//      scanf("%d",&a[i]);
?//       
?    printf("产生的随机数组为："); 
?    PrintSort(n);       //打印初始数组元素 
?        
?    SetMaxHeap(n);  //创建大根堆 
?    printf("创建大根堆后数组顺序为："); PrintSort(n);
?    
?    HeapSort(n);    //对创建的大根堆进行排序 
?    printf("排序完成后的数组序列为："); PrintSort(n);
?    
?    return 0; 
?}

7 归并排序

7.1 算法思想

把两个或多个已经有的序列合并为一个序列

7.2 算法性能

时间复杂度：O（n*logn）
空间复杂度：O（n）
稳定排序

7.3 算法代码

?#include<stdio.h>
?#include<stdlib.h>
?#include<time.h>
??
?int a[100];
?int m;
?void PrintSort(int n){  //打印当前的数组序列 
?    for(int i=0;i<n;i++)
?        printf("%d ",a[i]);
?    printf("\n");
?}
??
?void MergerPrint(int left,int right,int n){
?    for(int i=0;i<n;i++){
?        if(left==i || right==i) printf(" ** ");
?        printf("%d ",a[i]);
?    }
?        
?    printf("\n");
?}
??
?void Merge(int left,int mid,int right){
?    int b[100];
?    int i,j,k;
?    
?    for(i=left;i<=right;i++)    //将数组a的待排序部分复制到临时数组B中 
?        b[i]=a[i];
?    
?    for(i=left,j=mid+1,k=i;i<=mid&&j<=right;k++){   //进行归并 
?        if(b[i]<=b[j]) a[k]=b[i++];
?        else ?a[k]=b[j++];
?    }
?    while(i<=mid) a[k++]=b[i++];
?    while(j<=right) a[k++]=b[j++];
?}
??
?void MergeSort(int left,int right){
?    if(right<=left) return;
?    int mid=(left+right)/2;
?    MergeSort(left,mid);    //对左半部分进行归并 ——递归 
?    MergeSort(mid+1,right); //对右半部分进行归并 ——递归 
?    Merge(left,mid,right);  //对当前部分进行归并 
?    
?//  MergerPrint(left,right,m); //查看归并排序过 
?} 
??
?int main(){
?    
?    srand((unsigned)(time(NULL)));  //调用srand函数，让rand函数没次使用不同的随机数种子，保证每次产生的随机数不相同。 
?    
?    int n;
?    
?    printf("请输入需要产生随机数的个数:"); 
?    scanf("%d",&n); //n<100 
?    m=n;
?    for(int i=0;i<n;i++) //产生n个随机数在数组a内 
?        a[i]=rand()%100;    //保证数组元素大小在0到99以内 
?    printf("产生的随机数组为："); 
?    PrintSort(n);       //打印初始数组元素 
?        
?    MergeSort(0,n-1);
?    printf("最终排序结果为："); 
?    PrintSort(n);
?    return 0; 
?}