首页 > 其他分享 >希尔排序:优化的插入排序

希尔排序:优化的插入排序

时间:2023-09-19 21:31:35浏览次数:49  
标签:arr int 插入排序 gap 希尔 排序 间隔

希尔排序(Shell Sort)是一种插入排序的改进算法,它通过比较相距一定间隔的元素进行排序,逐步减小间隔,最终实现整体有序。本文将详细介绍希尔排序的工作原理,提供示例和Python、Go、Java以及C语言的实现代码。

希尔排序的基本思想

希尔排序的核心思想是将整个待排序序列分割成若干个子序列,分别对这些子序列进行插入排序,然后逐步减小子序列的间隔,直到间隔为1,最终对整个序列进行一次插入排序。这样,插入排序的效率会得到大幅提升。

具体步骤如下:

  1. 确定间隔序列: 选择一个间隔序列,一般是逐步减半,直到间隔为1。
  2. 间隔排序: 对间隔序列所对应的子序列进行插入排序。
  3. 逐步缩小间隔: 重复第二步,逐步减小间隔,直到间隔为1,完成最终的插入排序。

希尔排序的示例

让我们通过一个示例来理解希尔排序的工作原理。假设我们有一个整数数组 [12, 34, 54, 2, 3],我们希望按升序排序它。

  1. 选择间隔序列: 假设我们选择间隔序列为 [2, 1]
  2. 间隔为2的排序: 分别对间隔为2的子序列进行插入排序。
第一轮:[12, 3]  [34, 2]  [54]
  1. 间隔为1的排序: 对整个序列进行一次插入排序。
第二轮:[3, 2, 12, 34, 54]

最终,我们得到了排序后的数组 [2, 3, 12, 34, 54]

希尔排序的时间复杂度

希尔排序的时间复杂度取决于间隔序列的选择。一般来说,间隔序列的选择直接影响到希尔排序的性能。

  1. 最好情况时间复杂度: O(n log n)
  2. 平均情况时间复杂度: 取决于间隔序列
  3. 最坏情况时间复杂度: O(n^2)

希尔排序是一种不稳定的排序算法,适用于中等大小的数据集。它是插入排序的改进版本,通过减小元素移动的距离来提高排序效率。

示例代码

以下是希尔排序的示例代码,分别使用Python、Go、Java和C语言编写。

Python 希尔排序

def shell_sort(arr):
    n = len(arr)
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

arr = [12, 34, 54, 2, 3]
shell_sort(arr)
print("排序后的数组:", arr)

Go 希尔排序

package main

import "fmt"

func shellSort(arr []int) {
	n := len(arr)
	gap := n / 2

	for gap > 0 {
		for i := gap; i < n; i++ {
			temp := arr[i]
			j := i

			for j >= gap && arr[j-gap] > temp {
				arr[j] = arr[j-gap]
				j -= gap
			}

			arr[j] = temp
		}

		gap /= 2
	}
}

func main() {
	arr := []int{12, 34, 54, 2, 3}
	shellSort(arr)
	fmt.Println("排序后的数组:", arr)
}

Java 希尔排序

import java.util.Arrays;

public class ShellSort {
    public static void shellSort(int arr[]) {
        int n = arr.length;
        int gap = n / 2;

        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;

                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }

                arr[j] = temp;
            }

            gap /= 2;
        }
    }

    public static void main(String[] args) {
        int arr[] = {12, 34, 54, 2, 3};
        shellSort(arr);
        System.out.print("排序后的数组: ");
        System.out.println(Arrays.toString(arr));
    }
}

C 语言 希尔排序

#include <stdio.h>

