首页 > 其他分享 >【CPP】插入排序、希尔排序

【CPP】插入排序、希尔排序

时间:2024-06-22 20:29:35浏览次数:22  
标签:clock int 插入排序 a1 CPP 排序 复杂度

目录

1.插入排序

基本思想:把一个待排数字按照关键码值插入到一个有序序列中,得到一个新的有序序列。

1.1直接插入排序

简介

直接插入排序即是直接把一个待排数字插入一个有序序列的这种插入排序方法。

这类似于打牌时插排的情况:
在这里插入图片描述

请添加图片描述

我们写直接插入排序应该先写好单趟插入排序再写完整体的插入排序。

代码

我们假设要排升序。
且假设[0,end]有序,让end+1的数字插入到有序序列当中。

单趟插入排序:
直接插入排序的单趟存在下面两种情况:
在这里插入图片描述
每个数的插入:
在这里插入图片描述

完整插入排序:
我们由单趟直接插入排序扩展到多趟的插入排序。
在这里插入图片描述

问:数组位置0处可以存数据个数吗?
特殊情况下可以,但是不建议。
在这里插入图片描述

分析

最坏情况:O(N^2)
最好情况:O(N)

结论:直接插入排序适合基本有序的序列排序,不适合逆序排序。
插入排序在基本有序的情况下,时间复杂度接近O(N),因而直接插入排序比较适合于基本有序的序列排序。
但是,一旦碰到逆序的序列,时间复杂度直接到了O(N^2)。

1.2直接插入对比冒泡排序

与直接插入排序相似思路的是冒泡排序

简介

略。
在这里插入图片描述

代码

在这里插入图片描述

对比分析(直接插入排序与冒泡的复杂度效率区别)

最好的时间复杂度:O(N)
最差的时间复杂度:O(N^2)
冒泡排序与直接插入排序是一个量级的。但是仍然还有一些细微区别:

void TestOP()
{
	srand(time(0));
	const int N = 10000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	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();
		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();
	//SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	//HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	//QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	//MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	bubbleSort(a7, N);
	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("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("BubbleSort:%d\n", end7 - begin7);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}

在这里插入图片描述

为什么会造成这种差异呢?
原因在于,冒泡排序每次单趟一定走n-1-i次(假设这是第i趟排序)。
但是,直接插入排序每次单趟一定小于或者等于走n-1-i次(假设这是第i趟排序),只有逆序情况下才与冒泡等价。

1.3希尔排序

简介

希尔排序就是先进行预排序,再进行排序的插入排序。

  • 预排序(让序列接近有序)
  • 直接插入排序

代码

在这里插入图片描述

在这里插入图片描述

分析

希尔排序时间复杂度是O(N^1.3)


EOF

标签:clock,int,插入排序,a1,CPP,排序,复杂度
From: https://blog.csdn.net/2302_79031646/article/details/139772051

相关文章

  • python 快速排序
     快速排序快速排序是一种非常高效的排序算法,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 以下是一个使用Python实现的快速排序的示例代码: pythond......
  • 如何用GO语言实现快速排序算法?
    本章教程,介绍一下如何用GO语言实现基础排序算法中的快速排序。快速排序(Quicksort)是一种高效的排序算法,它采用分治法策略,将一个数组分成两个子数组,然后递归地对这两个子数组进行排序。一、程序代码packagemainimport( "fmt" "math/rand" "time")//quickSo......
  • MySQL-文件排序原理详解
    目录Usingfilesort文件排序原理详解filesort文件排序方式示例验证下各种排序方式:单路排序的详细过程:双路排序的详细过程:单路排序相对于双路排序具有以下特点:Usingfilesort文件排序原理详解filesort文件排序方式单路排序:是一次性取出满足条件行的所有字段,然后在s......
  • 使用MPI 实现奇偶排序
    使用MPI实现奇偶排序0号进程获得待排序序列并输出排序好的序列使用文件进行输入输出进行性能测试与对比代码奇偶排序头文件引入#include<iostream>#include<algorithm>#include<mpi.h>#include<fstream>#include<chrono>定义规模#defineN100000000......
  • Python 冒泡排序
    冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。以下是一个用Python实现的冒泡排序算法的例子:pythondefbubble_sort(lst):n=len......
  • 随机链表的复制 && 排序链表
    随机链表的复制题目.-力扣(LeetCode)思路:思路:       ①一个结点一个节点去拷贝,当拷贝了第一个节点的时候,把原节点与拷贝节点连接起来,直接到所有的节点拷贝完毕,这样做的目的是为下一步处理random指针做准备      ②处理random       ③处理......
  • 手撕排序2--选择排序(直接选择+堆排序
    目录:1.直接选择排序  的实现及分析2.堆排序的实现及分析1.直接选择排序1.1基本思想:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。1.2一次排序-->将最大值放在第一个,最小值放在最后一个代码实现:#incl......
  • 校招常见七大排序C++版(适合新人,通俗易懂)
    作者:求一个demo版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处内容通俗易懂,没有废话,文章最后是面试常问内容是否稳定最优、最坏、平均时间复杂度最优、最坏、平均空间复杂度冒泡排序是O(n)、O(n^2)、O(n^2)0、O(n)、O(1)选择排序否O(n^2)、O(n^2)......
  • CPP知识 typedef
    typedef本身是typedefine(类型定义)的缩写。typedef为c语言的关键字,作用是为一种数据类型(基本类型或自定义数据类型)定义一个新名字,不能创建新类型。与define不同,typedef仅限于数据类型,而不是表达式或具体的值。define发生在预处理,typedef发生在编译阶段。点击查看代码st......
  • P8500 [NOI2022] 冒泡排序 题解
    考虑特殊性质B。限制相当于钦定一些位置的值,其他位置无限制。可以发现性质:无限制的位置上填的值是单调不减的。证明:设得到的最优序列为\(A\),对于无限制的位置\(i,j\),若\(A_i>A_j\),交换\(i,j\)后逆序对个数必然减小。根据改性质,只需考虑每个位置对已经确定位置的位置的贡......