Java实现插入排序,希尔排序和归并排序
作者：程序小猿2 发布时间：2022-02-24 18:45:52
标签：Java,插入,希尔,排序,归并,排序
插入排序
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
算法步骤
1.将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2.从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
动图演示
JavaScript代码实现
function insertionsort(arr){
var len = arr.length;
var preIndex,current;
for(var i = 1;i < len;i++){
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current){
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
Python代码实现
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
Go代码实现
func insertionSort(arr []int)[]int{
for i := range arr {
preIndex := i - 1
current := arr[i]
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex -= 1
}
arr[preIndex+1] = current
}
return arr
}
Java代码实现
public class InsertSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
//对arr进行拷贝，不改变参数内容
int[] arr = Array.copyOf(sourceArray,sourceArray.length);
//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for(int i = 1;i < arr.length;i++{
//记录要插入的数据
int temp = arr[i];
//从已经排序的序列最右边开始比较，找到比其小的数
int j = i;
while(j > 0 && temp < arr[j - 1] {
arr[j] = arr[j-1];
j--;
}
//存在比其小的数，插入
if(j != i){
arr[j] = temp;
}
}
return arr;
}
}
希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
算法步骤
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
JavaScript代码实现
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap =gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
python代码实现
def shellSort(arr):
import math
gap=1
while(gap < len(arr)/3):
gap = gap*3+1
while gap > 0:
for i in range(gap,len(arr)):
temp = arr[i]
j = i-gap
while j >=0 and arr[j] > temp:
arr[j+gap]=arr[j]
j-=gap
arr[j+gap] = temp
gap = math.floor(gap/3)
return arr
}
Go代码实现
func shellSort(arr []int) []int {
length := len(arr)
gap := 1
for gap < gap/3 {
gap = gap*3 + 1
}
for gap > 0 {
for i := gap; i < length; i++ {
temp := arr[i]
j := i - gap
for j >= 0 && arr[j] > temp {
arr[j+gap] = arr[j]
j -= gap
}
arr[j+gap] = temp
}
gap = gap / 3
}
return arr
}
Java代码实现
public class ShellSort implements IArraySort{
@Override
public int[] sort(int[] sourceArray) throws Exception{
//对arr进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
int gap = 1;
while(gap < arr.length/3){
gap = gap * 3 = 1;
}
while(gap > 0){
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
gap = (int) Math.floor(gap / 3);
}
return arr;
}
}
归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代；
在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。
说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
算法步骤
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4.重复步骤 3 直到某一指针达到序列尾；
5.将另一序列剩下的所有元素直接复制到合并序列尾。
动图演示
JavaScript代码实现
function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
python代码实现
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result
Go代码实现
func mergeSort(arr []int) []int {
length := len(arr)
if length < 2 {
return arr
}
middle := length / 2
left := arr[0:middle]
right := arr[middle:]
return merge(mergeSort(left), mergeSort(right))
}
func merge(left []int, right []int) []int {
var result []int
for len(left) != 0 && len(right) != 0 {
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1:]
} else {
result = append(result, right[0])
right = right[1:]
}
}
for len(left) != 0 {
result = append(result, left[0])
left = left[1:]
}
for len(right) != 0 {
result = append(result, right[0])
right = right[1:]
}
return result
}
Java代码实现
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}
来源：https://juejin.cn/post/7178125182362452029
0
投稿猜你喜欢
一、this关键字this是一个引用，它指向自身的这个对象。看内存分析图：假设我们在堆内存new了一个对象，在这个对象里面你想象着他有一个引- 在进行一个表达式的计算时，先将表达式分割成数字和字符串然后利用出入栈将分割后的表达式进行中缀转后缀，再将后缀表达式进行计算得到结果(思想在上
- 添加jar包这里的Scala不是maven工程所以要找到项目结构（快捷键：同时按住Ctrl+shift+Alt+s）在模块里面添加添加MyS
- 问题的起源在项目里，有时候需要实现一个图片轮播的效果，用来展示Banner。同时，图片能循环播放，下面还有一排小圆点来指示当前轮播到哪一页了
- 这篇文章主要介绍了JAVA实现账户取款和存款操作,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以
- 打开首页，明显看到链接是https打头，https和http的通信协议差别，在于https安全性更高：http和https的差别很明显，二者
- 本文实例讲述了winform导出dataviewgrid数据为excel的方法。分享给大家供大家参考。具体实现方法如下：#region 导出
- 本文实例为大家分享了shader实现基于世界坐标的贴图置换效果。效果如下：设置面板如下：可在面板上设置切换方向，与切换对象，及其切换速度。s
- 目录一 、递归算法简介二 、Fibonacci数列和阶乘1、 Fibonacci数列2、阶乘三 、汉诺塔问题 四 、排列组合1、输
- OpenCv提供了函数 findContours()用于对物体轮廓进行检测，该函数实现算法是由S.suzuki K.Abe于1985年发表的
- 1. 前言Spring的核心技术IOC(Intorol of Converse控制反转)的实现途径是DI(dependency Insert
- 看到当上面的对话框弹出时，可以使用命令查看顶层的活动窗口adb shell dumpsys window | findstr mCurren
- 本文实例讲述了如何计算(或者说，估算)一个Java对象占用的内存数量的方法。分享给大家供大家参考。具体分析如下：通常，我们谈论的堆内存使用的
- 本文给大家介绍Activity的生命周期，如果大家学习过iOS的小伙伴的话，Activity的生命周期和iOS中ViewController
- 本文实例讲述了Java二维数组。分享给大家供大家参考，具体如下：一 点睛1 每行的元素个数不同的二维数组Java定义二维数组更加灵活，允许二
- Java-关键字：final1 .final可以用来修饰的结构：类、方法、变量2.final 用来修饰一个类:此类不能被其他类所继承比如：S
- 话不多说，请看下面//C# 代码int year = DateTime.Now.Year;int month = DateTime.Now.
- 一、前言在学习分治算法之前，问你一个问题，相信大家小时候都有存钱罐的经历，父母亲人如果给钱都会往自己的宝藏中存钱，我们每隔一段时间都会清点清
- 析构函数用于析构类的实例。备注不能在结构中定义析构函数。只能对类使用析构函数。一个类只能有一个析构函数。无法继承或重载析构函数。无法调用析构
- 自定义封装 banner 组件，供大家参考，具体内容如下1. 效果图预览 2.基本功能一个简单方便的轮播图组件，基于viewpag
