排序算法之我观

笔者今年是xmu大一新生 9月初学编程 学到泡排的时候就对排序这一块深入了解 (也只是很粗浅地学习了一下) 写这篇文章的初衷就是复习一下之前所学,有不足之处请不吝赐教 所谓排序 就是将杂乱无章的数据变得有规律 这其中有五花八门的算法,时间复杂度相同的算法不一而足 目前笔者只给读者展示几种基础算法 (冒泡排序,选择排序,插入排序,快速排序,基数排序,希尔排序,归并排序) (之所以没有介绍堆排序的原因是笔者也不是很懂这方面,大一上还没学数据结构) 有低效但好用,高效但不好写之类的 1.冒泡排序(Bubble Sort) 相信大家对这个应该也不陌生吧 应该要熟到半分钟就能把模板打出来 具体运作过程如下: 比较相邻的元素,如果前一个比后一个大,就把它们两个调换位置。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。 这步做完后,最后的元素会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 分析: 平均时间复杂度:两重循环:o(n^2) 稳定的算法 上代码(笔者目前只学一门c,IDE是cb) 图源:https://blog.csdn.net/qq_39741605/article/details/80821595

#include <stdio.h>
void swap(int *a, int *b); //交换两个数
int main()
{
    int n;
    printf("请输入要排序的数个数:");
    scanf("%d",&n);
 int   num[100000];
 int     i, j;
for(i=0;i<n;i++)
{
    scanf("%d",&num[i]);
}
for(i=0;i<n-1;i++)
{
    for(j=0;j<n-i-1;j++)        //i<n-1与j<n-i-1的由来可以由上图得到,这里不再叙述
    {
        if(num[j]>num[j+1])
        {
           swap(&num[j],&num[j+1]);
        }
    }
}
for(i=0;i<n;i++)
{
    printf("%d ",num[i]);
}
 return  0;
}
void swap(int *a, int *b)
{
 int    c;
  c = *a;
 *a = *b;
 *b =  c;
}

码风丑陋勿怪 泡排其实和选择排序有点像 都是在一轮排序后将最大或最小的元素“沉”到尾部或前排 //笔者注:若下标为1开头,怎么修改? 其实也简单: 改为:

for(i=1;i<n;i++)
{
    for(j=1;j<=n-i;j++)
    {
        if(num[j]>num[j+1])
        {
           swap(&num[j],&num[j+1]);
        }
    }
}

2.桶排序(Bucket sort) 说起来,这种排序方法时间复杂度不高(很低o(n)左右) 快到上天 一个桶代表一个数字,数组内数字应分配到与桶编码相等的桶中去。 如果一个数组中最大数不是很大的话,可以直接取数据范围的最大值 如果不是的话 (要先求出数组的最大值,因为数组的最大值是决定桶数量的重要依据)。 每个桶都有一个编号,编号从0开始。然后每个桶内装的是数组内等于该编号的元素的个数,初始值为0。接下来对数组内的数字进行检测,检测到该数字,对应编码的桶就+1。当检测完毕时,各个桶就完成了对数组内数字的统计。接下来,我们可以按照桶的编号从0开始一次输出桶的编号,根据桶内数字决定这个桶输出编号的次数。如此,输出的数据必是从小到大。 废话不说,上代码(我给的桶排不是空间复杂度优化过的)

#include <stdio.h>
#include <stdlib.h>
#include<memory.h>
int a[100];
int main()
{
    memset(a,0,sizeof(a));
    int n;
    printf("请输入要排序的数个数:");
    scanf("%d",&n);
    int i,b,j;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&b);
        a[b]++;
    }
    for(i=1;i<=100;i++)
    {
        for(j=0;j<a[i];j++)
        {
            printf("%d ",i);
        }
    }
    return 0;
}

代码很短,但是占用内存其实不小 适用范围很窄,但是在特定问题上可以把时间复杂度做到O(n)。 3.选择排序(Selection sort) 是一种简单直观的排序算法。 初始时在序列中找到最小(大)元素,放到序列的起始位置作为已排序序列;然后,再从剩余未排序元素中继续寻找最小(大)元素,放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

