希尔排序是依据直接插入排序的,希尔排序时间复杂度为O(nlogn)

5.希尔排序(Shell)

       
华杰让自家看了一道面课题:现有一段程序S,可以对任意n个数举行排序。假使后天亟需对n^二个数举办排序,最少须求调用S多少次?(只同意调用S,不得以做其他操作)。

void shellsort1(int num[], const int len)
{
    if (len <= 1) return;

    int i, j, k, dlen, temp;

    for (dlen = len / 2; dlen > 0; dlen /= 2) //确定步长
    {
        for (i = 0; i < dlen; i++)
        {
            for (j = i + dlen; j < len; j += dlen)
            {
                temp = num[j];
                k = j - dlen;
                while (k >= 0 && num[k] > temp)
                {
                    num[k + dlen] = num[k];
                    k -= dlen;
                }
                num[k + dlen] = temp;
            }
        }
    }
}

void shellsort2(int num[], const int len)
{
    int i, j, dlen, temp;

    for (dlen = len / 2; dlen > 0; dlen /= 2)
    {
        for ( i = dlen; i < len; i++) //从第二序列开始,前面为有序区
        {
            if (num[i] < num[i - dlen])
            {
                temp = num[i];
                j = i - dlen;
                while (j >= 0 && num[j] > temp)
                {
                    num[j + dlen] = num[j];
                    j -= dlen;
                }
                num[j + dlen] = temp;
            }
        }
    }
}

        看到了这些,小编想试试希尔排序,就学习。

一行三种写法都得以,不过后者相比便利明白和书写。

一.答辩准备

希尔排序时间复杂度为O(nlogn),可是无需额外开发空间,属于不平稳排序。

       
希尔排序是依照直接插入排序的,不了然请看这一篇http://www.cnblogs.com/hxsyl/archive/2013/06/02/3113656.html

Hill排序的年月品质优于直接插入排序,原因如下:

        希尔排序(Shell
Sort)是插入排序的一种,是针对性直接插入排序算法的校订,是将全方位无连串分割成几何小的子系列分别进行插入排序,希尔排序并不稳定。该办法又称缩短增量排序,因DL.Shell于1957年指出而得名。

(1)当文件初态基本铁定的事情时,直接插入排序所需的相比和运动次数较多;

       
基本思维:先取2个小于n的平头d1作为第四个增量,把文件的凡事记录分成d二个组。全部距离为d1的翻番的笔录放在同二个组中。先在各组内举办直接插入排序;然后,取第贰个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即全体记录放在同样组中举办间接插入排序截止。

(2)当n值较小时,n和n^2的歧异也较小,即直接插入排序的最好时光复杂度O(n)和最坏时间复杂度O(n^2)差异不大。

     希尔排序的日子质量优越直接插入排序的原由:
     ①当文件初态基本平稳时直接插入排序所需的可比和移动次数均较少。
    
②当n值较小时,n和n2的不一致也较小,即直接插入排序的极端时光复杂度O(n)和最坏时间复杂度0(n2)差异不大。
    
③在希尔排序开首时增量较大,分组较多,每组的笔录数据少,故各组内直接插入较快,后来增量di逐步减少,分组数逐步压缩,而各组的笔录数据渐渐增多,但鉴于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序进程也较快。
        因而,Hill排序在功能上较直接插人排序有较大的惜墨如金。

据悉以上两点,在Hill排序先河时增量较大,分组比较多,每组的笔录数据较少,故各组内直接插入排序较快。后来增量逐步压缩,分组数目渐渐较少,各组记录数据逐步增多,但由于文件中央接近平稳状态,所以新的排序进度较快。

        增量体系的选料:Shell排序的施行时间凭借于增量连串。
    好的增量序列的联手特征(查到的资料都这么讲):
     ① 最终三个增量必须为1;
     ② 应该尽量防止体系中的值(尤其是附近的值)互为倍数的情状。      

 

二.Java实现

6.飞快排序(QuickSort)

public class ShellSort {

