• 排序是将一串数据按照其某个或者某些关键字的大小进行递增或递减排列的操作我，通常指的排序是升序，排序方式是原地排序
• 下面介绍下希尔排序

希尔排序

• 原理：
  • 指定一个值gap，将待排序区间分成gap个组，每个组相邻元素的下标差值是gap。将每个组元素进行排序
  • 减小gap的值，重复进行排序直到gap等于1
  • 当gap等于1的时候，数组变成有序数组
• 实质：
  • 希尔排序是对直接插入排序的优化
  • 当gap>1时都是进行序排序，当gap=1时，数组已接近有序
• 希尔排序是一个不稳定的排序

实现方式

   public void shellSort(int[] array) {
       int gap = array.length;
       while(gap > 1) {
           insertSortGap(array, gap);
           //gap的缩小方式决定了性能提升的程度
           gap = gap / 3 + 1;
       }
       insertSortGap(array, 1);
   }

   private void insertSortGap(int[] array, int gap) {
       for(int i = 0; i < array.length; i++) {
           int tmp = array[i];
           int j = i - gap;
           for(;j > 0 && array[j] > tmp; j -= gap) {
               array[j + gap] = array[j];
           }
           array[j + gap] = tmp;
       }
   }

性能分析

• 时间复杂度
  • 最好情况：数组有序时时间复杂度是O(N)
  • 最快情况：时间复杂度是O(N^2)，很难构造出实例
  • 平均情况：时间复杂度是O(N^1.3)
• 空间复杂度：O(1)
• 稳定性：不稳定

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。