首页 > 其他分享 >排序 （插入/选择排序）

排序 （插入/选择排序）

时间：2024-11-03 21:45:01浏览次数：3  
标签：arr end int 插入排序 选择 插入 排序 复杂度

目录

一 . 排序概念及运用

1.1 排序的概念

1.2 排序的应用

1.3 常见的排序算法

二 . 插入排序

2.1 直接插入排序

2.1 复杂度分析

 2.3 希尔排序

 2.4 希尔排序时间复杂度分析

三 . 选择排序

3.1 直接选择排序

3.2 堆排序

一 . 排序概念及运用

1.1 排序的概念

排序 : 所谓排序 ， 就是使一条记录 ， 按照其中的某个或某些关键字的大小，递增 或 递减的排序起来的操作 。 

1.2 排序的应用

排序在生活中无处不在 ， 如果没有排序 ， 那么许多业务也不会实现

1 . 院校排名

2 .  购物筛选排序

1.3 常见的排序算法

二 . 插入排序

 基本思想 :

直接插入排序是一种简单的插入排序算法 ， 其基本思想是 : 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中 ， 直到所有记录插入完为止 ， 得到一个新的有序序列 。 

 在实际生活中 ， 玩扑克牌就使用了   插入排序   的思想 !

2.1 直接插入排序

插入排序是在已经有序序列中 ， 插入新的数据 ， 形成一个新的有序序列

直接插入排序 ， 需要一个变量来存储需要插入的数据(tmp) , 另一个变量初始为有序序列的最后一个位置 (end)， arr[end] 与 tmp 比较 ， 谁大谁往后排 。 

 这里我们依旧创建三个文件 ， 方便文件的管理 ， 使用一个test.c 文件也是可以实现的。

test.c

#include "Sort.h"

void PrintArr(int* arr,int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void test()
{
	int a[] = { 5,3,9,6,2,4,7,1,8 };
	int n = sizeof(a) / sizeof(a[0]);
	printf("排序之前:");
	PrintArr(a, n);

	InsertSort(a, n);
	printf("排序之后:");
	PrintArr(a, n);
}
int main()
{
	test();
	return 0;
}

Sort.c

#include "Sort.h"

//直接插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

Sort.h 

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

//直接插入排序
void InsertSort(int* arr, int n);

2.1 复杂度分析

直接插入排序的特性总结 :

1 . 元素集合越接近有序 ， 直接插入排序算法时间的效率越高

2 . 时间复杂度 : O ( n^2)

3 . 空间复杂度 : O （1）

 

对比之前学过的 冒泡排序 ， 堆排序 堆排序和TOP-K问题-CSDN博客

1 .  冒泡排序时间复杂度为 O(n^2) 

2 .  堆排序时间复杂度为 O (n * log n)

3 . 直接插入排序时间复杂度为 O（n^2)

在冒泡排序中 ， 如果序列本身为有序 ， 时间复杂度最优 O(n) ； 在直接插入排序中 ， 如果序列为有序 ， 且为降序 ， 时间复杂度最差 O (n^2) , 但这种情况的出现概率很小 ，在一定程度上可以说 ， 直接插入排序的时间复杂度达不到 O(n^2) , 但也没比冒泡排序好了多少 。 

以下测试以下三个方法运行时所需的时间 ， 单位为毫秒

 从上面的测试结果我们可以得出 ， 堆排序的算法  时间复杂度相较于  冒泡排序  和  直接插入排序的更优一些  

test.c

#include "Sort.h"
#include <time.h>
#include <stdlib.h>

void PrintArr(int* arr,int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void test()
{
	int a[] = { 5,3,9,6,2,4,7,1,8 };
	int n = sizeof(a) / sizeof(a[0]);
	printf("排序之前:");
	PrintArr(a, n);

	//InsertSort(a, n);
	//BubbleSort(a, n);
	HeapSort(a, n);

	printf("排序之后:");
	PrintArr(a, n);
}

// 测试排序的性能对⽐
void TestOP()
 {
	srand(time(0));
	const int N = 100000;
	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);
	
}


int main()
{
	//test();
	TestOP();
	return 0;
}

Sort.c

#include "Sort.h"

//直接插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