 public static void main(String[] args) {



      int[] arr = new int[]{44,33,99,10,30,20,59,78,23,48};

      System.out.print("排序前:");

      for(int o: arr) {

          System.out.print(o+" ");

      }

      System.out.println();

      shellSort(arr);

      System.out.print("排序后:");

      for(int o: arr) {

          System.out.print(o+" ");

      }

      System.out.println();

  }

 private static void shellSort(int[] arr) {



      int j;

      int len = arr.length;

      for(int val=len>>1; val>0; val>>=1) {

          //下面是对本次的所有分组做直接插入排序

          for(int i=val; i<len; i++) {

              int temp = arr[i];

              /*

                * 为什么每次都用temp比较呢?

               * 因为直接插入就是找到temp的合适位置。

               * 为什么temp<arr[j-val]这个条件可以放在for内呢?

               * 因为原来的组内数据已经有序,找到位置就停止便是。

               * 不甚理解的去看直接插入排序吧。

               */

              for(j=i; j>=val&&temp<arr[j-val]; j-=val) {

                  /*

                    * 为什么是arr[j-val]不是arr[j]呢?

                   * 因为j=i开始的,而且条件是j>=val&&temp<arr[j-val]

                   */

                  arr[j] = arr[j-val];

              }

              /*

                * 注意不是arr[i] = temp

               * 直接插入排序也是这样的。

               * 为什么呢?

               * 因为j是位置,i是待插入元素

               */

              arr[j] = temp;

          }

      }

  }

}
//快速排序
template<typename T>
void SWAP(T& a, T&b)
{
    T temp = a;
    a = b;
    b = temp;
}

int Partition(int data[], int left, int right)
{
    if (data == NULL || left < 0 || (right - left) <= 0)
    {
        assert(false);
    }

    int pivot = data[left]; //轴心元素
    while (left < right)
    {
        //末尾元素大于轴心元素数值时,不作处理,尾指针往前递进
        while (left < right&&data[right] >= pivot)
            --right;

        //找到第一个不满足data[right]>pivot的元素,让其与data[left]交换
        SWAP(data[left], data[right]);

        //当前端的元素小于轴心元素时,不作处理,头指针往后递进
        while (left < right&&data[left] <= pivot)
            ++left;

        //找到第一个不满足data[left]<pivot的元素,让其与data[right]交换
        SWAP(data[left], data[right]);
    }

    /*由于前面
    while(start<end&&arry[end]>=pivot)和while(start<end&&arry[start]<=pivot)的限定,
    保证了最后不会出现low>high的情况,因此最后low=high,该位置就是轴心元素在数组中的置。
    */
    return left;
}

void Qsort(int data[], int left, int right)
{
    if (left < right)
    {
        //此步保证data[pivot]大于左边的元素小于右边的元素,arry[pivot]被正确安排
        int pivot = Partition(data, left, right);
        Qsort(data, left, pivot - 1);
        Qsort(data, pivot + 1, right);
    }
}

void QuickSort(int data[], const int& length)
{
    if (data == NULL || length <= 1)
        return;

    Qsort(data, 0, length - 1);
}

三.问题

很有意思的算法,通晓确实要花一点年华。

       
希尔排序一定正确么?换句话说怎样抉择增量体系才能保障科学(包涵长度、值)?是的,最终一遍只要保险增量是1就ok(不管连串长度,只但是功用就低了),如若连串唯有1,这就是直接插入排序了,不清楚对否。

具体原领悟释可以参考:http://blog.csdn.net/morewindows/article/details/6684558,结合里面的图解,学习曲线一下就降下来了。

四.结束语

 

       
写完正准备叫内人去吃饭,隔壁宿舍一匹夫过的话大一新生已经攻占饭铺了。

7.二分查找(随机乱入)

//二分查找
int binary_search(int data[], const int length, const int target)
{
    if (data == NULL || length <= 0)
        return -1;

    int left = 0, right = length - 1, mid = 0;

    while (left <= right)
    {
        mid = (left + right) >> 1;
        if (data[mid] == target)
        {
            return mid;
        }
        else if (data[mid] < target)
        {
            right = mid - 1;
        }
        else if (data[mid] > target)
        {
            left = mid + 1;
        }
    }

    return -1;
}

剑指offer中有一个摸索旋转数组中细小值,二分查找的变形,蛮不错的。

相关文章