c语言数据结构冒泡|选择|插入|希尔

简介: 目录冒泡排序:选择排序:插入排序:希尔排序:冒泡排序:原理:基于交换的排序,每一轮将序列中的最大值(最小值)放到数组的尾部。使用循环重复操作,(每轮排序都会少一个最大值或最小值),当最后只剩下一个数据的时候整个序列就已经排好序了。 代码思路:从第一个数开始,每一次在数组中选两个数继续比较,如果前面的数大于后面的数,就将两者交换位置,第一次是1,2两个位置比较,第二次就是2,3两个位置比较,以此类推//采用两层循环实现的方法//arr是待排序数组的首地址,n是数组元素个数void bubblesort1(int* arr, int n){ if (n < 2)

目录

冒泡排序:

选择排序:

插入排序:

希尔排序:


冒泡排序:

原理:基于交换的排序,每一轮将序列中的最大值(最小值)放到数组的尾部。使用循环重复操作,(每轮排序都会少一个最大值或最小值),当最后只剩下一个数据的时候整个序列就已经排好序了。


代码思路:从第一个数开始,每一次在数组中选两个数继续比较,如果前面的数大于后面的数,就将两者交换位置,第一次是1,2两个位置比较,第二次就是2,3两个位置比较,以此类推

//采用两层循环实现的方法//arr是待排序数组的首地址,n是数组元素个数voidbubblesort1(int*arr, intn)
{
if (n<2)
return ;//数组个数小于2不需要排序inti;//排序次数intj;//每次排序元素位置inttmp;//交换位置时的临时变量for (i=n-1; i>0; i--)//一共进行n-1次    {
for (j=0; j<i; j++)//每次比较0和i之前的元素,i之后已经排好        {
if (arr[j] >arr[j+1])//如果前面大于后面,则交换位置            {
tmp=arr[j+1];
arr[j+1] =arr[j];
arr[j] =tmp;
            }
        }
    }
}

直接使用两层循环去实现,外层循环主要作用改变次数,保存最小值(最大值),内存循环的主要作用是找到发生冲突的元素,如果发生冲突就交换两个数据。当两层循环的结束的时候整个序列就自然排好序了

此外,还有一种方法:

//采用递归的方法voidbubblesort2(int*arr, intn)
{
if (n<2)
return;//数组个数小于2不需要排序intj;//每次排序元素位置inttmp;//交换位置时的临时变量for (j=0; j<n-1; j++)//每次比较0和n-1之前的元素,n-1之后已经排好    {
if (arr[j] >arr[j+1])//如果前面大于后面,则交换位置        {
tmp=arr[j+1];
arr[j+1] =arr[j];
arr[j] =tmp;
        }
    }
bubblesort2(arr, --n);
}

递归方法和两层循环方法相似,只是将第一次的循环以递归的形式展现

intmain()
{
intarr[15] = { 44,3,38,5,47,15,36,26,24,2,46,4,19,50,48 };
//bubblesort1(arr, 15);bubblesort2(arr, 15);
for (inti=0; i<15; i++)
    {
printf("%d ", arr[i]);
    }
printf("\n");
return0;
}

运行结果:

选择排序:

原理:基本思想和冒泡排序是一样的,选择排序相对于冒泡排序的优点就是减少交换次数。算法思想都是在序列中找到最大值(最小值),然后存放好下次进入循环就访问不到这个最大值(最小值)。当两层循环都结束的时候序列就自然排好了。


代码思路:从第一个元素开始,往后寻找,在n个数中找到最小的值,将其与第一个元素交换位置,然后从第二个元素开始继续往后寻找,在n-1个元素中找到最小的元素,与第二个元素交换位置,以此类推

//采用两层循环实现的方法//arr是待排序数组的首地址,n是数组元素个数voidselectsort1(int*arr, intn)
{
if (n<2)
return;//数组个数小于2不需要排序inti;//排序次数intj;//每次排序元素位置inttmp;//每次循环时最小的元素位置for (i=0; i<n-1; i++)//一共进行n-1次比较    {
tmp=i;
for (j=i+1; j<n; j++)//每次只需要比较i+1和n-1之间的元素,i之前的是已经排序号的        {
if (arr[j] <arr[tmp])//找到值更小的元素,记下位置tmp=j;
        }