#include <stdio.h>
#include <stdlib.h>
int n,a[100]={0};
void selective_sort(int a[],int n)
{
    int i,j,k;
    for(i=1;i<n;i++)
    {
        k=i;
        for(j=i+1;j<=n;j++)
        {
            if(a[j]<a[k])
            {
                k=j;
            }
            if(k!=i)
            {
                int temp;
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    for(i=1;i<=n;i++)
{
   printf("%d ",a[i]);
}
}
int main()
{
    printf("请输入要排序的数个数:");
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
}
selective_sort(a,n);
    return 0;
}

分析: 时间复杂度:o(n^2);空间复杂度:o(1); 不稳定算法 4.希尔排序(Shell Sort) 是一种对插入排序的优化 平均时间复杂度:o(n^1.3);空间复杂度:o(1); 不稳定 主要思想:有点类似分治 将序列分割成许多元素个数相同的子序列,进行插入排序 最后对整个序列进行插入排序 由于在进行最后的排序之前,子序列已然保持很高的有序性,所以效率通常会比泡排,选择排序快上一些。 下面以十个元素为例:初始步长一般选择为数组长度一半 ,10/2=5 第一趟 分为5组将每一组中的元素按非递减次序排列 第二趟 分为5/2=2组,依次执行 最后一趟 整个数组进行插排

具体代码:

#include <stdio.h>
#include <stdlib.h>
int a[100];
void shell_sort(int array[], int length)
{
 int i,j,temp,gap; //gap是分组的步长
 for(gap=length/2; gap>=1; gap=gap/2)
        {
  for(i=gap+1;i<=length;i++)
  {       temp=array[i];
    for(j=i-gap;j>=1&&array[j]>temp;j-=gap)
            {array[j+gap]=array[j];}
           array[j+gap]=temp;
           int k;
                     for(k=1;k<=length;k++)
   {
      printf("%d ",array[k]);
   }
   printf("\n");
        }
           for(i=1;i<=length;i++)
   {
      printf("%d ",array[i]);
   }
   printf("\n");
        }
}
int main()
{
   int n;
   printf("请输入要排序的数个数:");
   scanf("%d",&n);
   int  i;
   for(i=1;i<=n;i++)
   {
       scanf("%d",&a[i]);
   }
   shell_sort(a,n);
    return 0;
}

5.插入排序(Insert Sort) 时间空间复杂度平均为o(n^2) 稳定 直接插入排序即是在要排序的数组中,假设前n-1(n>=2)个数已经是排好序的,现在要把第n个数插入到前n个已经排好序的数组中,使得这n个数也变成有序的,如此反复循环,使得要排序的数组中的最后一个元素也排好序, 我们可以先假设第一个数是排好序的,然后第二个数和第一个数进行比较,如果第二个数比第一个数大,那么说明前两个数排好序,无需做调整,如果第二个数比第一个数小,那么就把第一个数向后移,将第二个数放在第一个数的位置上,抽象出来就是用a[i]和a[i-1]进行比较,如果a[i]>a[i-1],那么就说明前i个数是已经排好序的, 如果a[i]<a[i-1],就让j=i-1,temp=a[i],然后一边将数据a[j]向后移动,一边向前搜索,直到找到a[j]<a[i]时停止,并将temp放到a[j+1]处即可。

void InsertSort(int arr[], int left, int right)
{
    int i, v;
    for (i = left; i <= right; i++) {
        v = arr[i];
        int l = left, r = i;
        int j;
        while (l < r) 
        {//在l与r之间插入排序,可以理解为解决子问题1→2→...→n
            int mid = (l + r) / 2;
            if (arr[mid] <= v)
                l = mid + 1;
            else
                r = mid;
        }
        for (j = i - 1; l <= j; j--)
            arr[j + 1] = arr[j];
        arr[l] = v;
    }
}
int main()
{  int n,i; 
 printf("请输入要排序的数个数:");  
 scanf("%d",&n);  
 for(i=1;i<=n;i++) 
  {      
  scanf("%d",&a[i]);
  } 
     InsertSort(a,1,n);  
     for(i=1;i<=n;i++)  
     {    
       printf("%d ",a[i]); 
     }   
         return 0;
  }
```

6.归并排序(Merge Sort) 用一张图来阐述原理 图源:https://blog.csdn.net/yushiyi6453/article/details/76407640

归并排序是分治思想的一个很好应用 将已有序的子序列合并,得到完全有序的序列; 即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为归并。

#include <stdio.h>
#include <stdlib.h>
int n,a[10000];
void merge(int a[],int left,int mid,int right)
{
    int i=left,j=mid+1,k=0,c[10000]={0};    
    while(i<=mid&&j<=right) 
    {     
       if(a[i]<=a[j])     
      c[k++]=a[i++];      
      else    
        c[k++]=a[j++]; 
    }    
    while(i<=mid) 
       {     
           c[k++]=a[i++];
      }
          while(j<=right)  
       {    
              c[k++]=a[j++];   
        } 
                  int f=left; 
              for(i=0;i<k;i++)
          {        
                  a[f+i]=c[i]; 
           } 
           }
       void MergeSort(int arr[], int left, int right)
       {
       if(left<right)
       {   
        int mid=(left+right)/2; 
           MergeSort(arr,left,mid);  
             MergeSort(arr,mid+1,right);    
             merge(arr,left,mid,right);
             }
             else
              return ;
       }

            int main()
            {
            printf("请输入要排序的数个数:");
            scanf("%d",&n);
            int i;for(i=1;i<=n;i++)
            {    scanf("%d",&a[i]);
            }
            MergeSort(a,1,n);
            for(i=1;i<=n;i++)
            {    
            printf("%d ",a[i]);
            }    
            return 0;
            }

7.快速排序(Quick Sort)(二十世纪十大算法、与傅里叶变换齐名) 这是笔者讲述的重点 此法由Tony Hoare在1959年发明(1961年公布),类似于归并,也有分治的一种思想,即找到一个基准数,将比它大的放在它的右边,比它小的放在它的左边. 问题来了 基准数要怎么取? 不清楚的话先选开头的数 之后有优化 先上传统快排

void swap(int a, int b)
{
    int temp = a;
    a = b;
    b = temp;
}

void quickSort(int a[], int left, int right)
{
    if (left >= right)
        return;
    int i = left, j = right;
    while (i < j)
    {
        while (j > i && a[j] >= a[left])
            j--;
        while (i < j && a[i] <= a[left])
            i++;
        swap(a[i], (i == j) ? a[left] : a[j]);  //i和j相遇则与pivot(基准元素)交换,否则a[i]与a[j]交换
    }
    quickSort(a, left, i-1);
    quickSort(a, j+1, right);
}

但是我们会发现这样的快速排序遇到某些情况序列原本就有序、有大量重复元素等等)会进行很多完全不必要的操作,耗费大量时间。 例如,处理一个本来按非递增次序排列的数组,排序效率就退化为与冒泡排序一样o(n^2)

这样的循环要进行N轮 优化可以从这几方面入手: 1.分割地愈细,快排的优势显现越不明显,可用插排替代之。 多少开始变换排序方式呢? 取10个元素为基准 2.遇到连续有序数字怎么处理? 随机化 pivot取rand()%(right-left+1)+left 可以在一定程度上防止最坏情况的出现 做到以上两点 快排基本达到极致 但还有一种情况 3.如果所有元素都是相同的呢? 笔者有幸拜读了某洛谷dalao写的一篇有关快排的题解, 大家可以去品味一下 https://www.luogu.org/problemnew/solution/P1177?page=7 笔者不才只学习了一个可以解决以上问题,较为简短的代码

#include <stdio.h>
#include <stdlib.h>
int n,a[1000000]={0};
void swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
void quicksort(int left,int right)
{
    int mid=a[(left+right)/2];
    int i=left,j=right;
    do
    {
      while(a[i]<mid)   //在左端找比基准数大的数
      {
          i++;
      }
     while(a[j]>mid)      //在右端找比基准数小的数
     {
         j--;
     }
     if(i<=j)       //找到了即为不满足要求,交换之
     {
         swap(&a[i],&a[j]);
         i++;
         j--;
    }
    }while(i<=j);
    if(left<j)quicksort(left,j);
    if(i<right)quicksort(i,right);
}
int main()
{
    printf("请输入要排序的数个数:");
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
}
quicksort(1,n);
for(i=1;i<=n;i++)
{
    printf("%d ",a[i]);
}
    return 0;
}

以上就是七种排序方法,有不足之处请指正,笔者不胜感激。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python Tips(1) 数字与字符串之间转换,采用内置函数

    glm233
  • 过河卒

    P1002 过河卒 题目描述 棋盘上AAA点有一个过河卒,需要走到目标BBB点。卒行走的规则:可以向下、或者向右。同时在棋盘上CCC点有一个对方的马,该马所...

    glm233
  • 数据结构回顾及展望(二)(3.22更新)

    事在人为,盛衰之理,虽曰天命,岂非人事哉!原庄宗之所以得天下,与其所以失之者,可以知之矣。------------《伶官传序》

    glm233
  • 1365 浴火银河星际跳跃

    1365 浴火银河星际跳跃 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 小...

    attack
  • LeetCode 323. 无向图中连通分量的数目(并查集)

    给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。

    Michael阿明
  • 蓝桥杯--算法入门级题目及答案解析

    写在最前面: 本文中会出现大量的请查阅.请自学什么的,不是我不讲,本文是面向算法初学者和蓝桥杯的文章,如果真的想看进阶算法的也不会来看这些题目,所以不要介意,...

    风骨散人Chiam
  • codeforces329B(bfs)

    由于猎人事先知道我们行走的路线,所以猎人们可以先走到终点前等待,可以使用bfs预处理出终点到各个点之间的距离,如果猎人到终点的距离小于等于我们从起点到终点的距离...

    dejavu1zz
  • P3809 【模版】后缀排序

    题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

    attack
  • LeetCode第五天

    leetcode 第五天 2018年1月6日 22.(566) Reshape the Matrix ? ? JAVA class Solution { ...

    郭耀华
  • BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

    Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

    attack

扫码关注云+社区

领取腾讯云代金券