电子类网站模板,网站建设技术课程设计,在线编辑图片加字,公司内部网站建设目录
排序的概念
插入排序
直接插入排序
哈希排序 排序的概念
排序#xff1a;所谓的排序#xff0c;就是使一串记录#xff0c;按照某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。
稳定性#xff1a;假定在待排序的记录序列中#xff0c;存在多个…目录
排序的概念
插入排序
直接插入排序
哈希排序 排序的概念
排序所谓的排序就是使一串记录按照某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳 定的否则称为不稳定的。 常见的排序算法有下面四种 插入排序直接插入排序希尔排序选择排序选择排序堆排序交换排序冒泡排序快速排序归并排序归并排序 这里主要介绍Java如何实现插入排序中的直接排序和希尔排序。
插入排序
基本思想把待排序的记录按照其关键码值的大小逐个插入到一个已经拍好的有序序列中直到所有的记录插入完为止得到一个新的有序序列。生活中的例子就像我们在完扑克牌的时候机型排序一样。
直接插入排序
思路
直接插入排序的过程就像是有一组无序数据用第二个元素先和第一个元素比较如果第一个元素比第二个元素大那么二者就交换位置否则继续往后推随着往后推每一次前一个元素都要不断和之前排序过的元素进行比较。 Sort类
public class Sort {/*** 时间复杂度O(N^2)* 空间复杂度O(1)* 稳定性稳定的排序* param array*///直接插入排序public static void insertSort(int[] arr){for (int i 1; i arr.length; i) {int tmp arr[i];int j i-1;for (; j 0; j--) {if(arr[j] tmp){arr[j1] arr[j];}else{arr[j1] tmp;break;}}//确保j位置的数也就是前一个数能换位成功arr[j1] tmp;}}
}
Test类 测试类
public class Test {public static void main(String[] args) {int[] arr {12,6,59,45,73,26,2};System.out.println(排序前 Arrays.toString(arr));Sort.insertSort(arr);System.out.println(排序前 Arrays.toString(arr));}
}输出结果为 关于i1且i arr.length思路因为数组是从0开始的所以arr[6]的位置刚好是最后一位。
通过上面的动图我们不难发现如果数组一开始越有序直接插入排序的效率越高这也为下面的哈希排序提供了思路。
稳定性
直接插入排序是稳定的由上面图片能看到它是具有稳定性的但如果是代码部分的 arr[j] tmp 改为arr[j] tmp以上面的2a和2b为例它们的顺序就会发生变化。那么这还能说直接插入排序是稳定的吗
当然能因为 本身是一个稳定的排序那么可以实现为不稳定的。
但是如果一个排序 本身是不稳定的那就不能实现稳定的排序。 哈希排序
哈希排序可以看作是直接插入排序的优化先通过 gap来不断简化 其中的有序性然后再用直接插入排序越有序直接插入排序的时间复杂度越小速度越快。 通过间隔分为不同的组组内进行排序然后再缩短gap来进行再次排序。
代码为
public static void shellInsert(int[] array){int gap array.length;while(gap 1){gap / 2;shell(array, gap);}
}private static void shell(int[] array, int gap) {for (int i gap; i array.length; i) {int tmp array[i];int j i-gap;for (; j 0; j- gap) {if(array[j] tmp){array[jgap] array[j];}else{array[jgap] tmp;break;}}array[jgap] tmp;}
}
到这里插入排序中的直接插入排序和希尔排序就结束了接下来我会继续给出剩下排序的思路和代码。
