锐客网

  1. 首页 > it技术 > >

C语言数据结构与算法之排序总结(一)

目录

  • 一、前言
  • 二、基本概念
    • 1.排序
    • 2.排序方法的稳定性
    • 3.内部和外部排序
  • 三、插入类排序
    • 1.直接插入排序
    • 2.折半插入排序
    • 3.希尔排序
  • 四、交换类排序
    • 1.冒泡排序
    • 2.快速排序
  • 五、总结比较

    一、前言 学习目标：
    排序和查找密不可分，将待处理的数据按关键值大小有序排列后，查找更加快速准确
    理解各种排序算法的定义和特点，并能将代码灵活运用
    掌握各种排序方法时间复杂度与空间复杂度
    理解排序稳定和不稳定的概念
    重点和难点： 希尔、快速、堆、归并排序这几种快速排序

    二、基本概念
    1.排序
    定义：将一个无序的数据元素任意序列，重新排列成有序的过程
    代码：
    typedef struct{int key; //假设关键字为int型OtherTypeother_data; } RecordType;


    2.排序方法的稳定性
    0 1 2 3 4 5 6 7 8 9
    5 4 10 11 22 8 10 76 1 2
    解读：如上个表格这样的一个无序数组，想要将它按照从小到大排序。上图下标2和6对应的数字都是10，排序后假如红色的10任然在黑色的10前面，那这种排序方法就是稳定的，否则排序方法不稳定。

    3.内部和外部排序
    • 内部排序：整个排序过程在内存中
    • 外部排序：需要排序的数过大，需要借助外部设备

    三、插入类排序 插入类：在一个有序序列插入一个新的记录，使之仍然有序

    1.直接插入排序
    动态演示：

    算法讲解：
    1. 上面的动态图可以很好的表达直接插入的过程，只是动态图有点长
    2. 首先将0作为监视哨，用一个指针从前往后找后面的数字比前面数字小的，找到了放到0
    3. 指针开始向前移动，如果指向的值比监视哨里的值大，数字向后移
    4. 如果指向的值比监视哨里的值小，那把监视哨里的值存入这个元素之后
    5. 以此类推
    代码：
    void InsSort(RecordTyper[],int length)/* 对记录数组r做直接插入排序，length为数组中待排序记录的数目*/{ int i,j; for (i=2; i<=length; i++) {r[0]=r[i]; /*将待插入记录存放到监视哨r[0]中*/j=i-1; while (r[0].key< r[j].key )/* 寻找插入位置 */{r[j+1]= r[j]; j=j-1; }r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/ }} /*InsSort*/

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

    2.折半插入排序
    C语言数据结构与算法之排序总结(一)
    文章图片

    算法讲解：
    1. 动态图没找到，只能用上面这张图片了
    2. 折半插入和折半查找思想差不多，对于一个有序的数组，将一个数字插入之后任然有序
    3. k=要插入的值low=1, high=length , mid=(low+high)+1mid对应的值比k大， high=low-1,否则 low=mid+1,
    4. 当low >high ，low后面就是k插入的位置
    代码：
    void BinSort (RecordTyper[],int length)/*对记录数组r进行折半插入排序，length为数组的长度*/{ int i,j; RecordType x; int low,high,mid; for (i=2; i<=length ; ++i ) {x= r[i]; low=1; high=i-1; while (low<=high )/* 确定插入位置*/ {mid=(low+high) / 2; if ( x.key< r[mid].key) high=mid-1; elselow=mid+1; }for ( j=i-1 ; j>= low; --j )r[j+1]= r[j]; /*记录依次向后移动 */ r[low]=x; /* 插入记录 */ }}/*BinSort*/

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

    3.希尔排序
    动态演示：

    算法讲解：
    1. 对于希尔排序来说取增量 d (d一般为奇数，并且逐次递减)
    2. 上图第一次排序d等于5，将第一个作为起始点，下标+5取下一个值，一直到最后，将去到的值从小到达排序，然后将第二个作为起始点，3 4 5依次作为起始点排序
    3. 第二次是d等于3
    4. 第三次是d等于1
    代码：
    voidShellInsert(RecordType r[], int length,intdelta)/*对记录数组r做一趟希尔插入排序，length为数组的长度,delta 为增量*/{ int i,j; for(i=1+delta; i<= length; i++)/* 1+delta为第一个子序列的第二个元素的下标 */if(r[i].key < r[i-delta].key){r[0]= r[i]; /*备份r[i](不做监视哨) */for(j=i-delta; j>0 &&r[0].key < r[j].key; j-=delta)r[j+delta]= r[j]; r[j+delta]= r[0]; }}/*ShellInsert*/

    特点：
    不稳定排序方法
    增量序列的d取值无除1之外的公因子，最后一个增量值必须为1
    时间复杂度O(nlogn)空间复杂度O(1)

    四、交换类排序
    1.冒泡排序
    动态演示：
    C语言数据结构与算法之排序总结(一)
    文章图片

    算法讲解：
    1. 设立两个指针，i，j
    2. 每一次排序都会把最大的一个数放到后面，依次类推，假设执行2次以后，那么最后2个数就不需要比较了
    3. 执行n-1次排序，结果完成
    代码：
    voidBubbleSort(RecordType r[], int length )/*对记录数组r做冒泡排序，length为数组的长度*/{ int n,i,j; nt change; RecordType x; n=length; change=TRUE; for ( i=1 ; i<= n-1 && change ; ++i ) { change=FALSE; for ( j=1 ; j<= n-i ; ++j) if (r[j].key > r[j+1].key ){x= r[j]; r[j]= r[j+1]; r[j+1]= x; change=TRUE; } }} /*BubbleSort

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

    2.快速排序
    动态演示：

    算法讲解：
    1. 快速排序讲起来稍微有点复杂，其实就是划分区域
    2. 建立两个指针low high 分别指向第一个和第二个元素，把第一个元素的值赋给x变量
    3. high向前移动，假如high指向的值小于x，则high指向的值与x互换
    4. low向后移动，假如low指向的值大于x，则low指向的值与x互换
    5. 重复3 4两步，知道high==low，第一次结束
    6. 将low指向第二个元素，把第二个元素的值赋给x变量
    7. 重复操作，知道元素有序
    代码：
    1.递归算法:
    void QKSort(RecordType r[],int low, int high )/*对记录数组r[low..high]用快速排序算法进行排序*/{ int pos; if(low
    2.非递归算法：
    int QKPass(RecordType r[],int left,int right)/*对记录数组r 中的r[left]至r[right]部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/{ RecordType x; int low,high; x= r[left]; /* 选择基准记录*/ low=left; high=right; while ( low=x.key )/* high从右到左找小于x.key的记录 */high--; if ( low
    特点：
    不稳定排序，但内部排序中公认效率最好的一种
    时间复杂度O(nlogn)空间复杂度O(logn)

    五、总结比较 C语言数据结构与算法之排序总结(一)
    文章图片

    【C语言数据结构与算法之排序总结(一)】以上就是C语言数据结构与算法之排序总结(一)的详细内容，更多关于C语言 数据结构 排序的资料请关注脚本之家其它相关文章！

      推荐阅读


      上一篇：Java实现茶叶售卖商城系统(java+SSM+JSP+EasyUi+mysql)

      下一篇：MySQL索引失效原理