网站主机和空间,淘宝客建站模板,云南建设招标网站首页,vi设计步骤流程前言 本篇博客我们正式开启数据结构中的排序#xff0c;说到排序#xff0c;我们能联想到我之前在C语言博客中的冒泡排序#xff0c;它是排序中的一种#xff0c;但实现效率太慢#xff0c;这篇博客我们介绍两种新排序#xff0c;并好好深入理解排序 #x1f493; 个人主… 前言 本篇博客我们正式开启数据结构中的排序说到排序我们能联想到我之前在C语言博客中的冒泡排序它是排序中的一种但实现效率太慢这篇博客我们介绍两种新排序并好好深入理解排序 个人主页小张同学zkf ⏩ 文章专栏数据结构 若有问题 评论区见 欢迎大家点赞收藏⭐文章 目录 1.排序
1.1排序的概念
1.2排序的常见算法
2.插入排序
3.选择排序 1.排序
1.1排序的概念 排序 所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序 数据元素全部放在内存中的排序。 外部排序 数据元素太多不能同时放在内存中根据排序过程的要求不断地在内外存之间移动数据的排序。 1.2排序的常见算法 2.插入排序
即冒泡排序外我们来认识一下一个新的排序 直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为 止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想 我们来看一下动图 如何用代码实现出来这个插入排序那
我们观察动图其实可以看到假如一趟0~end数是有序的那么end1的数得挨个与0~end数比较比较若比end1的数大向右移一位继续与下一位比较若比end1的数小就插在这个数的前面进行下一趟重复此过程
代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
void charupaixu(int* a, int x)
{for (int i 0; i x - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end1] a[end];end--;}else{break;}}a[end 1] tmp;}
}
int main()
{int arr[] { 2,4,89,23,987,123,5678,13,76,67,6666};charupaixu(arr, sizeof(arr) / sizeof(arr[0]));for (int i 0; i sizeof(arr) / sizeof(arr[0]); i){printf(%d , arr[i]);}return 0;
}
这个排序的时间复杂度ON为N^2但相比冒泡效率还是快的 3.选择排序 选择排序其实思路特别简单通过最前面与最后面的指针进行遍历找到最大的与最小的将最小的与开头的数交换最大的与最后面的数交换再两边指针减减重复此过程
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
void swap(int* as, int* aq)
{int tmp *as;*as *aq;*aq tmp;
}
void xuanzepaixu(int* a, int n)
{int begin 0;int end n-1;while (begin end){int max begin;int min begin;for (int i begin1; i end; i){if (a[min] a[i]){min i;}if (a[max] a[i]){max i;}}swap(a[min], a[begin]);if (begin max){max min;}swap(a[max], a[end]);begin;end--;}
}
int main()
{int arr[] { 34,56,56,87,7644,79,382,4657,272687,246581,6341,346345,5,267,7,22,2724,57 };xuanzepaixu(arr, sizeof(arr) / sizeof(arr[0]));for (int i 0; i sizeof(arr) / sizeof(0); i){printf(%d , arr[i]);}return 0;
}
但要注意将最小数与开头数交换此刻有可能最大数就是开头数如果是这种情况我们要刷新一遍最大值然后再将最大值与结尾互换。
选择排序的时间复杂度也是ON^2但是比效率比冒泡还要低综上三个排序插入排序目前最优 结束语 这篇博客先介绍三个排序与之前的冒泡排序已经有四个但这些还都是太慢其中之一的插入排序一定要好好掌握下片博客的希尔排序要用到插入排序的思维 OK本篇博客结束
