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

news/2024/11/8 17:16:54 标签: 数据结构, 排序算法, 算法

文章目录

  • 排序
  • 一插入排序
  • 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+nlogn）大概是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次循环，所以时间复杂度为nlogn~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.niftyadmin.cn/n/5744195.html

相关文章

YOLOv6-4.0部分代码阅读笔记-figure_iou.py

YOLOv6-4.0部分代码阅读笔记-figure_iou.py

figure_iou.py yolov6\utils\figure_iou.py 目录 figure_iou.py 1.所需的库和模块 2.class IOUloss: 3.def pairwise_bbox_iou(box1, box2, box_formatxywh): 1.所需的库和模块 #!/usr/bin/env python3 # -*- coding:utf-8 -*- import math import torch2.class IOUlo…
阅读更多...
【热门主题】000027 React：前端框架的强大力量

【热门主题】000027 React：前端框架的强大力量

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 【热…
阅读更多...
◇【论文_20160610】Generative Adversarial Imitation Learning 【附录 A】

◇【论文_20160610】Generative Adversarial Imitation Learning 【附录 A】

文章目录 A 证明Section 3 的证明引理 3.1 证明命题 3.2 的证明 A.2 Section 5 的证明命题 A.1推论 A.1.1引理 A.1 因果熵的策略梯度公式 A 证明 Section 3 的证明 引理 3.1 证明 Proof of Lemma 3.1. 首先&#xff0c;我们证明 H ˉ \bar H Hˉ 是严格凹的。 令 ρ \rho ρ…
阅读更多...
阿里云多端低代码开发平台魔笔使用测评

阿里云多端低代码开发平台魔笔使用测评

文章目录 前言一、魔笔是什么&#xff1f;二、测评1.基本组件布局2.前端逻辑3.事件绑定 总结 前言 最近对于低代码平台挺感兴趣的&#xff0c;了解到很多云服务&#xff0c;国内有很多的这种平台&#xff0c;最近阿里云推出了他们的多端低代码开发平台魔笔&#xff0c;目前还在…
阅读更多...
qt QTextCursor详解

qt QTextCursor详解

1、概述 QTextCursor是Qt框架中用于在QTextDocument或QTextEdit中编辑和导航文本的类。它提供了对文本选择和编辑操作的低级控制&#xff0c;允许插入、删除、修改文本以及改变文本的格式。QTextCursor可以看作是一个在文本中移动的插入点或选择区域&#xff0c;通过它可以执行…
阅读更多...
uniapp实现H5和微信小程序获取当前位置（腾讯地图）

uniapp实现H5和微信小程序获取当前位置（腾讯地图）

之前的一个老项目&#xff0c;使用 uniapp 的 uni.getLocation 发现H5端定位不准确&#xff0c;比如余杭区会定位到临平区&#xff0c;根据官方文档初步判断是项目的uniapp的版本太低。 我选择的方式不是区更新uniapp的版本&#xff0c;是直接使用高德地图的api获取定位。 1.首…
阅读更多...
【深度学习】论文笔记：空间变换网络（Spatial Transformer Networks）

【深度学习】论文笔记：空间变换网络（Spatial Transformer Networks）

博主简介&#xff1a;努力学习的22级计算机科学与技术本科生一枚&#x1f338;博主主页&#xff1a; Yaoyao2024往期回顾&#xff1a; 【机器学习】有监督学习由浅入深讲解分类算法Fisher算法讲解每日一言&#x1f33c;: 今天不想跑&#xff0c;所以才去跑&#xff0c;这才是长…
阅读更多...
RK3568 关于python依赖Miniconda3虚拟环境自启动

RK3568 关于python依赖Miniconda3虚拟环境自启动

有关如何安装Miniconda3可以查看博客：RK3568 安装Miniconda3_miniconda3 aarch64 linux-CSDN博客 然后目前有个需求是需要开机自启动python脚本，但是需要依赖于虚拟环境，也就是说一起来就要打开虚拟环境并运行python脚本，一旦没有虚拟环境，python脚本就无法运行 解决办法…
阅读更多...
最新文章

Copyright @ 2022~2023