排序算法(1)—选择,插入,希尔
in 数据结构 with 0 comment

排序算法(1)—选择,插入,希尔

in 数据结构 with 0 comment

三种初级排序

一.选择排序

  1. 排序思想:依次找到最小(最大)元素,并与未排序数组的第一个元素交换,若为数组第一个元素,则和自己进行交换,若为数组最后一个元素,排序完成。
  2. 排序实现:(java代码)
    public static void SelctionArray(int[] arr)
    {
        int N = arr.length;
        for ( int i = 0; i<N; i++)
        {
            int min = i;
            for (int j = i+1; j<N; j++)
                if (arr[j]<arr[i])    
                {
                    min = j;
                    int t = 0;
                    t = arr[i];arr[i] = arr[j]; arr[j] = t;
                }            
        }
    }
  1. 复杂度:

     时间复杂度:N^2
    空间复杂度:1
    对于长度为N的数组,大约进行N^2次比较和N次交换。
    注意:排序所需时间和数组是否有序无关;
          数据移动次数相对大多数排序算法是最少的。
    

二.插入排序

  1. 排序思想:
  2. 排序实现:(java代码)
    public static void InsertionSort(int[] arr)
    {
        int N = arr.length;
        for (int i = 0; i<N; i++)
        {
            for (int j = i; j>0 && arr[j]<arr[j-1];j--)
                exch(arr,j,j-1);  //交换arr[j]和arr[j-1].
        }
    }
  1. 复杂度:

    时间复杂度:N~N^2
    空间复杂度:1

    对于长度为N的且不重复的数组,平均需要~N^2/4次比较,一级~N^2次交换。
    最好需要N-1次比较,最坏需要~N^2/2次比较和~N^2次交换。

三.希尔排序

  1. 排序思想:使数组任意相隔为h的元素是有序的(h有序数组)。当h=N(数组长度)/3递减到h=1时,则排序完成。
  2. 排序实现:(java代码)
    public static void shellSort(int[] arr)
    {
        int N = arr.length;
        int h = 1;
        while(h < N/3) h = h*3+1;//h=1,4,13,40,...
        while(h>=1)
        {
            //使得数组变为h有序
            for (int i = h;i<N; i++)
            {
                for(int j = i;j>=h && arr[j]<arr[j-h]; j -= h)
                    exch(arr,j,j-h);  //交换arr[j]和a[j-h]
            }
            h = h/3;
        }
    }
  1. 复杂度:

    时间复杂度:并非很确定,~N的5/6次方,~NlogN.
    空间复杂度:1
    注意:h的每次递减的次数,带来的比较次数大约为N的1/5次方。
    

参照算法第四版


内容原创,转载请注明出处



Responses