void Swap(int* x,int*y )
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//冒泡排序
void BubbleSort(int* arr, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		int exchange = 0;
		for (int j = 0; j < size - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1]) {
				exchange = 1;
				Swap(&arr[j], &arr[j + 1]);
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}

//向下调整
void AdjustDown(int* arr, int parent, int n)
{

	int child = parent * 2 + 1;
	while (child < n)
	{
		//先找最小孩子
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}

}

//堆排序
void HeapSort(int* arr, int n)
{
	//向下调整算法建堆
	for (int i = n - 1 - 1; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[end], &arr[0]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

//直接插入排序
void InsertSort(int* arr, int n);

//冒泡排序
void BubbleSort(int* arr, int size);

//堆排序
void HeapSort(int* arr, int n);

 2.3 希尔排序

在数组为降序时 ， 直接插入排序的时间复杂度为 O（n^2) ,  那么可以优化吗 ？

-------> 可以 ， 将数组划分成多组来进行直接插入排序，降低时间复杂度

希尔排序法又称缩小增量法 。

希尔排序法的基本思想是 :  选定一个整数 ( 通常是gap = n/3 + 1 ) , 把待排序文件所有记录分成各组 ， 所有的距离相等的记录分在同一组内 ， 并对每一组内的记录进行排序 ，

然后gap = gap / 3 +1 得到下一个整数 ， 再将数组分成各组 ， 进行插入排序 ， 当 gap = 1 时 ， 就相当于直接插入排序 。

它是在直接插入排序算法的基础上进行改进而来的 ， 综合来说它的效率肯定是要高于直接插入排序算法的 。

思考 :

1 ) 为什么要分组 ？

 通过分组来降低元素之间的比较次数，优化时间复杂度

2 ) 怎么分组 ?

通过间隔 gap (gap / 3 + 1 ) 的元素  组成一组

3 ）为什么要 +1 , 不直接 gap/3 ?

假设gap = 3 , gap/3 = 0 , 此时数据还没有排序好 就终止了排序 , 希望是当gap == 1  时 ， 预排序结束 ， 然后进行直接插入排序 。

4 ) 可以gap/2 , gap/8 吗？

可以 ， 视情况而论 ， 一般是 gap/3 , 因为除小了 ， 分组过多就过多 ； 除大了 ， 比较次数就多了

//希尔排序
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 tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

 2.4 希尔排序时间复杂度分析

希尔排序时间复杂度不好计算。因为 gap 的取值很多 ，导致很难去计算 ， 因此很多书中给出的希尔排序的时间复杂度后不固定 。 《数据结构 （C语言版）》 -- 严蔚敏书中给出的时间复杂度为 

 这里我们大致记住 ， 希尔排序的时间复杂度比直接插入排序更优 ，并且大致上为 O（n^1.3)  ， 下面是大致对希尔排序的时间复杂度进行估算 :

外层循环 : ： O(\log_{2}n) 或者 O(\log_{3}n) ，即 O(log n)

内层循环 : 

 

 通过以上分析 ， 可以画得如下曲线图 : 

 因此 ， 希尔排序在最初和最后的排序的次数都为 n ， 即前一阶段排序次数是逐渐上升的状态 ， 当达到某顶点时 ， 排序次数逐渐下降至 n ,  而该顶点的计算暂时无法给出具体的计算过程 。 

 单位为毫秒 ， 通过性能的测试 ， 我们发现 ， 希尔排序的运行速度 很近似于   堆排序 ， 相较于直接插入排序 是一个 较优的算法 ！

三 . 选择排序

 选择排序的基本思想 : 

每一次从待排序的数据元素中选出最小（或最大）的一个元素 ， 存放在序列的起始位置 ，直到全部待排序的数据元素排完 。  

3.1 直接选择排序

//直接选择排序
void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;

		//找最大最小
		for (int i = begin + 1; i <= end; i++)
		{	
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}

		//如果maxi == began
		if (maxi == begin)
		{
			maxi = mini;
		}

		Swap(&arr[mini], &arr[begin]);
		Swap(&arr[maxi], &arr[end]);
		begin++;
		end--;
	}
}

 直接选择排序的思路比较好理解，但是 效率不是很高 ， 实际中 很少使用

