数据结构第六课 -----排序

2023-12-12 20:36
文章标签 数据结构 排序 第六课

本文主要是介绍数据结构第六课 -----排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者前言

🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂
​🎂 作者介绍： 🎂🎂
🎂 🎉🎉🎉🎉🎉🎉🎉 🎂
🎂作者id：老秦包你会， 🎂
简单介绍：🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂
喜欢学习C语言和python等编程语言，是一位爱分享的博主，有兴趣的小可爱可以来互讨 🎂🎂🎂🎂🎂🎂🎂🎂
🎂个人主页::小小页面🎂
🎂gitee页面:秦大大🎂
🎂🎂🎂🎂🎂🎂🎂🎂
🎂 一个爱分享的小博主 欢迎小可爱们前来借鉴🎂

排序

  • **作者前言**
  • 直接插入排序
  • 冒泡排序
  • 希尔排序
  • 直接选择排序
  • 堆排序
  • 快速排序
      • hoare版本
    • 优化点
      • 三数取中
    • 小区间优化
    • 挖坑法
    • 前后指针版本
  • 疑惑

直接插入排序

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

思路： 我们要记得[0,end]是有序的,我们要把tmp的值插入到[0,end]就要进行判断,直到tmp等于数组的长度结束,这个过程中我们要注意到我们把tmp插入到[0,end] 是要遍历[0,end]的当我们判断当前的元素大于tmp,就把这个元素往后移动,我们就要往后一个元素比较,直到碰见比tmp小的元素,并再该元素后面插入,如果碰见了在[0,end]都没有小于tmp的元素,我们就要在下标为0的地方插入,

void InsertSort(int* a, int n)
{//[0,end] int i = 0;for (i = 0; i < n-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;}}//这个写法一箭双雕,一来可以防止end为-1的情况不用去判断,二来可以插入到a[end + 1]a[end + 1] = tmp;}
}

冒泡排序

在这里插入图片描述

