认知算法(十)

简介: 认知算法(十),一起来学习吧。

嗨,欢迎来到异星球,我是小怪同志。这篇文章主要讲认识算法,请一起学习吧。

一、希尔排序

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

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

插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;
希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。

  1. 算法步骤
    1.选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;

    2.按增量序列个数 k,对序列进行 k 趟排序;

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

二、代码实现

1.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;
            }

}
2.c++
template
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;
}

}

相关文章
|
6月前
|
安全 测试技术
认识-认知
认识-认知
101 0
|
Kubernetes 负载均衡 网络协议
K8S 的新认知与初领会
我们今天开始正式进⼊ Kubernetes 的课程学习,Kubernetes 相信各位已经听过很多次了,那么什么是 Kubernetes呢?
K8S 的新认知与初领会
|
存储 算法 搜索推荐
认知算法(三)
认知算法(三),一起来学习吧。
认知算法(三)
|
机器学习/深度学习 存储 算法
认知算法(四)
认知算法(四),一起来学习吧。
认知算法(二)
认知算法(二),一起来学习吧。
|
算法 搜索推荐 大数据
认知算法(八)
认知算法(八),一起来学习吧。
|
算法 搜索推荐 索引
认知算法(七)
认知算法(七),一起来学习吧。
|
存储 算法 搜索推荐
认知算法(六)
认知算法(六),一起来学习吧。
|
算法 搜索推荐
认知算法(五)
认知算法(五),一起来学习吧。
|
算法 JavaScript 前端开发
认知算法(九)
认知算法(九),一起来学习吧。