void shellSort(int arr[], int n) {
    int gap = n / 2;

    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;

            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }

            arr[j] = temp;
        }

        gap /= 2;
    }
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    shellSort(arr, n);
    printf("排序后的数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

以上示例代码展示了不同编程语言中的希尔排序算法实现。这些示例帮助你理解希尔排序的工作原理,并提供了可供参考和使用的代码示例。希尔排序是一种高效的排序算法,可以在大多数情况下获得不错的性能。


标签:arr,int,插入排序,gap,希尔,排序,间隔
From: https://blog.51cto.com/u_16170163/7529430

相关文章

  • Python实现排序的方式有:内置函数sort()和sorted()以及lambda函数
    排序是计算机编程中经常需要用到的操作,它将一组数据按照规则重新排列,以便更好地处理数据。在Python中,有多种方法可以对数组进行排序,本文将从多个方面进行介绍。一、Python中的排序方法Python中内置了多个排序算法,包括冒泡排序、插入排序、选择排序、快速排序等。使用内置的sort(......
  • 快速排序算法
    快速排序1.快速排序的思想快速排序是一种分治的排序算法,是对于冒泡排序的改进算法,在C语言标准库中的函数qsort()的实现就是快速排序。(下述快速排序都是最后要求值按从小到大排序)快速排序的核心思想在于:每次都选择主元,然后利用主元进行划分,使得左边的元素都小于主元,右边的元素......
  • NFLS-NOIP模拟 排序
    题面Link小Z是一位热爱优化算法的同学。一天他在研究归并排序,并想到,如果在归并排序的过程中提前return,对正确率的影响并不会很大。于是他写了如下部分代码:voidmerge_arr(intl,intmid,intr)//此函数表示将S[1,mid],S[mid+1,r]两个有序序列合并成为一个大的有序序列S[l,r],......
  • sql server单一某列实现排序____附件数据表
    USE[YJ]GO/******Object:Table[dbo].[T_OA_WDSTORE]ScriptDate:04/16/201400:23:38******/SETANSI_NULLSONGOSETQUOTED_IDENTIFIERONGOSETANSI_PADDINGONGOCREATETABLE[dbo].[T_OA_WDSTORE]( [WDBH][nvarchar](50)NOTNULL, [APPBH][nvarc......
  • DRF之排序类源码分析
    【一】排序类介绍在DjangoRESTframework(DRF)中,排序类用于处理API端点的排序操作,允许客户端请求按特定字段对数据进行升序或降序排序。排序类是一种特殊的过滤类DRF提供了内置的排序类,并且你也可以自定义排序类以满足特定的需求。【二】内置排序类OrderingFilterrest_f......
  • 堆排序
    时间复杂度为O(n)voidheapify(vector<int>&nums,intn,inti){intlargest=i;//假设为父节点intlson=i*2+1;intrson=i*2+2;//找到最大值if(lson<n&&nums[lson]>nums[largest])swap(nums[lson],nums[largest]);if(rson<......
  • sql server单一某列实现排序
    WDBHAPPBHWDMC430175500443659sg430044033903992转发省环境保护厅省财政厅关于印发广东省排污权有偿使用和交易试点管理办法的通知(会签文)(修改).doc430175500443659430044033903992转发省环境保护厅省财政厅关于印发广东省排污权有偿使用和交易试点管理办法的通知(会签文).doc......
  • map-key 排序对比
    publicstaticMap<String,List<TPricePpiBaseWeight>>sortMapByKey(Map<String,List<TPricePpiBaseWeight>>map){if(map==null||map.isEmpty()){returnnull;}Map<String,List<TPricePpi......
  • listview排序
    intWINAPICustomSortProc(LPARAMItem1,LPARAMItem2,LPARAMParamSort){staticboolb=true;if(b){b=false;return-CompareText(((TListItem*)Item1)->Caption,((TListItem*)Item2)->Caption);}......
  • [MAUI]实现动态拖拽排序列表
    @目录创建页面元素创建可绑定对象创建绑定服务类拖拽(Drag)拖拽悬停,经过(DragOver)释放(Drop)限流(Throttle)和防抖(Debounce)项目地址上一章我们使用拖放(drag-drop)手势识别实现了可拖拽排序列表,对于列表中的条目,完整的拖拽排序过程是:手指触碰条目->拖拽条目->拖拽悬停在另一个......