论编程中常见的20种算法-CSDN博客

        🚀欢迎互三👉：WSH2012ffff 💎💎

        🚀关注博主，后期持续更新系列文章

        🚀如果有错误感谢请大家批评指出，及时修改

目录

01什么是排序？

02排序的稳定性是什么？

03内排序和外排序有什么区别？

04直接插入排序——排序思路

05直接插入排序——排序实例

06直接插入排序——排序算法

07直接插入排序——算法分析

提到排序算法，可能各位程序员们都并不陌生，在计算机科学技术和数学里，排序又称排序算法。一个排序算法（Sorting algorithm）是一种能将一串资料依照特定排序方式的一种算法。

简单的说下算法，算法（Algorithm）是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，能够得出所要求或期望的终止状态或输出数据。算法常常含有重复的步骤和一些比较或逻辑判断。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

虽然排序算法是一个简单的问题，但是从计算机科学技术发展以来，已经有大量的研究在此问题上。关于排序的分类，有稳定的、不稳定的、不实用的排序算法。今天开始，东小萌就带大家学习一下Java的八大经典排序算法！

好啦，首先我们来明确一下排序的基本概念！

01什么是排序？

所谓排序，就是整理表中的元素，使之按关键字递增或递减的顺序排列。

02排序的稳定性是什么？

当待排序元素的关键字各不相同时，排序的结果是唯一的，否则排序的结果不一定唯一。

如果待排序的表中，存在多关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是稳定的；反之，若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是不稳定的。

注意，排序算法的稳定性是针对所有输入实例而言的。也就是说，在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

03内排序和外排序有什么区别？

在排序过程中，若整个表都是放在内存中处理，排序时不涉及内、外存数据的交换，则称之为内排序；反之，若排序过程中要进行内、外存数据的交换，则称之为外排序。

内排序适用于元素个数不是很多的小表，外排序则适用于元素个数很多，不能一次将全部元素放入内存的大表。

按所用的策略不同，排序方法还可以分为需要关键字比较和不需要关键字比较两类。需要关键字比较的排序方法有插入排序。选择排序。交换排序和归并排序；不需要关键字比较的排序方法有基数排序。

▲ 排序的分类

好了，现在你已经了解了排序的基本概念，下面我们就来认识一下Java八大经典内排序算法的第一位——直接插入排序。

04直接插入排序——排序思路

假设待排序的元素存放在数组 Data[0..n-1] 中，排序过程中的某一时刻，Data 被划分成两个子区间 Data[0..i-1] 和 Data[i..n-1]（刚开始时 i=1，有序区只有 Data[0] 一个元素），其中，前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，称其为无序区。直接插入排序的一趟操作是将当前无序区的开头元素 Data[i] （1 <= i <= n-1）插入到有序区 Data[0..i-1] 中适当的位置上，使 Data[0..i] 变为新的有序区，如下图所示。这种方法通常称为增量法，因为它每趟操作使有序区增加一个元素。

▲ 直接插入排序的一趟排序过程

※说明：直接插入排序每趟产生的有序区并一定是全局有序区，也就是说有序区中的元素并不一定放在其最终的位置上。当一个元素在整个排序结束前就已经放在其最终的位置上，称为归位。

05直接插入排序——排序实例

设待排序的表有 10 个元素，其关键字为 {9,8,7,6,5,4,3,2,1,0}。以下为直接插入排序的排序过程：

▲ 直接插入排序过程

图中用方括号表示每趟操作后的有序区。每趟向有序区中插入一个元素（用方框表示），并保持有序区中的元素仍有序。

06直接插入排序——排序算法

07直接插入排序——算法分析

时间复杂度：O(n2)；

空间复杂度：O(1)；

稳定性：稳定；

复杂性：简单。