徐州城乡建设网站网站优化工作

前言

本篇博客我们正式开启数据结构中的排序，说到排序，我们能联想到我之前在C语言博客中的冒泡排序，它是排序中的一种，但实现效率太慢，这篇博客我们介绍两种新排序，并好好深入理解排序

💓 个人主页：小张同学zkf

⏩ 文章专栏：数据结构

      若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章 ​

 

 

目录

 1.排序

1.1排序的概念

1.2排序的常见算法

2.插入排序

3.选择排序

---

 

 1.排序

1.1排序的概念

 

---

1.2排序的常见算法

---

2.插入排序

即冒泡排序外，我们来认识一下一个新的排序

 

我们来看一下动图

 

如何用代码实现出来这个插入排序那

我们观察动图其实可以看到假如一趟0~end数是有序的，那么end+1的数得挨个与0~end数比较，比较若比end+1的数大，向右移一位，继续与下一位比较，若比end+1的数小，就插在这个数的前面，进行下一趟重复此过程

代码如下

#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[end+1] = 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;
}

这个排序的时间复杂度O（N）为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 = begin+1; 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;
}

但要注意，将最小数与开头数交换，此刻有可能最大数就是开头数，如果是这种情况，我们要刷新一遍最大值，然后再将最大值与结尾互换。

选择排序的时间复杂度也是O（N^2）但是比效率比冒泡还要低，综上三个排序，插入排序目前最优

---

结束语 

这篇博客先介绍三个排序，与之前的冒泡排序已经有四个，但这些还都是太慢，其中之一的插入排序一定要好好掌握，下片博客的希尔排序要用到插入排序的思维

OK，本篇博客结束！！！