首页 / 知识

Java数据结构，常见排序详解

2023-04-11 16:19:00

　　一、排序的概念和分类

　　1.排序的基本概念

　　排序是将一批无序的记录（数据）重新排列成按关键字有序的记录序列的过程。

　　排序分为内部排序和外部排序

　　若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

　　反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

　　内部排序的过程是一个逐步扩大记录的有序序列长度的过程

　　2.排序的稳定性

　　假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

　　总结起来就是，如果一个数据在排序过程中发生了跳跃行为，则为不稳定的排序；反之，则是稳定的排序。

　　时间复杂度：一个算法执行所耗费的时间

　　空间复杂度：运行完一个程序所需的内存大小。

　　二、常见排序

　　1.直接插入排序

　　直接插入排序的基本操作是讲一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

　　代码：

　　public static void insertSort（int[] array） {

　　for （int i = 1; i < array.length; i++） {

　　int tmp = array[i];

　　int j = i-1;

　　for （; j >= 0 ; j--） {

　　if（array[j] > tmp） {

　　array[j+1] = array[j];

　　}else {

　　break;

　　}

　　//j回退到了小于0的地方

　　array[j+1] = tmp;

　　}