高级程序员的生存之道：希尔排序的各类程序代码

拼搏现实的明天。 2022-01-27 00:25 186阅读 0赞

下面来简单介绍一下希尔排序的各类程序代码，具体如下所示：

### 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 ###

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

*  插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
 *  但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

### 算法步骤如下： ###

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

## 各类代码实现： ##

### JavaScript ###

### 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) {
                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;
        }
    }

### PHP ###

### C ###

void shell_sort(int arr[], int len) {
            int gap, i, j;
            int temp;
            for (gap = len >> 1; gap > 0; gap >>= 1)
                    for (i = gap; i < len; i++) {
                            temp = arr[i];
                            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                                    arr[j + gap] = arr[j];
                            arr[j + gap] = temp;
                    }
    }

### C++ ###

template<typename T>
    void shell_sort(T array[], int length) {
        int h = 1;
        while (h < length / 3) {
            h = 3 * h + 1;
        }
        while (h >= 1) {
            for (int i = h; i < length; i++) {
                for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                    std::swap(array[j], array[j - h]);
                }
            }
            h = h / 3;
        }
    }