一、插入排序
(1)、主要思路:
- 假设数组分为两部分,有序部分【0~i-1】,无序部分【i~N】。初始有序部分只有一个元素。
- 从有序部分【0~i-1】中找到一个值小于(或大于)数组【i】的位置,即为将要排序的数据
- 把数组【i】插入到适当的位置,其他的数据往后转移
(2)、代码实现:
public void sort(int[] arr) { for(int i=1;i<arr.length;i++){ int insertValue = arr[i]; int j; for(j=i-1;j>=0;j--){//1.从arr[i-1]~arr[0]数组之间,找到一个位置 if(insertValue > arr[j]){ break; } } //2.如果j==i-1,说明不需要调换,恰好处于排序的位置 if(j==i-1){ continue; } //3.找到一个恰好的位置 for(int k =i-1;k>j;k--){ arr[k+1] = arr[k]; } arr[j+1] = insertValue; } }
二、希尔排序
希尔排序是对插入排序的一种改进算法,是一种分组插入排序,又称为缩小增量排序法。
希尔排序的时间复杂度与增量(即,步长gap)的选取有关。例如,当增量为1时,希尔排序退化成了直接插入排序,此时的时间复杂度为O(N²),而Hibbard增量(N/2)的希尔排序的时间复杂度为O(N3/2)。
- 对一个数组长度为N的数组,取一个小于N的整数gap(gap称为步长)
- 根据该步长将数组分为若干个子数组,所有距离为gap的倍数的记录放在同一个子数组
- 对每个子数组进行插入排序
- 然后缩减gap的值,并重复上面的分组和排序
- 当gap==1时,整个数组就是有序的
下面以数列{80,30,60,40,20,10,50,70}为例,演示它的希尔排序过程。
第1趟:(gap=4)
当gap=4时,意味着将数列分为4个组: {80,20},{30,10},{60,50},{40,70}。 对应数列: {80,30,60,40,20,10,50,70}
对这4个组分别进行排序,排序结果: {20,80},{10,30},{50,60},{40,70}。 对应数列: {20,10,50,40,80,30,60,70}
第2趟:(gap=2)
当gap=2时,意味着将数列分为2个组:{20,50,80,60}, {10,40,30,70}。 对应数列: {20,10,50,40,80,30,60,70}
注意:{20,50,80,60}实际上有两个有序的数列{20,80}和{50,60}组成。
{10,40,30,70}实际上有两个有序的数列{10,30}和{40,70}组成。
对这2个组分别进行排序,排序结果:{20,50,60,80}, {10,30,40,70}。 对应数列: {20,10,50,30,60,40,80,70}
第3趟:(gap=1)
当gap=1时,意味着将数列分为1个组:{20,10,50,30,60,40,80,70}
注意:{20,10,50,30,60,40,80,70}实际上有两个有序的数列{20,50,60,80}和{10,30,40,70}组成。
对这1个组分别进行排序,排序结果:{10,20,30,40,50,60,70,80}
(3)、代码实现
public void sort(int[] arr) { // gap为步长,每次减为原来的一半。 for (int gap = arr.length / 2; gap > 0; gap /= 2) { // 共gap个组,对每一组都执行直接插入排序 for (int i = 0; i < gap; i++) { group_sort(arr, arr.length, i, gap); } } } private void group_sort(int arr[], int n, int i, int gap) { for (int j = i + gap; j < n; j += gap) { // 如果a[j] < a[j-gap],则寻找a[j]位置,并将后面数据的位置都后移。 if (arr[j] < arr[j - gap]) { int tmp = arr[j]; int k = j - gap; while (k >= 0 && arr[k] > tmp) { arr[k + gap] = arr[k]; k -= gap; } arr[k + gap] = tmp; } } }
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
同时,插入排序也可以用于构建更复杂的排序算法,如希尔排序。 **源码和工具**: 标签中的"源码"指的是上述给出的`InsertionSort.java`文件,这个文件包含了插入排序的Java实现。"工具"可能是指开发环境中使用的...
本资源提供了七大经典排序算法的实现程序,包括快速排序、冒泡排序、选择排序、归并排序、插入排序、希尔排序和堆排序。下面将逐一详细介绍这些排序算法及其原理。 1. 快速排序:由C.A.R. Hoare提出,是一种采用...
本话题主要探讨六种内部排序算法:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序以及堆排序。这六种排序算法各有优劣,适用于不同的场景,接下来我们将逐一进行详细阐述。 1. **直接插入排序**: 直接...
在给定的标题和描述中,我们关注四种经典的排序算法:快速排序、希尔排序、插入排序和折半排序。这些算法各有特点,适用于不同的场景,下面将详细介绍它们的工作原理、性能以及应用场景。 1. **快速排序(Quick ...
本篇文章将深入探讨标题和描述中提到的九大排序算法:快速排序、冒泡排序、堆排序、希尔排序、直接插入排序、直接选择排序、基数排序、箱排序和桶排序。 1. **快速排序**:快速排序是一种基于分治策略的排序算法,...
插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序...
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
4. 希尔排序(Shell Sort):希尔排序是插入排序的一种优化版本,通过间隔序列(也称为增量序列)减少元素间的比较距离,从而提高效率。其平均时间复杂度介于O(n)到O(n^2)之间。 5. 快速排序(Quick Sort):快速...
经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - ...
本文将深入探讨标题和描述中提到的一些基本排序算法,包括选择排序、冒泡排序、插入排序、希尔排序、堆排序、快速排序以及归并排序,并结合C++编程语言进行讲解。 1. **选择排序(Selection Sort)** - 选择排序是一...
综上所述,希尔排序、直接插入排序和折半插入排序都是常见的排序算法。它们各有特点,适用于不同场景下的数据排序需求。希尔排序通过增加子序列的插入排序来提高效率;直接插入排序简单直观,但效率较低;而折半插入...
【希尔排序】希尔排序是一种基于插入排序的快速排序算法,由希尔(Hoare)提出。它的主要思想是将待排序的元素按照一定的间隔分组,然后对每组进行插入排序,随着间隔逐渐减小,最后当间隔为1时,整个序列就是一个有序...
希尔排序的时间复杂度为 O(n^2),但实际上它的性能比插入排序要好得多,特别是在大型列表上。希尔排序的性能取决于间隔序列的选择,但是目前还没有一种最优的间隔序列。 在 Java 中,希尔排序可以使用以下代码实现...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的元素按照一定的间隔分组,对每组进行插入排序,然后逐渐减小间隔,直到间隔为1,此时整个序列视为...
- **稳定性**:直接插入排序是稳定的排序算法,而希尔排序则不是。 - **适用场景**:对于较小的数据量或者部分有序的数据,直接插入排序可能更高效;而对于大数据量或无序数据,希尔排序更为适合。 通过上述实验,...
根据提供的文件信息,我们可以深入探讨几种经典的排序算法:冒泡排序、直接插入排序、快速排序以及希尔排序。这些算法在数据结构与算法课程中是非常重要的基础内容,它们各自有着独特的特性和应用场景。 ### 1. ...
排序算法汇总(选择排序、直接插入排序、冒泡排序、希尔排序、快速排序、堆排序) 本资源介绍了六种常用的排序算法:选择排序、直接插入排序、冒泡排序、希尔排序、快速排序和堆排序。下面对每种算法进行详细介绍:...