数据结构 希尔排序 c Swift 版本

个人对希尔排序的理解

• 是将待排序 分成若干的子系列排序（是由相隔的个参数，分割而成）。
• 每次 排序子序列（相隔的参数减少一半）
• 最终 会对全体元素进行一次直接插入排序， 因为在 （元素大部分有序的情况下，直接插入排序效率很高），所以希尔排序时间效率就快

算法 时间复杂度 与 自己想法

• 由于 希尔排序 基于 插入排序的一种算法，当相隔的参数为1，过程就为插入排序。
• 所以 希尔排序 优化点可以根据 实际的情况 和 待排序的元素有序程度。 来单独设计 相隔的参数
• 在 待排序列 有序的情况下 速度很快， 当然在最差的情况下 也比 直接插入排序快。
• 希尔排序的时间复杂度是：O（n^1.2）
• 算法 不稳定

        #include <stdio.h>

        void shellsort(int a[], int n)
        {
            int j, gap;
            
            for (gap = n / 2; gap > 0; gap /= 2) //空开几个
                for(j = gap; j < n; j++) //扫一遍
                    if (a[j] < a[j-gap])  //比较 俩
                    {
                        int temp = a[j];
                        int k = j - gap;
                        
                        while (k >= 0 && a[k] > temp) ///让最小的 移动到最前面
                        {
                            a[k + gap] = a[k];
                            k -= gap;
                        }
                        ///最小的复制过来
                        a[k + gap] = temp;
                    }
        }

        int main(){
           
            int a[10] = {2,5,6,7,8,9,0,1,3,4};
            
            shellsort(a, 10);
            
            int i ;
            
            for (i = 0; i < 10; i++) {
                
                printf("%d",a[i]);
                
            }
            printf("\n");

            return 0;
        }

• swift

        import UIKit
  
        func shellsort(inout a : [Int]){
            
            let n = a.count-1
            
            for(var gap = n / 2; gap > 0; gap /= 2){
                for j in gap...n {
                    if a[j] < a[j-gap]{
                        let tmep = a[j]
                        var k = j - gap
                        while k >= 0 && a[k] > tmep {//扫一遍 好填最小值
                            a[k + gap] = a[k]
                            k -= gap
                        }
                        a[k + gap] = tmep
                    }
                }
            }
            
        }
  
        var a = [2,5,6,7,8,9,0,1,3,4]
  
        shellsort(&a)
  

• 看我那么可爱n(≧▽≦)n

• 关注我的微薄 (梁同桌)：http://weibo.com/tongrenyinsheng

• 个人博客： http://www.liangtongzhuo.com

• ios 个人写的app （同人音声）ASMR音乐