插入排序介绍:
插入式排序属于内部排序法,是对于欲排序元素以插入的方式寻找该元素适当的位置,已达到排序的目的.
插入排序法思想:
插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序和无序表,开始时有序表只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中适当位置,使之成为新的有序表.
插入排序思路图:
?从小到大演示
插入排序应用案例：
有一群小牛，考试成绩分别是101，34，119，1，请从小到大排序
代码实现：
package sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
* 插入排序 80000个数据2s左右
*/
public class InsertSort {
public static void main(String[] args) {
// int []arr = {101,34,119,1,-1,89};
// insertSort(arr);
//创建80000个数据
int []arr =new int[80000];
for (int i=0; i<80000; i++){
arr[i]=(int)(Math.random()*80000);//生成一个【0，800000】数
}
Date date1= new Date();
SimpleDateFormat simpleDateFormat= new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str =simpleDateFormat.format(date1);
System.out.println("排序前的时间="+date1Str);
insertSort(arr);
Date date2= new Date();
String date2Str =simpleDateFormat.format(date2);
System.out.println("排序后的时间="+date2Str);
}
//插入排序
public static void insertSort(int[]arr){
int insertVal = 0;
int insertIndex = 0;
//使用for循环简化代码
for (int i = 1; i <arr.length; i++) {
//定义待插入的数
insertVal = arr[i];
insertIndex = i - 1;//即arr[1]的前面这个数的下标
//给insertVal找到插入的位置
//说明
//1.insertIndex >=0 保证在给insertVal找到插入位置,不越界
//2.insertVal< arr[insertIndex]待插入的数,还没有找到插入位置
//3.就需要将arr[insertIndex]后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//当推出while循环时,说明插入的位置找到,insertIndex +1
//这里我们判断是否需要赋值
if (insertIndex + 1== i){
arr[insertIndex + 1] = insertVal;
}
// System.out.println("第"+i+"轮插入");
//System.out.println(Arrays.toString(arr));
}
/* //第二轮
insertVal = arr[2];
insertIndex = 2 - 1;//即arr[1]的前面这个数的下标
//给insertVal找到插入的位置
//说明
//1.insertIndex >=0 保证在给insertVal找到插入位置,不越界
//2.insertVal< arr[insertIndex]待插入的数,还没有找到插入位置
//3.就需要将arr[insertIndex]后移
while(insertIndex >=0 && insertVal < arr[insertIndex]){
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//当推出while循环时,说明插入的位置找到,insertIndex +1
arr[insertIndex + 1] = insertVal;
System.out.println("第二轮插入");
System.out.println(Arrays.toString(arr));
//第三轮
insertVal = arr[3];
insertIndex = 3 - 1;//即arr[1]的前面这个数的下标
//给insertVal找到插入的位置
//说明
//1.insertIndex >=0 保证在给insertVal找到插入位置,不越界
//2.insertVal< arr[insertIndex]待插入的数,还没有找到插入位置
//3.就需要将arr[insertIndex]后移
while(insertIndex >=0 && insertVal < arr[insertIndex]){
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//当推出while循环时,说明插入的位置找到,insertIndex +1
arr[insertIndex + 1] = insertVal;
System.out.println("第三轮插入");
System.out.println(Arrays.toString(arr));
*/
}
}
希尔排序
希尔排序法介绍
? ? ? ? 希尔排序是希尔(DonaldShell)于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进后的一个更高效的版本，也称为缩小增量排序。
希尔排序法基本思想
? ? ? ? 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
希尔排序法的示意图
经过上面的“宏观调控”，整个数组的有序化成果喜人
此时，仅仅需要对以上数列简单微调，无需大量移动操作即可完成整个数组的排序。
希尔排序法应用实例：
有一群小牛，考试成绩分别是{8，9，1，7，2，3，5，4，6，0}请从小到大排序，请分别使用
（1）希尔排序时，对有序序列在插入时采用交换法，并测试排序速度
（2）希尔排序时，对有序序列在插入时采用移动法，并测试排序速度
代码实现
package sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
* 希尔排序
* 交换法30s左右
* 移位法1s左右
*/
public class ShellSort {
public static void main(String[] args) {
//int[] arr = {8,9,1,7,2,3,5,4,6,0};
//shellSort(arr);
//创建80000个数据
int []arr =new int[80000];
for (int i=0; i<80000; i++){
arr[i]=(int)(Math.random()*80000);//生成一个【0，800000】数
}
Date date1= new Date();
SimpleDateFormat simpleDateFormat= new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str =simpleDateFormat.format(date1);
System.out.println("排序前的时间="+date1Str);
shelSort2(arr);
Date date2= new Date();
String date2Str =simpleDateFormat.format(date2);
System.out.println("排序后的时间="+date2Str);
}
//使用逐步推导的方式来编写希尔排序
//希尔排序时，对有序序列在插入时采用交换法 30s
//思路（算法）===》代码
public static void shellSort(int[] arr) {
int temp = 0;
int count = 0;
//根据前面的逐步分析，使用循环处理
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
//遍历各组中所有的元素（共gap组，每组一2个元素），步长gap
for (int j = i - gap; j >= 0; j -= gap) {
//如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
// System.out.println("希尔排序第"+(++count)+"轮="+ Arrays.toString(arr));
}
}
/* //希尔排序的第一轮排序
//因为第一轮排序，是将10个数据分成5组
for (int i = 5; i < arr.length; i++){
//遍历各组中所有的元素（共5组，每组一2个元素），步长5
for (int j = i - 5; j >=0; j -= 5){
//如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + 5]){
temp = arr[j];
arr[j] = arr[j + 5];
arr[j + 5] = temp;
}
}
}
System.out.println("希尔排序第一轮="+ Arrays.toString(arr));
//希尔排序的第二轮排序
//因为第二轮排序，是将10个数据分成5/2=2组
for (int i = 2; i < arr.length; i++){
//遍历各组中所有的元素（共5组，每组一2个元素），步长5
for (int j = i - 2; j >=0; j -= 2){
//如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + 2]){
temp = arr[j];
arr[j] = arr[j + 2];
arr[j + 2] = temp;
}
}
}
System.out.println("希尔排序第二轮="+ Arrays.toString(arr));
//希尔排序的第三轮排序
//因为第三轮排序，是将10个数据分成2/2=1组
for (int i = 1; i < arr.length; i++){
//遍历各组中所有的元素（共5组，每组一2个元素），步长5
for (int j = i - 1; j >=0; j -= 1){
//如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + 1]){
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println("希尔排序第三轮="+ Arrays.toString(arr));
*/
//对交换式的希尔排序进行优化-》位移法 1s不到
public static void shelSort2(int[] arr){
int j = 0;
int temp = 0;
//增量gap，并逐步的缩小增量
for (int gap = arr.length / 2; gap >0 ; gap /= 2) {
for (int i = gap; i < arr.length; i++){
j = i;
temp = arr [j];
if (arr[j] < arr[j - gap]){
while (j - gap >=0 && temp < arr[j -gap]){
//移动
arr[j] = arr[j -gap];
j -=gap;
}
//当推出while后，就给temp找到插入的位置
arr[j] = temp;
}
}
}
}
}