希尔排序算法cyuyan

希尔排序（Shell Sort）是插入排序的一种改进算法。其基本思想是：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

具体实现：
1.选择一个增量序列 t1，t2，……，tk，其中 ti > tj，tk = 1；
2.按增量序列个数 k，对序列进行 k 趟排序；
3.每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

Python 实现代码如下：

def shellSort(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]
shellSort(arr)
print(arr)

输出结果为：[2, 3, 12, 34, 54]

相关问题

希尔排序算法C语言完整代码

以下是希尔排序算法的C语言完整代码：

#include <stdio.h>

void ShellSort(int* arr, int size) {
    int gap, i, j, temp;
    
    // 设置初始增量
    for (gap = size / 2; gap > 0; gap /= 2) {
        // 对每个增量进行插入排序
        for (i = gap; i < size; i++) {
            temp = arr[i];
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];            }
            arr[j] = temp;
        }
    }
}

int main() {
    int arr[] = {9, 5, 1, 8, 3, 7, 4, 6, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    ShellSort(arr, size);
    
    printf("排序后的数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

希尔排序的C语言算法

以下是希尔排序的C语言算法：

void ShellSort(int* arr, int flag) {
    int tap = flag; //设置排序每组的增量
    while (tap > 1) {
        tap = tap / 2; //（每次每组的增量）
        for (int i = 0; i < flag - tap; i++)//一组一个轮流排
        {
            int end = i;
            int label = arr[end + tap];
            while (end >= 0) {
                if (label < arr[end]) {
                    arr[end + tap] = arr[end];
                    end -= tap;
                } else {
                    break;
                }
            }
            arr[end + tap] = label;
        }
    }
}

希尔排序是一种高效的排序算法，它是插入排序的改进版。它通过将待排序的数组分成若干个子序列，对每个子序列进行插入排序，从而达到排序整个数组的目的。希尔排序的时间复杂度为O(nlogn)，比插入排序的时间复杂度O(n^2)要快得多。