一、插入排序
(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代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - ...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
数据结构之排序算法 包含目前所有排序方法: 1 快速排序 2 冒泡排序 3 堆排序 4 希尔排序 5 直接插入排序 6 直接选择排序 7 基数排序 8 箱、桶排序 9 归并排序
希尔排序,直接插入排序,折半插入排序算法的实现,c语言实现希尔排序
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
C#算法 -- (三)希尔排序 朋友们,我最近加紧写C#的一些算法。选择排序,插入算法是我已经推出的。现推出希尔排序....希尔排序是将组分段,进行插入排序. 对想提高C#语言编程能力的朋友,我们可以互相探讨一下。
内容简介: 涵盖 - 插入排序 & - 冒泡排序 & - 选择排序 & - 希尔排序 & - 归并排序 & - 快速排序 & - 计数排序 & - 堆排序 模板与解析。 适合人群: 普及早期的萌新 OIer 们。
8.12-8.19_冒泡_选择_插入_希尔_快速_归并_基数_堆排序_排序算法Swift代码及UI演示
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort...插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序mergesort
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
快速排序 希尔排序 插入排序 折半排序算法
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...
有选择排序,冒泡排序,希尔排序,插入排序,归并排序算法