// 冒泡排序
void Bubblisort(int* a, int n)
{int i = 0; for (i = 0; i < n - 1; i++){//如果该数组是一个有序数组,只需遍历一遍下面的就可以了,时间复杂度为O(N)bool excheng = false;int j = 0;for (j = 0; j < n - 1 - i; j++){if (a[j] > a[j + 1]){int c = a[j];a[j] = a[j + 1];a[j + 1] = c;excheng = true;}}if (excheng == false)break;}
}

时间复杂度是O(N^2), 最好的情况就是O(N)

希尔排序

在这里插入图片描述

分成两步:
1.预排序 (接近有序)
2.直接插入排序
思路:
在这里插入图片描述
相同颜色的框进行插入排序,因为多少种颜色是有gap的数值决定的,每一种颜色对应的是整个数组的一部分

//预排序int gap = 3;int i = 0;//有gap个数组for (i = 0; i < gap; i++){//每个数组进行插入排序int sub = i;while (sub <= n - 1 - gap){int end = sub;int top = a[end + gap];while (end >= 0){if (top < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = top;sub += gap;}}

上面这种是一组组进行插入排序.如果是多组进行插入排序

在这里插入图片描述
思路就是我们仍然采用上面的方法,但是我们是多组进行插入排序,仍然是相同颜色的进行插入排序

//预排序int gap = 3;int i = 0;//有gap个数组for (i = 0; i <= n - 1 - gap; i++){//每个数进行插入排序int end = i;int top = a[end + gap];while (end >= 0){if (top < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = top;}

预排序的特点:
gap越大,大的值更快调到后面,小的值可以更快的调到前面,越不接近有序
gap越小,跳得越慢,但是越接近有序,如果gap == 1就是直接插入排序
最终代码为

//希尔排序
void ShellSort(int* a, int n)
{//预排序int gap = 3;int i = 0;//有gap个数组for (i = 0; i <= n - 1 - gap; i++){//每个数进行插入排序int end = i;int top = a[end + gap];while (end >= 0){if (top < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = top;}//直接插入排序InsertSort(a, n);
}

但是我们可以简化一下
我们可以抓住gap=1为直接插入排序

//希尔排序
void ShellSort(int* a, int n)
{//预排序int gap = n;while (gap > 1){//一来gap等于1时,就是直接插入排序,二来就是gap是随n增大的,//再还有就是gap越小,就越接近有序gap = gap / 3 + 1;int i = 0;//有gap个数组for (i = 0; i <= n - 1 - gap; i++){//每个数进行插入排序int end = i;int top = a[end + gap];while (end >= 0){if (top < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = top;}}}

在这里插入图片描述
时间复杂度O（N ^1.3）,这个有点难算,我们只需要理解大概就行

直接选择排序

在这里插入图片描述
思路：从开头开始找，找到最小的，然后进行和开头交换，然后再从剩下的后面继续寻找最小的，依次往后插入
思路图1：这个思路是很多人能想出来的

在这里插入图片描述
思路图2：

在这里插入图片描述

​这里我是使用了两边，左边插入最小的，右边插入最大的，插入好后，begin往前 ，end往后，直到begin等于end，就停止了

void excheng(int* a, int* b)
{int c = *a;*a = *b;*b = c;
}
//直接选择排序
void SelectSrot(int* a, int n)
{int min = 0, max = 0; //找出最大和最小int begin = 0, end = n - 1;// 在最大和最小的位置插入for (int i = begin + 1; i <= end; i++){int idx = i;while (idx <= end){//找出最小的值if (a[min] > a[idx])min = idx;//找到最大值if (a[max] < a[idx])max = idx;idx++;}excheng(&a[begin], &a[min]);//防止开头就是最大值,一旦最小值交换,就乱了if (max == begin)max = min;excheng(&a[end], &a[max]);begin++;end--;}
}

时间复杂度是 O（N^2）

堆排序

大家可以观看这部博客
堆排序
在这里插入图片描述

//堆排序
typedef int Heapdata;
void exchange(Heapdata* a, Heapdata* b)
{Heapdata e = *a;*a = *b;*b = e;
}
void Heapsort(Heapdata* heap, int size)
{//建大堆int i = 0;for (i = 1; i < size; i++){//向上调整int child = i;int parent = (child - 1) / 2;while (child > 0){if (heap[child] > heap[parent]){//交换exchange(&heap[child], &heap[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}//开始升序排序while (size > 0){// 根节点和最后一个叶节点交换exchange(&heap[0], &heap[--size]);//向下调整int parent = 0;int child = parent * 2 + 1;while (child < size){if (child + 1 < size && heap[child] < heap[child + 1]){child += 1;}if (heap[child] > heap[parent])exchange(&heap[child], &heap[parent]);elsebreak;parent = child;child = parent * 2 + 1;}}}

快速排序

hoare版本

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
在这里插入图片描述
这个图可能有点简陋
在这里插入图片描述
在这里插入图片描述
时间复杂度：每一次都会把当前数组的每个元素遍历一遍，然后再把key交换， 需要进行log（n）次递归
时间复杂度是：O(n*log(n))
在这里插入图片描述
复杂的话,就如同这个一样,这种情况就是有n层, 时间复杂度就是 1+2+3+…+n, 所以时间复杂度就是O(n^2)

//快速排序
void QuickSrot(int* a, int begin, int end)
{//当只有一个元素就不用进行了if (begin >= end)return;int key = begin;int left = begin;//这里不能begin加1 否则在遇到有序的时候就会排序出错int right = end;while (left < right){// 找最小while (left < right){if (a[right] < a[key]){break;}right--;}// 找最大while (left < right){if (a[left] > a[key]){break;}left++;}excheng(&a[right], &a[left]);}excheng(&a[right], &a[key]);//左QuickSrot(a, begin, right - 1);// 右QuickSrot(a, right + 1, end);
}

优化点

三数取中

思路:
我们可以在数组的前后和中间选取中位数,然后把中位数和开头进行交换,

int TriNum(int *a,int begin, int end)
{int mid = (begin - end) / 2 + end;if (begin > end){if (end > mid){return end;}else if(begin < mid){return begin;}return mid;}else{if (begin > mid){return begin;}else if (end < mid){return end;}elsereturn mid;}
}
//快速排序
void QuickSrot(int* a, int begin, int end)
{//当只有一个元素就不用进行了if (begin >= end)return;//三数取中int key = 0;key = TriNum(a, begin, end);exchange(&a[begin], &a[key]);key = begin;int left = begin;int right = end;//普通方法//int key = begin;//int left = begin;//这里不能begin加1 否则在遇到有序的时候就会排序出错//int right = end;while (left < right){// 找最小while (left < right){if (a[right] < a[key]){break;}right--;}// 找最大while (left < right){if (a[left] > a[key]){break;}left++;}excheng(&a[right], &a[left]);}excheng(&a[right], &a[key]);//左QuickSrot(a, begin, right - 1);// 右QuickSrot(a, right + 1, end);
}

小区间优化

当我们在使用快速排序的时候，一直排序知道递归到还剩下该数组的10%的数没有排序，我们如果使用递归就很对栈的空间浪费很大。那我们可以选择使用插入排序，

//快速排序
void QuickSrot(int* a, int begin, int end)
{//当只有一个元素就不用进行了if (begin >= end)return;if (end - begin  + 1 <= 10){//插入排序InsertSort(a + begin, end - begin + 1);//我们要清楚要从哪里开始插入排序}else{//三数取中int key = 0;key = TriNum(a, begin, end);excheng(&a[begin], &a[key]);key = begin;int left = begin;int right = end;//普通方法,有可能会栈溢出//int key = begin;//int left = begin;//这里不能begin加1 否则在遇到有序的时候就会排序出错//int right = end;while (left < right){// 找最小while (left < right){if (a[right] < a[key]){break;}right--;}// 找最大while (left < right){if (a[left] > a[key]){break;}left++;}excheng(&a[right], &a[left]);}excheng(&a[right], &a[key]);//左QuickSrot(a, begin, right - 1);// 右QuickSrot(a, right + 1, end);}}

挖坑法

在这里插入图片描述

//挖坑法
void QuickSrot2(int* a, int begin, int end)
{if (begin >= end)return;if (end - begin + 1 <= 10){InsertSort(a + begin, end - begin + 1);}else{//三数取中int key = TriNum(a, begin, end);excheng(&a[key], &a[begin]);//坑key = begin;int num = a[key];int left = begin;int right = end;while (left < right){//找小while (left < right){if (a[right] < num){a[key] = a[right];key = right;break;}right--;}//找大while (left < right){if (a[left] > num){a[key] = a[left];key = left;break;}left++;}}a[key] = num;//左QuickSrot(a, begin, right - 1);// 右QuickSrot(a, right + 1, end);}}

前后指针版本

在这里插入图片描述
思路:
cur遇见比key大的值,cur++
cur遇见比key小的值,prev++,交换prev和cur的值交换,然后cur++
在这里插入图片描述

//前后指针版本
// 快速排序版本3
void QuickSrot3(int* a, int begin, int end)
{if (begin >= end)return;int key = TriNum(a, begin, end);excheng(&a[key], &a[begin]);key = begin;int prev = begin;int cur = begin + 1;while (cur <= end){//cur 比较if (a[cur] < a[key] && ++prev != cur)//增加++prev != cur可以有效解决相同位置进行交换{exchange(&a[cur], &a[prev]);}cur++;}exchange(&a[key], &a[prev]);//左QuickSrot(a, begin, prev - 1);// 右QuickSrot(a, prev + 1, end);
}

疑惑

在这里插入图片描述

  1. 为什么相遇位置比key小
    原因:是right先走
    两种情况:
    (1).R遇见L —>(L和R交换后,R先走)R没有找到比key小的,一直走,直到R遇见L,(特殊情况除外)
    (2)L遇见R----->(R找到小了),然后L没有找到比key大的,一直走,直到L遇见R,(特殊情况除外)

这篇关于数据结构第六课 -----排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/485853。

相关文章

Mybatis 传参与排序模糊查询功能实现

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》：本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
C++快速排序超详细讲解

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
Spring排序机制之接口与注解的使用方法

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri
阅读更多...
大数据小内存排序问题如何巧妙解决

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法：数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高；分治法高效但实现复杂；位图法可读性差,但存储空间受限... 目录三种方法：方法概要数据库排序（http://www.chinasem.cn对数据库设备要求较高）分治法（常
阅读更多...
Python中lambda排序的六种方法

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序
阅读更多...
关于Java内存访问重排序的研究

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2