1 ） 时间复杂度 : O( n ^ 2 )

2 )   空间复杂度 : O ( 1 )

3.2 堆排序

堆排序(HeapSort) 是利用堆 这种数据结构所设计的一种排序算法 ， 他是选择排序的一种 。 它是通过堆来进行选择数据 。 需要注意的是 排升序要建大堆 ， 排降序建小堆 。 

之前的文章详细介绍了堆排序 ， 这里不再赘述 

堆排序和TOP-K问题-CSDN博客

标签：arr,end,int,插入排序,选择,插入,排序,复杂度
From： https://blog.csdn.net/khjjjgd/article/details/143441409

相关文章

  • 选择性必修1 化学反应原理 小记
    可能是易错升高温度时\(v_{\text{正}}\)和\(v_{\text{逆}}\)均增大。稀释酸时，并不是所有的离子浓度均减小：\(\mathrm{OH^-}\)。图表的浓度/其他数据可能不止指一个量。多检查一下pH比大小的方向。连上双键的能量不要用成连上单键的能量。绝热过程指的是不与外界进行热......
  • 定时任务频繁插入数据导致锁表问题 -＞ 查询mysql进程
    场景定时任务每10秒插入一批数据，由于过去频繁导致锁表，从而无法再插入数据解决方案具体查看博客：https://blog.csdn.net/weberhuangxingbo/article/details/88709556数据库中执行sql：SELECT*FROMinformation_schema.innodb_trxSELECT*FROMinformation_schema.innodb_lo......
  • mysql编写sql脚本：要求表没有主键，但是想查询没有相同值的时候才进行插入
    @目录背景说明背景说明我这里主要针对2处地方要进行增量执行sql：1.新功能需要创建一张新表结构indicator_alarm_threshold2.给菜单表和另一个表新增数据我们现在使用的是项目启动先初始化加载init-table.sql的脚本(这里面的轻易不动了，保持原结构数据)，然后还有个用于后续迭......
  • 【算法-选择排序】挑挑拣拣，排出顺序——选择排序入门
    什么是选择排序？选择排序是一种比较简单直接的排序方式。想象你在打散一副牌，想按照大小顺序从小到大排列这些牌。你会怎么做？可能会先找出最小的那张，放在最前面，然后在剩下的牌里找第二小的，依次类推，这就是选择排序的基本思路！在程序中，选择排序的操作流程也类似：它逐步将未排序......
  • 算法-图论-拓扑排序
    1.拓扑排序（卡码网117）fromcollectionsimportdeque,defaultdictdefmain():num_node,num_edge=map(int,input().split())inDegrees=[0for_inrange(num_node)]edges=defaultdict(list)for_inrange(num_edge):source,target=......
  • 【LeetCode:153. 寻找旋转排序数组中的最小值 + 二分】
    在这里插入代码片......
  • HarmonyOS NEXT开发实战教程：选择相册和拍照
    今天的内容是介绍在鸿蒙开发中从相册选择照片，和调用相机拍照，并使用这两个功能实现朋友圈编辑页面。  这部分内容没什么好废话的，都是固定用法，直接上代码。首先添加权限：ohos.permission.CAMERAohos.permission.READ_IMAGEVIDEO选择相册：​asyncgetAlbum(){co......
  • 美团面试：Mysql如何选择最优 执行计划，为什么？
    文章很长，且持续更新，建议收藏起来，慢慢读！疯狂创客圈总目录博客园版为您奉上珍贵的学习资源：免费赠送:《尼恩Java面试宝典》持续更新+史上最全+面试必备2000页+面试必备+大厂必备+涨薪必备免费赠送:《尼恩技术圣经+高并发系列PDF》，帮你实现技术自由，完成职业升级，薪......
  • 本科阶段讲个透（全）|保研/推免（流程、时间、前期必要的准备、心得感悟）、考试学习（思政类、
    文章目录一、前言二、保研/推免2.1保研流程2.2保研的前期准备2.3保研心得2.4如何择校三、考试学习（学习方法、学习时间、记忆方法、各科的学习大致规划）四、科研竞赛（途径、队友、机会）五、志愿六、社会工作七、就业7.1为什么考虑就业7.1明白自己具体做什么7.2招聘看......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99