冒泡排序、插入排序、选择排序、希尔排序

排序是一个非常经典的问题,它以一定的顺序对一个数组(或一个列表)中的项进行重新排序(可以进行比较,例如整数,浮点数,字符串等)(增加,非递减,递减, 增加,词典等)。
有许多不同的排序算法,每个都有其自身的优点和局限性

引用于 https://visualgo.net/zh

1 冒泡排序

这是来自于网上搜索的一张动态图:

冒泡排序、插入排序、选择排序、希尔排序

所谓冒泡排序,一句话描述就是最大的数向上冒泡

import java.util.Arrays; //java 冒泡排序 public void bubbleSortFunction1(){ //待排序数组 int arr[]={3,44,38,5,50,48}; //记录比较次数 int count=0; //外层循环 取出每个数据 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]) { //将最大的数据放到右侧 //临时变量记录左侧大的数据 int temp=arr[j]; //将右侧小的数据赋值到左侧 arr[j]=arr[j+1]; //将临时变量保存的大的数据赋值到右侧 arr[j+1]=temp; } count++; } } System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50] System.out.println('一共比较了:'+count+'次');//一共比较了:15次 }

2 选择排序

冒泡排序、插入排序、选择排序、希尔排序

所谓选择排序,一句话描述就是找出最小的,放到最左侧

  public void selectSortFunction(){    //待排序数组    int arr[]={3,44,38,5,50,48};    //记录比较次数    int count=0;    for (int i = 0; i < arr.length-1; i++) {      int index=i;//标记第一个为待比较的数      for (int j = i+1; j < arr.length; j++) { //然后从后面遍历与第一个数比较        if (arr[j]<arr[index]) {  //如果小,就交换最小值          index=j;//保存最小元素的下标        }        count++;      }      //找到最小值后,将最小的值放到第一的位置,进行下一遍循环      int temp=arr[index];      arr[index]=arr[i];      arr[i]=temp;    }    System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50]    System.out.println('一共比较了:'+count+'次');//一共比较了:15次  }

3、插入排序

冒泡排序、插入排序、选择排序、希尔排序
public void insertSortFunction(){ //待排序数组 int arr[]={3,44,38,5,50,48}; //长度不减1,是因为要留多一个位置方便插入数 for (int i = 0; i < arr.length; i++) { //记录待插入的数 int insertValue=arr[i]; //找到待插入数的前一个数的下标 int preInsertIndex=i-1; //因为是向前插入 所以 preInsertIndex 必须大于等于0 //只有待插入数据 比 前一个数据小时 才进行位置递减 while (preInsertIndex>=0 && insertValue <arr[preInsertIndex]) { //将前一个数据向后移 arr[preInsertIndex+1]=arr[preInsertIndex]; //位置递减 preInsertIndex--; } //赋值插入的位置 arr[preInsertIndex+1]=insertValue; } System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50] }

4、希尔排序

希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序

冒泡排序、插入排序、选择排序、希尔排序

希尔排序的基本步骤,在此选择增量gap=length/2,缩小增量继续以gap = gap/2的方式。

冒泡排序、插入排序、选择排序、希尔排序
  public void shellSortFunction(){    //待排序数组    int arr[]={3,44,38,5,50,48};    //记录比较次数    int count=0;    for (int gap=arr.length / 2; gap > 0; gap = gap / 2) {      //将整个数组分为若干个子数组      for (int i = gap; i < arr.length; i++) {        //遍历各组的元素        for (int j = i - gap; j>=0; j=j-gap) {          //交换元素          if (arr[j]>arr[j+gap]) {            int temp=arr[j];            arr[j]=arr[j+gap];            arr[j+gap]=temp;          }          count++;        }      }    }    System.out.println(Arrays.toString(arr));//[3, 5, 38, 44, 48, 50]    System.out.println('一共比较了:'+count+'次');//一共比较了:18次  }
2021-05-09 原文

冒泡排序、插入排序、选择排序、希尔排序的相关文章

十种排序算法总结(冒泡、插入、选择、希尔、归并、堆、快速,计数,桶,基数)

#include<iostream> using  namespace std; void swap1( int *left,  int *right) {      int temp = ...

Python|插入排序之希尔排序

引言 希尔排序(Shell's Sort)是插入排序的一种又称"缩小增量排序",是直接插入排序算法的一种更高效的改进版本.希尔排序是非稳定排序算法. 问题描述 希尔排序是把记录按下 ...

Java排序算法(四)希尔排序2

希尔排序移步法:分组+直接插入排序组合 一.测试类SortTest import java.util.Arrays; public class SortTest { private static fi ...

PHP数据结构-插入类排序:简单插入、希尔排序

插入类排序:简单插入.希尔排序 总算进入我们的排序相关算法的学习了.相信不管是系统学习过的还是没有系统学习过算法的朋友都会听说过许多非常出名的排序算法,当然,我们今天入门的内容并不是直接先从最常见的那 ...

其它排序:简单选择、桶排序

其它排序:简单选择.桶排序 这是我们算法正式文章系列的最后一篇文章了,关于排序的知识我们学习了很多,包括常见的冒泡和快排,也学习过了不太常见的简单插入和希尔排序.既然今天这是最后一篇文章,也是排序相关 ...

希尔排序

希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本.希尔排序是非稳定排序算法.该方法因DL.Shell于1959年提出而得名. 希尔排序是把记 ...

Python | 深入希尔排序世界

引言 希尔排序(Shell Sort),是插入排序的一种又称"缩小增量排序",同时它是非稳定排序算法.该方法因 D.L.Shell 于 1959 年提出而得名. 问题描述 希尔排序 ...

「翔博精选指标」竞价排序打板排序 指标 通达信 贴图 无未来 加密不限时介绍

做价值的传播者,一路同行,一起成长 适用软件:通达信 公式说明:不包含未来函数,不加密,副图公式 指标公式描述 竞价排序打板排序 指标 通达信 贴图 无未来 加密不限时介绍 由于通达信不支持分笔全推, ...

600-70年代知青非常流行的一手歌《望故乡》老知青们听听很是凄凉7707次观看&#160;&#183;&#160;发布于&#160;05-23&#160;&#183;&#160;原创云水谣歌1184粉丝&#160;&#183;&#160;48视频关注8&#160;条评论热度排序时间排序

600-70年代知青非常流行的一手歌《望故乡》老知青们听听很是凄凉7707次观看&#160;&#183;&#160;发布于&#160;05-23&#160;&#183;&#160;原创云水谣歌1184粉丝&#160;&#183;&#160;48视频关注8&#160;条评论热度排序时间排序