数据结构:七种排序及总结

文章目录

  • 排序
  • 一插入排序
  • 1直接插入排序
  • 2希尔排序
  • 二选择排序
  • 3直接选择排序
  • 4堆排序
  • 三 交换排序
  • 5冒泡排序
  • 6快速排序
  • 四 归并排序
  • 7归并排序
  • 源码

排序

我们数据结构常见的排序有四大种,四大种又分为七小种,如图所示
在这里插入图片描述

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次
序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排
序算法是稳定的;否则称为不稳定的。
内部排序:数据元素全部放在内存中的排序。
外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不断地在内外存之间移动数据的排序。

一插入排序

1直接插入排序

void InsertSort(int* a, int n);

从i=0开始遍历,每次i之前的序列都是有序的,通过判断当前i的值能够在i之前哪个位置,找到后直接插入,

在这里插入图片描述

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

为什么直接插入排序最坏的情况是n^2?
如果一个开始原序列是降序,想排为升序
第一个循环是n,第二个循环最坏是n,所以是最大n^2

void InsertSort(int* arr, int n) {for (int i = 0; i < n-1; i++) {int end = i;int tem = arr[end + 1];while (end >= 0) {if (arr[end] > tem) {arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tem;}}

2希尔排序

希尔排序是对直接插入排序的优化,大大优化了时间复杂度
他们是先规定了一个gap值,然后每次进行循环把gap值缩小,最后把 gap值调为1。这样最后一次排序就是直接插入排序,前面的是预排序。
条件就是

while(gap>1){
gap=gap/3+1;//最后一次gap=1随后跳出循环}
void ShellSort(int* arr, int n) {int gap = n;while(gap>1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++) {int end = i;int tem = arr[end +gap];while (end >= 0) {if (arr[end] > tem) {arr[end + gap] = arr[end];end-=gap;}else{break;}}arr[end + gap] = tem;}	}}

在这里插入图片描述
判断两种排序的时间复杂度
在这里插入图片描述

二选择排序

3直接选择排序

直接选择排序就是一种很暴力的解法,思路简单,代码简单,但是时间复杂度很差,和 冒泡排序差不多
在这里插入图片描述
思路就是分别从两头找最大和最小,然后对下标进行++ – 然后直到相遇。

void SeletSort(int* arr, int n) {int end = n - 1;int begin = 0;int max, min;max = min = 0;while (begin < end) {max = min = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[max]) {max = i;}if (arr[i] < arr[min]){min = i;}}if (max == begin) {max = min;}Swap(&arr[min], &arr[begin]);Swap(&arr[max], &arr[end]);begin++;end--;}}

有一种特殊情况要处理就是换的时候max在begin位置,因为先&arr[min], &arr[begin]换,所以要提前max=min.(此时最大值在min下标位置)

	if (max == begin) {	max = min;		}

时间复杂度n*(n/2+n/2)=n^2.

4堆排序

要了解堆排序我们要先了解一些误区:
1无论向下调整算案建堆还是向上调整算法建堆都是形成一个二叉树结构,本身并没有让数组完全有序,
2向下调整算法建堆比向上调整算法建堆时间复杂度更优
3排升序建大堆,排降序 建小堆。

所以我们要先完成堆排序的话要完成两个步骤,
1把原序列进行向下或向上调整遍历,成为一个堆的结构,
2因为头结点一定是最值,我们每次把arr[0]和arr[end]交换,再让end–完成之后就完成排序。

void HeapSort(HeapType* arr, int n) {//第一步for (int i = (n - 1 - 1) / 2; i >= 0; i--) {AdjustDown(arr, i, n);}int end = n - 1;for (int i = end; i > 0; i--) {//第二步Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}

因为向下调整算法建堆的时间复杂度大概是O(n)
第二部大概是O(nlogn)
故时间复杂度O(n+n
logn)大概是O(n*logn).

三 交换排序

5冒泡排序

冒泡排序两层循环o(n^2)
加上优化还是最好情况O(n)所以是O(n^2)

void BubbleSort(int* a, int n) {for (int i = 0; i < n - 1; i++){int xz = 0;for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {swap(&a[j], &a[j + 1]);xz = 1;}}if (xz == 0) {break;}}}