if (tmp!=i)//如果此次循环的最小元素表示起始位置的元素,就交换他们的位置        {
intk=arr[tmp];
arr[tmp] =arr[i];
arr[i] =k;
        }
    }
}

同样的,与冒泡排序类似,选择排序也可以转换为递归形式:

//采用递归的方法voidselectsort2(int*arr, intn)
{
intj;//每次排序元素位置inttmp=0;//每次循环时最小的元素位置for (j=1; j<n; j++)//每次只需要比较i+1和n-1之间的元素,i之前的是已经排序号的    {
if (arr[j] <arr[tmp])//找到值更小的元素,记下位置tmp=j;
    }
if (tmp!=0)//如果此次循环的最小元素表示起始位置的元素,就交换他们的位置    {
intk=arr[tmp];
arr[tmp] =arr[j];
arr[j] =k;
    }
selectsort2(arr+1, --n);
}

插入排序:

原理:基本思想还是冒泡排序,不过插入排序是两边相靠的冒泡,所以在序列部分有序的情况下,插入排序的效率要比冒泡排序效率高。从序列的尾部开始往前比较,如果当前的数据小于(大于)前一个的数据就进行交换,否则进入下一次循环,直到外层循环遍历完整个序列就自然排好序了。


代码思路:从第二个元素开始,将第二个元素与前面第一个元素比较,如果比第一个元素大则位置不变,如果比他小则将第一个位置元素后移,将第二个位置的元素插入第一个位置,以此类推,让第三个元素与前面两个元素比较,如果第三个元素大于第二个位置的元素,则不变,如果小于第二个位置的元素,就将第二个位置的元素后移到第三个位置(此时第二个位置空缺),然后原来第三个元素再与第一个位置的元素比较,如果大于则顺理成章插入到第二个位置中,如果小于则第一个位置的元素后移,将原第三个位置的元素插入第一个位置

voidinsertsort(int*arr,intn)
{
if (n<2)
return;//数组个数小于2不需要排序inti;//待排序的元素intj;//每次插入时需要后移的元素inttmp;//当前需要排序的元素的值for (i=1; i<n; i++)
    {
tmp=arr[i];//待排序的元素//从已排序的最右边开始,把大于当前排序的元素后移for (j=i-1; j>=0; j--)
        {
if (arr[j] <=tmp)
break;
arr[j+1] =arr[j];
        }
//插入当前排序元素arr[j+1] =tmp;
    }
}
intmain()
{
intarr[15] = { 44,3,38,5,47,15,36,26,24,2,46,4,19,50,48 };
insertsort(arr, 15);
for (inti=0; i<15; i++)
    {
printf("%d ", arr[i]);
    }
printf("\n");
return0;
}

运行结果:

希尔排序:

原理:希尔排序是建立在插入排序的基础上进行优化的排序算法,所以希尔排序又叫做优化版的插入排序。


希尔排序的基本思想是把待排序的数列分为多组,然后再对每个组进行插入排序,先让数列整体大致有序,然后多次调整分组方式,使数列更加有序,最后再使用一次插入排序,使整个数列全部有序


代码思路:先将整个数组一分为二,再将每个组相同位置的元素比较大小,如果第二个组第一个元素小于第一个组第一个元素,就将两者交换位置,然后比较两个组第二个位置的元素大小,将两个组都比较完以后,再次分组,这一次将两个组各一分为二,各自比较,分到最后就变成了每个元素一一比较

//对希尔排序中的单个组进行排序voidgroupsort(int*arr,intn,intpos,intstep)
{
inti;//待排序的元素intj;//每次插入时需要后移的元素inttmp;//当前需要排序的元素的值for (i=pos+step; i<n; i=i+step)
    {
tmp=arr[i];//待排序元素for (j=i-step; j>=0; j=j-step)
        {
if (arr[j] <=tmp)
break;
arr[j+step] =arr[j];
        }
arr[j+step] =tmp;
    }
}
//希尔排序voidshellsort(int*arr,intn)
{
intstep;//每组个数,每次减为原来的一半取整数,最后一次必定为1for (step=n/2; step>0; step=step/2)
    {
for (inti=0; i<step; i++)
        {
groupsort(arr, n, i, step);
        }
    }
}


相关文章
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
376 4
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
390 4
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
984 1
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
719 5
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
874 1
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
563 59
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
1409 77
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
394 0
栈区的非法访问导致的死循环(x64)