算法（Algorithm）指对解决问题方案的准确、完整的描述，是一系列解决问题的明确指令，算法代表着用系统的方法来描述解决问题的战略机制。排序算法，是如何按要求排列记录的方法。Java排序算法它在许多领域发挥着重要作用，尤其是在处理大量数据方面。众所周知，一个优秀的算法不仅可以节省大量的资源，还可以加快目标项目的进度，提高其运行速度。对于排序，我们首先要求它具有一定的稳定性，即当两个相同的元素同时出现在一个序列中时，在排序前后的相对位置不会改变。
然而，结合各领域的实际情况，考虑到数据的各种限制和规范，需要大量的推理和分析才能获得符合实际情况的优秀算法。同时，大量的数据处理和计算也是必不可少的一步。我们之所以能理解大量高质量的排序算法，是因为我们站在巨人的肩膀上，可以预见这么多优秀的算法，从而完成很多难以完成的大型程序和项目。接下来，让我们了解一下java中的八大排序算法。
一、直接插入
- 1.基本思路
假设在要排序的组数中，前面(n-1) [n>=2] 数量已经安排好了。现在我们应该将第n个数插入前面的有序数中，这样n个数也可以安排好。如此重复的循环，直到所有的顺序都安排好。
- 2.代码实现
1）每个循环从第二个数字向前插入数组
2）设置插入数和得到已经排列好的最后一个数的位数。temp和j=i-1。
3）向前循环从最后一个数开始，如果插入数小于当前数，则向后移动当前数。
public static void insertSort(int[] data) {
int temp;
for(int i = 1;i < data.length; i++){// 取第一个数字，插入前面有序的序列
temp = data[i];
int j;
for(j = i - 1; j>=0; j--) {// 比较第一个i-1的位置
if(data[j] > temp) {// 如果前面的数字很大，那就向后移动一个
data[j+1] = data[j];
} else {
break;// 否则说明要插入的数量比较大
}
}
data[j+1] = temp;// 找到这个位置，插入数据
}
}
- 3.时间复杂度和空间复杂度
直接插入排序的平均复杂度是O(n²)，最坏的时间复杂度：O(n²)，空间复杂度：O(1)未分配内存。
二、希尔排名
针对直接插入排名下的效率问题，有人对此进行了改进和升级，即现在的希尔排名。希尔排名，又称递减增量排名算法，是一种更有效的插入排名改进版本。希尔排名是一种不稳定的排名算法。
1.基本思路
1）数的个数为length，i=length将下标差值为i的数量分成一组，形成有序列。
2）再取i=i/2 ，将下标差值为i的数分成一组，形成有序列。
3）重复第二步，直到k=执行简单插入排序。
2.代码实现
1）每个循环从第二个数字向前插入数组
2）设置插入数和得到已经排列好的最后一个数的位数。temp和j=i-1。
3）向前循环从最后一个数开始，如果插入数小于当前数，则向后移动当前数。
（1)首先确定每组序列下标的间隔，循环每次所需的间隔:int i = length/2; i >0 ; i /= 2
（2)然后插入每组序列中的元素进行排序。第二组第一个插入的数字是第一组第一个插入数字后的数组。从i开始，每个数字都应该插入排序，即插入的序列是不同的序列，而不是子序列循环，而是在一个循环中 (int j=i;j
（3)直到i=0。
public static void shellSort(int[] array) {
int length = array.length;
for (int i = length / 2; i > 0; i /= 2) {///序列间隔，直到间隔为一，此时只有一个子序列
for (int j = i; j < length; j++) {///从i之后，每个数字都要插入排序，即插入的序列是不同的序列
int temp = array[j];//直接插入算法
int k;
for (k = j - i; k >= 0; k -= i) {///将每个数字插入排序到不同的序列中，直到间隔为1，只有一个序列，完全直接插入排序
if (temp < array[k]) {
array[k + i] = array[k];
} else {
break;
}
}
array[k + i] = temp;////将数字插入位置
}
}
System.out.println(Arrays.toString(array));
}
3.时间复杂度和空间复杂度
希尔排名的平均时间复杂度是O(n²)，O(1)空间复杂度 。
三、简单选择
1.基本思路
基本原理如下：对于给定的一组记录，在第一轮比较后获得最小记录，然后将记录的位置与第一个记录的位置交换；然后对不包括第一个记录以外的其他记录进行第二次比较，获得最小记录并与第二个位置记录交换；重复这个过程，直到只剩下一个比较记录。
2.代码实现
1）确定插入最小值的位置，从从0开始到最后int i = 0; i
2）将每个开始位置上的数字暂定为最小值min,数字开始后，逐个与min进行比较，然后将最小值存储在min中
3）交换最小值位置和开始位置上的数字
public static void selectSort(int[] array) {
int len = array.length;
for (int i = 0; i < len; i++) {///确定每次开始的位置
int min = array[i];////设定最小值的开始数字
int flag = i;
for (int j = i + 1; j < len; j++) {///将最小值存储在min中，从开始的数字逐个与min进行比较，然后将最小值存储在min中
if (min > array[j]) {
min = array[j];
flag = j;
}
}
if (flag != i) {
array[flag] = array[i];
array[i] = min;
}
}
System.out.println(Arrays.toString(array));
}
3.时间复杂度和空间复杂度
简单选择排序的时间复杂度是O(n²)
四、堆排序
1.基本思路
1）若array[0，…，n-1]表示完全二叉树的顺序存储模式，父母节点指针与儿童节点指针之间的内部关系如下：
任何节点指针 i：
父节点：i==0 ? null : (i-1)/2
左孩子：2*i + 1
右孩子：2*i + 2
2）堆得定义
aray[0..，n-1]只满足以下要求：(0 <= i <= (n-1)/2)
① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆；
② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆；
3）建立大顶堆
n个节点的完全二叉树aray[0，…，n-1]N-1是最后一个节点的第一个(n-1-1)/2个节点的孩子。对(n-1-1)调整子树作为根的两个节点，使子树称为堆。
对于大根堆，调整方法如下:如果【根节点关键词】小于【左右子女关键词较大者】，则交换。
然后向前依次对每个节点进行（(n-2)/2 - 1）~ 调整0根子树，看节点值是否大于左右子节点值。如果没有，交换左右子节点的较大值，交换后可能会损坏下一层堆，因此继续使用上述方法构建下一层堆，直到节点根子树构成堆。
在根节点之前，重复使用上述调整堆的方法。
4）堆叠排序(大顶堆)
①将存储在array[00..，n-1]构建n个元素的初始堆；
②如果将堆顶元素与堆底元素交换，则序列的最大值已放置在正确位置；
③数组中的array[00..，n-1]前n-1个元素再次形成大根堆，重复第一个元素②③步骤，直到堆中只剩下一个元素。
3.时间复杂度和空间复杂度
时间复杂度:建堆：o(n)，每次调整o(log n)，因此，最好、最坏、平均情况：o(n*logn);
五、冒泡排序
打个小guang起诉，搜索拼duoduo店铺： boush杂货店
物美价廉，你值得拥有
1.基本思路
一次冒泡将序列中从头到尾的所有元素进行比较，将最大元素放在最后。
将剩余序列中的所有元素再次进行两两比较，将最大元素放在最后。
重复第二步，直到只剩下一个数字。
2.代码实现
/**
* @author fupeng
* 第二版冒泡排序优化
* 第一版优化添加flag标记，直接return无数字交换，最佳时间复杂度Olag(n)
* 第二版优化，增加tempostion记录内循环最后一次交换的位置，减少内循环次数
3.时间复杂度和空间复杂度
泡沫排序的最佳时间复杂度是O(n),最坏的时间复杂度是O(n²),平均时间复杂度为O(n²),O(1)是一种稳定的排序算法，具有空间复杂性。
六、快速排序
1.基本思路
使用分治策略快速排序一个序列（list）分为两个子序列（sub-lists）。步骤为：
1）从数列中挑出一个元素，称为"基准"（pivot）。
2）重新排序数列，所有比基准值小的元素都放在基准前面，所有比基准值大的元素都放在基准后面(相同的数量可以到达任何一边)。分区结束后，基准位于数列的中间。这叫分区（partition）操作。
3）3.时间复杂度和空间复杂度
并购排序是一种稳定的排序，它也是一种非常有效的排序，可以利用完全二叉树特性的排序一般性能不会太差。java中Arrays.sort()采用了一种名为Timsort的排序算法，即合并排序的优化版本。从上图可以看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度是|log2n|。平均时间复杂度为O(nlogn)。此外，合并排名最好、最坏，平均时间复杂度为O(nlogn)。
八、基数排序
1.基本思路
1.基数排序的思想是先把你排好，然后在你的基础上排十位，以此类推，直到遍历最高位 第二，排序结束(仔细理解最后一句话)
2.基数排序不是比较排序，而是通过分配和收集的过程来实现排序
3.初始化10桶(固定)，桶下标注0-9
4.将这个数字对应的item放入相应的桶中，获得待排序数字的100等位数字。
5.基数排序有两种排序方式:LSD和MSD，最小位优先(从右)和最大位优先(从左)
2.代码实现
由于基数排序的代码实现比较复杂，可以参考网上的一些例子。
3.时间复杂度和空间复杂度
并购排序是一种稳定的排序，它也是一种非常有效的排序，可以利用完全二叉树特性的排序一般性能不会太差。java中Arrays.sort()采用了一种名为Timsort的排序算法，即合并排序的优化版本。从上图可以看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度是|log2n|。平均时间复杂度为O(nlogn)。此外，合并排名最好、最坏，平均时间复杂度为O(nlogn)。
学习了以上八种java排序算法结束后，我们很快掌握了相关的专业知识。虽然java排序算法的类型有点复杂，但这也是许多算法大师经过无数实践和推导的结果。我希望你能珍惜这个宝贵的果实，这也是我们在未来编程中解决大量算法问题的利刃。
湘公网安备43019002002060