6快速排序

快排我们用的找中间值 ,然后分区间,类似堆排序,时间复杂度o(nlogn)
按最情况来说,每次循环排最差情况是n/2+n/2=n,一共是logn次循环(最好情况,每次中间值恰好在中间)
按最坏情况是n次循环,所以时间复杂度为n
logn~n^2.

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

int GetKeyi(int* arr, int left, int right) {int keyi = left;left++;while (right>=left){while (left<=right&&arr[right]>arr[keyi]) {right--;}while (left <= right && arr[left] < arr[keyi]) {left++;}if (left <= right) {swap(&arr[right--], &arr[left++]);}}swap(&arr[keyi], &arr[right]);return right;
}
void QuickSort(int* arr, int left,int right) {if (left >= right) {return;}int keyi = GetKeyi(arr, left, right);QuickSort(arr, left,keyi - 1);QuickSort(arr, keyi+1,right);}

四 归并排序

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

7归并排序

归并排序的思想是通过二分找中间值,[left,中间值] ,[中间值+1,right]两个序列再二分,直到left>=中间值,然后通过递归返回原来的函数栈帧进行排序,因为只有logn个函数栈帧,每次栈帧内最坏排n个数据。

为了不破坏arr序列,我们定义了tem序列接收,然后最后把tem数组覆盖arr,
时间复杂度为n*logn

void MergeSort(int* arr, int n) {int* tem = (int*)malloc(sizeof(int) * n);_MergeSort(arr,0, n - 1,tem);free(tem);}
void _MergeSort(int* arr, int left, int right, int* tem) {if (left >= right) {return;}int mid = (left + right) / 2;_MergeSort(arr, left, mid, tem);_MergeSort(arr, mid+1, right, tem);int begin1 = left;int begin2 = mid + 1;int end1 = mid;int end2 = right;int x = begin1;while (begin1 <= end1 && begin2 <= end2) {if (arr[begin1] < arr[begin2]) {	tem[x++] = arr[begin1++];}else{tem[x++] = arr[begin2++];}}while (begin1 <= end1) {tem[x++] = arr[begin1++];}while (begin2 <= end2) {tem[x++] = arr[begin2++];}for (int i = left; i < right; i++){arr[i] = tem[i];}
}

最后总结一下所有排序时间
在这里插入图片描述

源码

Sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#include<stdbool.h>
typedef int HeapType;
typedef struct Heap {HeapType* a;int capacity;int size;}Heap;
void SeletSort(HeapType* arr, int n);
void Inite(Heap* p);
void Push(Heap* p, HeapType x);
void Pop(Heap* p);
bool Empty(Heap* p);
HeapType Top(Heap* p);
void Print(Heap* p);
void Destry(Heap* p);
void Swap(HeapType* a, HeapType* b);
void AdjustUp(HeapType* a, int child);
void AdjustDown(HeapType* a, int parent, int n);
void HeapSort(HeapType* arr, int n);void BubbleSort(int* a, int n);
void swap(int* a, int* b);
void InsertSort(int* arr, int n);
void ShellSort(int* arr, int n);
int GetKeyi(int* arr, int left, int right);
void QuickSort(int* arr, int left, int right);
void MergeSort(int* arr,int n);
void _MergeSort(int* arr, int left, int right, int* tem);void test();

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
#include"time.h"
#include"stdlib.h"int main() {test();return 0;
}

