美文网首页
04-希尔排序(python,oc)

04-希尔排序(python,oc)

作者: Young_Blood | 来源:发表于2017-09-11 11:21 被阅读8次

简述:引入gap概念,分块进行插入排序。gap会根据要求递减,当 gap == 1 等于1时,为基本的插入排序。

  • 最优时间复杂度:根据步长序列的不同而不同
  • 最坏时间复杂度:O(n2)
  • 稳定型:不稳定

python3

# coding: utf-8

def shell_sort(alist):
    """希尔排序"""
    n = len(alist)
    gap = n // 2

    while gap > 0:
        for j in range(gap,n):
            i = j
            while i > 0:
                if j >= gap and alist[i] < alist[i - gap]:
                    alist[i], alist[i - gap] = alist[i - gap], alist[i]
                    i -= gap
                else:
                    break
        gap //= 2

if __name__ == "__main__":
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(li)
    shell_sort(li)
    print(li)
/**
 希尔算法
 */
- (void)shell_sort:(NSMutableArray *)arr {
    
    NSInteger gap = arr.count / 2;
    
    while (gap >= 1) {
        for (NSInteger i = gap; i < arr.count; i++) {
            NSInteger j = i;
            while (j > 0) {
                if (j >= gap && arr[j] < arr[j - gap]) {
                    NSNumber *temp = arr[j];
                    arr[j] = arr[j - gap];
                    arr[j - gap] = temp;
                    j -= gap;
                } else {
                    break;
                }
            }
        }
        // 缩短步长
        gap = gap / 2;
    }
}

相关文章

  • 04-希尔排序(python,oc)

    简述:引入gap概念,分块进行插入排序。gap会根据要求递减,当 gap == 1 等于1时,为基本的插入排序。 ...

  • 算法04-棋牌游戏常用排序算法

    算法04-棋牌游戏常用排序算法 一、介绍 棋牌游戏常用排序算法包括:链式基数排序、插入排序、希尔排序。 二、链式基...

  • Python排序算法有哪几种?

    python排序算法有哪些?python中常见的排序算法有:插入排序、选择排序、冒泡排序、快速排序、归并排序、希尔...

  • OC版-快速排序,希尔排序

    1.快速排序 1.从序列中选择一个轴点元素(pivot),假设每次选择0位置的元素为轴点元素, 2.利用pivot...

  • 七大排序算法的 Python

    本文用Python实现了插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序。 1、插...

  • 八大排序算法的 Python 实现(转)

    本文用Python实现了插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序。 1、插...

  • Python实现程序员必备之排序算法汇总

    本文用Python实现了快速排序、插入排序、希尔排序、归并排序、堆排序、选择排序、冒泡排序共7种排序算法。 一、快...

  • Python 实现七大排序算法

    本文用 Python 实现了插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序。 先整体看一下...

  • 希尔排序算法-OC实现

    简介 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Incre...

  • 10个常见的排序算法总结

    10个常见的排序(冒泡,插入,快速,归并,堆,希尔,计数,桶,基数,选择排序)算法总结和参考的资源,代码使用OC实...

网友评论

      本文标题:04-希尔排序(python,oc)

      本文链接:https://www.haomeiwen.com/subject/angxsxtx.html