希尔排序算法(代码实现)
这里我们将要讲的是位移式的希尔排序算法
- 因为我们的交换式的希尔排序算法效率很低,并且我们的交换式的希尔排序算法几乎是不会用的,所以我们就不对交换式的希尔排序进行实现了
- 交换式的希尔排序算法的效率要比直接插入排序的效率还要低很多,我们之前在希尔排序算法是思路分析中关于希尔排序的提出背景中讲到过: 我们的希尔排序就是为了优化我们的直接插入排序而提出的,所以我们的希尔排序算法的执行效率应该一定是要比直接插入排序的效率要高的,但是我们交换式的希尔排序算法的效率甚至是要比直接插入排序算法还要慢的多,那么我们为什么要使用交换式的直接插入排序? --> 我们的交换式的希尔排序在我们的数组是完全逆序的情况之下的执行效率几乎和我们的冒泡排序的效率是一样的
希尔排序其实是很容易理解的,这里我们就不一步一步进行推导了,这个时候我们直接给出我们归纳好的希尔排序的算法(以方法的形式):
- 这个希尔排序算法中insertIndex变量表示的是待插入位置
/*
这里我们直接给出我们归纳好的希尔排序的算法
这个希尔排序算法中insertIndex表示的是待插入元素的位置
*/
public static void shellSort(int arr []){
/*
我们将要进行使用的临时变量先定义在循环之外:
我们的希尔排序中要定义的变量和我们的直接插入排序中定义的变量是一样的,因为我们的希尔排序就是在分组的基础上进行了一个直接插入排序
*/
int insertValue = 0;
int insertIndex = 0;
//注意: 我们的希尔排序是要有三层循环组成的,这里我们先给出我们的最外层循环
//这个最外层循环是用于分组的,我们分组的次数就是通过最外层循环控制的
/*
这个时候我们定义的gap变量就是表示我们希尔排序中的增量,增量其实也就等于分的组的个数,我们的增量是在length/2之间的,包括
length/2和1,所以这个时候我们判断分组退出的条件就是当我们的gap(增量) = 0,这个时候等于0就会退出,那么我们就要让这个循环
的判断条件为gap>0,这个时候如果gap=0的时候就会退出循环了
关于增量值的变化我们每次都是让增量的值gap/2
*/
for (int gap = arr.length/2; gap > 0; gap = gap/2){
//从第gap+1个元素开始逐个设为待插入元素进行判断
//第gap +1 个元素其实就是第一组中的第二个元素
for (int i = gap; i < arr.length; i++) {
insertValue = arr[i];
insertIndex = i;
//这里arr[insertValue](待插入元素)一定是和带插入位置的前一个位置进行比较
while(insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]){
arr[insertIndex] = arr[insertIndex - gap];
//insertIndex前移: 注意: 希尔排序中是前移gap位
insertIndex -= gap;
}
arr[insertIndex] = insertValue;
}
}
}
下面我们再给出一个希尔排序算法:
- 这个希尔排序中insertIndex表示的是待插入的位置的前一个位置
/*
我们这里再来编写一个希尔排序算法
这个希尔排序算法中我们的insertIndex表示待插入位置的上一个位置(和我们前面写过的直接插入排序一样)
*/
public static void shellSort2(int [] arr){
int insertVal = 0;
int insertIndex = 0;
//最外层for循环控制分组次数
for(int gap = arr.length/2; gap>0; gap /= 2){
/*
遍历待插入元素,对所有的待插入元素进行指定值 , 直接插入排序中待插入元素是从数组中的第二个元素开始的,也就是从索引为1的元素处
而待插入元素应该是从第一组元素中的第二个元素开始,也就是从索引为 0 + gap的索引位置的元素开始
*/
for(int i = gap; i< arr.length;i++){
//给临时变量赋值
insertVal = arr[i];
insertIndex = i - gap;
//判断待插入元素的位置
while(insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex + gap] = arr[insertIndex];
insertIndex -= gap;
}
arr[insertIndex + gap] = insertVal;
}
}
}
我们是将希尔排序算法写到了一个自定义工具类ArraySort类中,这里我们就将ArraySort类给出:
package com.ffyc.util;
import java.awt.*;
import java.util.Arrays;
/**
* 数组排序的一个工具类(内部封装了很多排序的方法(八种内部排序都封装在里面))
*/
public class ArraySort {
/**
* 一步一步对冒泡排序的推演
*/
public static void bubbleSort(){
//定义了一个长度为5的数组
//对于这个长度为5的数组我们进行冒泡排序要进行排序4趟
int arr[] = {3,9,-1,10};
/*
第一趟排序,也就是将最大的数排到最后的位置
*/
//定义一个临时变量,用于两个位置的数值进行交换时使用
int temp = 0;
/*
在第一趟中我们要执行数组长度减-1次
*/
for (int j = 0; j < arr.length - 1 - 0; j++) {
//如果前面的数比后面的数大,则交换位置
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
//显示第一趟排序之后的结果
System.out.println("第一趟排序之后: ");
System.out.println(Arrays.toString(arr));
/*
第二趟排序,也即是将第二大的元素排到倒数第二个位置上
*/
//这里就不用重复的定义一个临时变量了
//注意: 由于我们第一趟中已经将我们的数组中的最后一个位置排好了,这个时候第二趟排序我们只需要排序除过最后一个元素的其他位置的元素就可以了
for(int j = 0; j < arr.length - 1 - 1; j++){
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
//显示第二趟排序之后的结果
System.out.println("第二趟排序之后: ");
System.out.println(Arrays.toString(arr));
/*
第三趟排序: 将第三大的数排到数组中倒数第三个位置上
*/
for(int j = 0; j < arr.length - 1 - 2; j++){
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
//显示第三趟的排序结果
System.out.println("第三趟的排序结果: ");
System.out.println(Arrays.toString(arr));
}
/**
* 将冒泡排序归纳为一个双层for循环
*/
public static void bubbleSort(int [] arr){
//定义一个临时变量用于我们对两个位置上的元素的值进行交换
int temp = 0;
//定义外层for循环,控制冒泡排序执行的趟数
for (int i = 0; i < arr.length - 1; i++) {
//定义内存for循环,控制冒泡排序每趟执行的次数
for (int j = 0; j < arr.length - 1 -i; j++) {
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
// System.out.println("第"+(i+1)+"趟冒泡排序的结果是");
// System.out.println(Arrays.toString(arr));
}
}
/**
* 冒泡排序算法的优化
* 如果在某趟冒泡排序中没有执行一次元素交换,那么就提前退出冒泡排序
* 因为说明在上一次就排好序了,那么这一次才能一次元素交换都不发生
*/
public static void bubbleSortPlus(int [] arr){
//定义一个临时变量用于交换两个位置的元素
int temp = 0;
//定义一个标识变量来判断我们的某一趟排序中是否一次交换位置的操作都没有发生
boolean flag = false;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 -i; j++) {
if(arr[j] > arr[j+1]){
flag = true;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if(!flag){ // 表示flag的值为false,表示在一趟排序中一次元素的交换都没有发生过
break;
}else{
flag = false; // 重置flag的值 ---> 这一点很重要
}
}
}
/*
选择排序
一步一步进行思路分析
*/
public static void selectSort(){
//这里我们是对选择排序算法的一个思路分析,所以我们直接创建一个原始的数组进行操作
int [] arr = {101,34,119,1};
/*
第一轮选择排序
*/
int minIndex = 0;
int min = arr[0];
for (int j = 0 + 1; j < arr.length; j++) {
if(min > arr[j]){ //说明假定的最小值并不是最小的
//重新指定最小值
min = arr[j];
//重新指定最小值索引位置
minIndex = j;
}
}
//判断我们的最小值查询出来的位置是否就是在最小值应该出现的位置
if(minIndex == 0) {
//查询出来的最小值的位置就是在最小值应该出现的位置
}else{
//查询出来的最小值的位置不是在应该出现的位置,那么就要进行交换
arr[minIndex] = arr[0];
arr[0] = min;
}
System.out.println("第一趟排序完成: ");
System.out.println(Arrays.toString(arr));
/*
第二轮选择排序
*/
minIndex = 1;
min = arr[1];
for (int j = 1 + 1; j < arr.length; j++) {
if(min > arr[j]){
min = arr[j];
minIndex = j;
}
}
if(minIndex == 1){
}else{
arr[minIndex] = arr[1];
arr[1] = min;
}
System.out.println("第二轮排序完成: ");
System.out.println(Arrays.toString(arr));
/*
第三轮选择排序
*/
minIndex = 2;
min = arr[2];
for(int j = 2 + 1; j < arr.length; j++){
if(min > arr[j]){
min = arr[j];
minIndex = j;
}
}
if(minIndex == 2){
}else{
arr[minIndex] = arr[2];
arr[2] = min;
}
System.out.println("第二轮排序完成");
System.out.println(Arrays.toString(arr));
}
//将选择排序汇总成由两个for循环构成的算法
public static void selectSort(int [] arr){
//记录最小值的大小和最小值位置的索引,为了后面可以进行交换
//我们的选择排序就是每次判断出一个待排序队列中的最小值,然后让这个最小值和最小值应该出现的位置上的值进行一个交换
int min = 0;
int minIndex = 0;
/*
我们的选择排序中执行的趟数为: 数组长度减一趟
*/
/*
注意: 这里的外层for循环的循环控制变量i就是我们的每次查询出来的最小值元素应该插入(存在)的位置
*/
for (int i = 0; i < arr.length - 1; i++) {
min = arr[i];
minIndex = i;
/*
这里注意: 我们每次都是选择出一个最小值 , 但是这个时候的最小值其实只是我们每次待排序元素中的最小值,每次选出一个最小值,放在前面
*/
for (int j = i + 1; j < arr.length; j++) {
//判断我们的当前索引是否是指向了最小值元素,如果不是则修改当前最小值的索引位置和数值
if(min > arr[j]){
minIndex = j;
min = arr[j];
}
}
/*
判断我们查询到的最小值位置是否就是最小值应该存在的位置,如果不是则交换位置,如果是则就不用交换位置
*/
if(minIndex == i){
break;
}else{
arr[minIndex] = arr[i];
arr[i] = min;
}
//显示每趟排序的结果
// System.out.println("第"+(i+1)+"趟排序的结果: ");
// System.out.println(Arrays.toString(arr));
}
}
/*
这里我们来一步一步推到着实现插入排序算法
我们先来一步一步的推到方便与我们去理解
*/
public static void insertSort() {
//我们先创建一个待排序数组
int[] arr = {101, 34, 119, 1};
/*
我们这里就开始第一轮的排序的实现
*/
//将无序表中的第一个元素认为是待插入元素
int insertVal = arr[1];
//将有序表中的最后一个元素的位置暂时记录为我们的待插入位置
//注意: 我们的这个算法设计中这里的待插入位置其实指的是待插入位置的前一个位置
int insertIndex = 0;
//判断我们的待插入位置是否是合法位置,如果不是就要退出循环
//如果我们的待插入元素的值比较小,这个时候我们就要进行有序表中对应元素的后移和待插入索引位置的前移
while(insertIndex >= 0 && insertVal < arr[insertIndex]){
//有序表中对应元素后移,后移之后不用担心会让我们的待插入元素失效,因为我们的待插入元素其实已经被我们保存到了一个临时变量insertVal中了
arr[insertIndex + 1] = arr[insertIndex];
//带插入索引位置前移
insertIndex--;
}
//如果推出到while循环的外面,那么就是说明我们的待插入位置找到了,这个时候我们就要将我们的待插入元素插入到我们的待插入位置的后一个位置上
arr[insertIndex + 1] = insertVal;
System.out.println("第一轮插入排序之后: ");
System.out.println(Arrays.toString(arr));
/*
这我们开始第二轮插入排序的实现
*/
insertVal = arr[2];
insertIndex = 2 - 1;
while(insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = insertVal;
System.out.println("第二轮插入排序后的结果为: ");
System.out.println(Arrays.toString(arr));
/*
第三轮选插入排序
*/
insertVal = arr[3];
insertIndex = 3 - 1;
while(insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = insertVal;
System.out.println("第三轮排序之后结果为: ");
System.out.println(Arrays.toString(arr));
}
/*
这里我们将上面一步一步推导的插入排序的算法归纳为一个for循环加上一个while循环
*/
public static void insertSort(int [] arr){
//注意: 如果for循环中有变量的声明和赋值操作同时执行的情况,这个时候我们就要将变量的定义放到我们的循环之外来以提升效率
//定义我们的待插入的值,先初始化为0,正真的复制操作会在外层for循环之中进行
int insertVal = 0;
//定义我们的待插入的位置,也是先初始化为0,正真的赋值操作会在外层循环之中进行
int insertIndex = 0;
//外层循环,我们可以发现我们的插入排序也是执行待排序数组长度-1次
/*
这个时候注意:我们之前讲过的冒泡排序和我们的选择排序都是从第一个位置开始去操作,但是这个时候我们的插入排序是从待排序数组中的第二个位置开始执行的
*/
for (int i = 1; i < arr.length; i++) {
//给待插入元素值变量赋值
insertVal = arr[i];
//给待插入位置索引变量赋值
insertIndex = i - 1;
//内层while循环
while(insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//将我们的待插入元素插入到待插入位置上
arr[insertIndex + 1] = insertVal;
}
}
/*
这里我们直接给出我们归纳好的希尔排序的算法
这个希尔排序算法中insertIndex表示的是待插入元素的位置
*/
public static void shellSort(int arr []){
/*
我们将要进行使用的临时变量先定义在循环之外:
我们的希尔排序中要定义的变量和我们的直接插入排序中定义的变量是一样的,因为我们的希尔排序就是在分组的基础上进行了一个直接插入排序
*/
int insertValue = 0;
int insertIndex = 0;
//注意: 我们的希尔排序是要有三层循环组成的,这里我们先给出我们的最外层循环
//这个最外层循环是用于分组的,我们分组的次数就是通过最外层循环控制的
/*
这个时候我们定义的gap变量就是表示我们希尔排序中的增量,增量其实也就等于分的组的个数,我们的增量是在length/2之间的,包括
length/2和1,所以这个时候我们判断分组退出的条件就是当我们的gap(增量) = 0,这个时候等于0就会退出,那么我们就要让这个循环
的判断条件为gap>0,这个时候如果gap=0的时候就会退出循环了
关于增量值的变化我们每次都是让增量的值gap/2
*/
for (int gap = arr.length/2; gap > 0; gap = gap/2){
//从第gap+1个元素开始逐个设为待插入元素进行判断
//第gap +1 个元素其实就是第一组中的第二个元素
for (int i = gap; i < arr.length; i++) {
insertValue = arr[i];
insertIndex = i;
//这里arr[insertValue](待插入元素)一定是和带插入位置的前一个位置进行比较
while(insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]){
arr[insertIndex] = arr[insertIndex - gap];
//insertIndex前移: 注意: 希尔排序中是前移gap位
insertIndex -= gap;
}
arr[insertIndex] = insertValue;
}
}
}
/*
我们这里再来编写一个希尔排序算法
这个希尔排序算法中我们的insertIndex表示待插入位置的上一个位置(和我们前面写过的直接插入排序一样)
*/
public static void shellSort2(int [] arr){
int insertVal = 0;
int insertIndex = 0;
//最外层for循环控制分组次数
for(int gap = arr.length/2; gap>0; gap /= 2){
/*
遍历待插入元素,对所有的待插入元素进行指定值 , 直接插入排序中待插入元素是从数组中的第二个元素开始的,也就是从索引为1的元素处
而待插入元素应该是从第一组元素中的第二个元素开始,也就是从索引为 0 + gap的索引位置的元素开始
*/
for(int i = gap; i< arr.length;i++){
//给临时变量赋值
insertVal = arr[i];
insertIndex = i - gap;
//判断待插入元素的位置
while(insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex + gap] = arr[insertIndex];
insertIndex -= gap;
}
arr[insertIndex + gap] = insertVal;
}
}
}
}
- 这里我们可以发现我们的ArraySort类中还封装了一些其他的排序算法 , 一共有:: 冒泡排序 , 选择排序, 插入排序, 希尔排序
这里我们来对我们的希尔排序做一个测试: (测试代码如下:)
//对我们归纳后的希尔排序的测试(此算法中insertIndex表示的是待插入位置)
@Test
public void test8(){
//创建一个待排序数组
int arr [] = {101,34,119,1};
System.out.println("排序前的数组为: ");
System.out.println(Arrays.toString(arr));
//调用希尔排序算法:
ArraySort.shellSort(arr);
System.out.println("排序后的数组为: ");
System.out.println(Arrays.toString(arr));
}
//对我们归纳后的希尔排序的测试(此算法中insertIndex表示的是待插入位置的前一个位置)
@Test
public void test9(){
//创建一个待排序数组
int arr [] = {101,34,119,1};
System.out.println("排序前的数组为: ");
System.out.println(Arrays.toString(arr));
//调用我们的希尔排序算法
ArraySort.shellSort2(arr);
System.out.println("排序后的数组为: ");
System.out.println(Arrays.toString(arr));
}