Sort.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"void test() {srand((unsigned)time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);//创建100000个空间的数组int* a2 = (int*)malloc(sizeof(int) * N);//创建100000个空间的数组int* a3 = (int*)malloc(sizeof(int) * N);//创建100000个空间的数组int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; i++) {a1[i] = rand();//循环100000次,每次赋予a1数组随机值a2[i] = a1[i];//赋值值来自上次一数组a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3= clock();SeletSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();BubbleSort(a5, N);int end5 = clock();int begin6= clock();QuickSort(a6, 0,N-1);int end6 = clock();int begin7 = clock();MergeSort(a7,  N - 1);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("BubbleSort:%d\n", end5 - begin5);printf("QuickSort:%d\n", end6 - begin6);printf("MergeSort:%d\n", end7 - begin7);}
void swap(int* a, int* b) {int tmp = *a;*a = *b;*b = tmp;}
void BubbleSort(int* a, int n) {for (int i = 0; i < n - 1; i++){int xz = 0;for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {swap(&a[j], &a[j + 1]);xz = 1;}}if (xz == 0) {break;}}}void InsertSort(int* arr, int n) {for (int i = 0; i < n - 1; i++) {int end = i;int tem = arr[end + 1];while (end >= 0) {if (arr[end] > tem) {arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tem;}}
void ShellSort(int* arr, int n) {int gap = n;while (gap > 1) {gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++) {int end = i;int tem = arr[end + gap];while (end >= 0) {if (arr[end] > tem) {arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tem;}}}
void SeletSort(int* arr, int n) {int end = n - 1;int begin = 0;int max, min;max = min = 0;while (begin < end) {max = min = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[max]) {max = i;}if (arr[i] < arr[min]){min = i;}}if (max == begin) {max = min;}Swap(&arr[min], &arr[begin]);Swap(&arr[max], &arr[end]);begin++;end--;}}
void Inite(Heap* p) {p->a = NULL;p->capacity = p->size = 0;}
void Push(Heap* php, HeapType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HeapType* tmp = (HeapType*)realloc(php->a, newcapacity * sizeof(HeapType));if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
void Pop(Heap* p) {Swap(&p->a[0], &p->a[p->size - 1]);p->size--;AdjustDown(p->a, 0, p->size);}
bool Empty(Heap* p) {return p->size == 0;}
HeapType Top(Heap* p) {return p->a[0];}
void Print(Heap* p) {{while (!Empty(p)){printf("%d ", Top(p));Pop(p);}}
}
void Swap(HeapType* a, HeapType* b) {int tem = *a;*a = *b;*b = tem;}
void AdjustUp(HeapType* a, int child) {int parent = (child - 1) / 2;while (child > 0) {if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(HeapType* a, int parent, int n) {int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] > a[child + 1]) {child = child + 1;}if (a[parent] > a[child]) {Swap(&a[parent], &a[child]);parent = child;child = child * 2 + 1;}else{break;}}}
void HeapSort(HeapType* arr, int n) {for (int i = (n - 1 - 1) / 2; i >= 0; i--) {AdjustDown(arr, i, n);}int end = n - 1;for (int i = end; i > 0; i--) {Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}
int GetKeyi(int* arr, int left, int right) {int keyi = left;left++;while (right>=left){while (left<=right&&arr[right]>arr[keyi]) {right--;}while (left <= right && arr[left] < arr[keyi]) {left++;}if (left <= right) {swap(&arr[right--], &arr[left++]);}}swap(&arr[keyi], &arr[right]);return right;
}
void QuickSort(int* arr, int left,int right) {if (left >= right) {return;}int keyi = GetKeyi(arr, left, right);QuickSort(arr, left,keyi - 1);QuickSort(arr, keyi+1,right);}
void MergeSort(int* arr, int n) {int* tem = (int*)malloc(sizeof(int) * n);_MergeSort(arr,0, n - 1,tem);free(tem);}
void _MergeSort(int* arr, int left, int right, int* tem) {if (left >= right) {return;}int mid = (left + right) / 2;_MergeSort(arr, left, mid, tem);_MergeSort(arr, mid+1, right, tem);int begin1 = left;int begin2 = mid + 1;int end1 = mid;int end2 = right;int x = begin1;while (begin1 <= end1 && begin2 <= end2) {if (arr[begin1] < arr[begin2]) {	tem[x++] = arr[begin1++];}else{tem[x++] = arr[begin2++];}}while (begin1 <= end1) {tem[x++] = arr[begin1++];}while (begin2 <= end2) {tem[x++] = arr[begin2++];}for (int i = left; i < right; i++){arr[i] = tem[i];}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/466622.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

A day a tweet(sixteen)——The better way of search of ChatGPT

Introducing ChatGPT search a/ad.及时的/及时地 ChatGPT can now search the web in a much better way than before so you get fast, timely a.有关的(relative n.亲戚,亲属;同类事物 a.比较的&#xff1b;相对的) answers with link…

HTMLCSS:呈现的3D树之美

效果演示 这段代码通过HTML和CSS创建了一个具有3D效果的树的图形&#xff0c;包括分支、树干和阴影&#xff0c;通过自定义属性和复杂的变换实现了较为逼真的立体效果。 HTML <div class"container"><div class"tree"><div class"…

系统规划与管理师——第十二章 职业素养与法侓法规

目录 职业素养 职业道德 行为规范 职业责任 对客户和公众的责任 法律法规 法律概念 法律体系 诉讼时效 民事诉讼时效 刑事追诉时效 常用的法律法规 合同法 招投标法 著作权法 政府采购法 劳动法 知识产权法 刑法修正案&#xff08;七) IT服务的广泛应用不仅…

HAL库硬件IIC驱动气压传感器BMP180

环境 1、keilMDK 5.38 2、STM32CUBEMX 初始配置 默认即可。 程序 1、头文件 #ifndef __BMP_180_H #define __BMP_180_H#include "main.h"typedef struct {float fTemp; /*温度&#xff0c;摄氏度*/float fPressure; /*压力&#xff0c;pa*/float fAltitude; /*…

沈阳乐晟睿浩科技有限公司抖音小店展望未来

在当今数字化浪潮汹涌的时代&#xff0c;电子商务以其独特的魅力和无限潜力&#xff0c;正深刻改变着人们的消费习惯与商业模式。抖音小店作为短视频与电商深度融合的产物&#xff0c;凭借其庞大的用户基础、精准的内容推送机制以及独特的购物体验&#xff0c;迅速崛起为电商领…

【论文复现】自动化细胞核分割与特征分析

本文所涉及所有资源均在这里可获取。 作者主页&#xff1a; 七七的个人主页 文章收录专栏&#xff1a; 论文复现 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01;&#x1f496;&#x1f496; 自动化细胞核分割与特征分析 引言效果展示HoverNet概述HoverNet原理分析整…

ESP32 gptimer通用定时器初始化报错:assert failed: timer_ll_set_clock_prescale

背景&#xff1a;IDF版本V5.1.2 &#xff0c;配置ESP32 通用定时器&#xff0c;实现100HZ&#xff0c;占空比50% 的PWM波形。 根据乐鑫官方的IDF指导文档设置内部计数器的分辨率&#xff0c;计数器每滴答一次相当于 1 / resolution_hz 秒。 &#xff08;ESP-IDF编程指导文档&a…

Jest项目实战(4):将工具库顺利迁移到GitHub的完整指南

开源代码&#xff1a;将工具库迁移到GitHub 随着项目的成熟和完善&#xff0c;将其开源不仅可以获得更多的用户和贡献者&#xff0c;还能促进项目本身的发展。GitHub作为全球最大的开源协作平台&#xff0c;自然成为了大多数开发者的首选。本文将引导您完成将工具库迁移至GitH…

C#线程池

目录 前言 线程 线程池 线程池的工作原理 重要方法 C#线程池总结 前言 线程池是一种多线程处理形式&#xff0c;它允许开发者将任务添加到队列中&#xff0c;然后线程池会自动管理线程的创建、分配和回收&#xff0c;以执行这些任务。线程池中的线程都是后台线程&#xf…

SpringBoot项目集成ONLYOFFICE

ONLYOFFICE 文档8.2版本已发布&#xff1a;PDF 协作编辑、改进界面、性能优化、表格中的 RTL 支持等更新 文章目录 前言ONLYOFFICE 产品简介功能与特点Spring Boot 项目中集成 OnlyOffice1. 环境准备2. 部署OnlyOffice Document Server3. 配置Spring Boot项目4. 实现文档编辑功…

用示例来看C2Rust工具的使用和功能介绍

C2Rust可以将C语言的源代码转换成Rust语言的源代码。下面是一个简单的C语言代码示例&#xff0c;以及使用c2Rust工具将其转换为Rust安全代码的过程。 C语言源代码示例 // example.c #include <stdio.h>int add(int a, int b) {return a b; }int main() {int result a…

【IC验证】systemverilog的设计特性

systemverilog的设计特性 一.概述二.面向硬件的过程语句块1.说明2.always_comb2.always_latch3.always_ff 三.关系运算符1.说明2.例子 四.inside判定符1.说明2.例子 五.条件分支语句&#xff08;1&#xff09;说明&#xff08;2&#xff09;例子&#xff08;case和unique case的…

计算不停歇,百度沧海数据湖存储加速方案 2.0 设计和实践

数据湖这个概念&#xff0c;从 2012 年产生到现在已经有十余年的时间&#xff0c;每家公司对它内涵的解读都不太一样。但是数据湖的主要存储底座有从传统的 HDFS 向对象存储演进的趋势。 传统的大数据计算场景&#xff0c;比如 MapReduce、Spark、Hive 这些大数据组件都是基于…

信息化运维方案,实施方案,开发方案,信息中心安全运维资料(软件资料word)

1 编制目的 2 系统运行维护 2.1 系统运维内容 2.2 日常运行维护方案 2.2.1 日常巡检 2.2.2 状态监控 2.2.3 系统优化 2.2.4 软件系统问题处理及升级 2.2.5 系统数据库管理维护 2.2.6 灾难恢复 2.3 应急运行维护方案 2.3.1 启动应急流程 2.3.2 成立应急小组 2.3.3 应急处理过程 …

【网络面试篇】HTTP(2)(笔记)——http、https、http1.1、http2.0

目录 一、相关面试题 1. HTTP 与 HTTPS 有哪些区别&#xff1f; 2. HTTPS 的工作原理&#xff1f;&#xff08;https 是怎么建立连接的&#xff09; &#xff08;1&#xff09;ClientHello &#xff08;2&#xff09;SeverHello &#xff08;3&#xff09;客户端回应 &a…

使用文心快码生成口算题,妈妈再也不用担心我的学习了

2024年10月NJSD技术盛典暨第十届NJSD软件开发者大会、第八届IAS互联网架构大会在南京召开。百度文心快码总经理臧志分享了《AI原生研发新范式的实践与思考》&#xff0c;探讨了大模型赋能下的研发变革及如何在公司和行业中落地&#xff0c;AI原生研发新范式的内涵和推动经验。 …

C#笔记 —— 事件

事件的语法 访问修饰符 event 委托类型 事件名&#xff1b; 例&#xff1a; public event Action myEvent; 事件的使用 事件的使用跟委托基本上一模一样&#xff0c; 1.但是事件不能在类外部直接赋值&#xff0c;只能使用 或 - 添加或删除函数&#xff1b; 2.事件不能在类…

JavaScript3*3表格实现每次点击只红一行

<script> window.onload function () { var myTd document.getElementsByTagName("td"); var currentlyHighlightedRow null; // 用于存储当前高亮显示的行 for (var i 0; i < myTd.length; i) { myTd[i].onclick function () { …

物理验证Calibre LVS | SMIC Process过LVS时VNW和VPW要如何做处理?

SMIC家工艺的数字后端实现PR chipfinish写出来的带PG netlist如下图所示。我们可以看到标准单元没有VNW和VPW pin的逻辑连接关系。 前几天小编在社区星球上分享了T12nm ananke_core CPU低功耗设计项目的Calibre LVS案例&#xff0c;就是关于标准单元VPP和VBB的连接问题。 目前…

基于Spring Boot的船舶监造系统的设计与实现,LW+源码+讲解

摘要 近年来&#xff0c;信息化管理行业的不断兴起&#xff0c;使得人们的日常生活越来越离不开计算机和互联网技术。首先&#xff0c;根据收集到的用户需求分析&#xff0c;对设计系统有一个初步的认识与了解&#xff0c;确定船舶监造系统的总体功能模块。然后&#xff0c;详…