图解排序算法

发表于 |
字数统计: 3k | 阅读时长 ≈ 12

转载

希尔排序

　　希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现。

基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

image

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package sortdemo;
import java.util.Arrays;
/**
 * Created by chengxiao on 2016/11/24.
 */
public class ShellSort 
{
    public static void main(String []args)
    {
        int []arr ={1,4,2,7,9,8,3,6};
        sort(arr);
        System.out.println(Arrays.toString(arr));
        int []arr1 ={1,4,2,7,9,8,3,6};
        sort1(arr1);
        System.out.println(Arrays.toString(arr1));
    }
    /**
     * 希尔排序 针对有序序列在插入时采用交换法
     * @param arr
     */
    public static void sort(int []arr)
    {
        //增量gap，并逐步缩小增量
       for(int gap=arr.length/2;gap>0;gap/=2)
       {
           //从第gap个元素，逐个对其所在组进行直接插入排序操作
           for(int i=gap;i<arr.length;i++)
           {
               int j = i;
               while(j-gap>=0 && arr[j]<arr[j-gap])
               {
                   //插入排序采用交换法
                   swap(arr,j,j-gap);
                   j-=gap;
               }
           }
       }
    }
    /**
     * 希尔排序 针对有序序列在插入时采用移动法。
     * @param arr
     */
    public static void sort1(int []arr)
    {
        //增量gap，并逐步缩小增量
        for(int gap=arr.length/2;gap>0;gap/=2)
        {
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for(int i=gap;i<arr.length;i++)
            {
                int j = i;
                int temp = arr[j];
                if(arr[j]<arr[j-gap])
                {
                    while(j-gap>=0 && temp<arr[j-gap])
                    {
                        //移动法
                        arr[j] = arr[j-gap];
                        j-=gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }
    /**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b)
    {
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }
}

堆排序

预备知识

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
image

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：

堆排序基本思想及步骤

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

  1. 假设给定无序序列结构如下

image

  1. 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

image

  1. 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

image

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

image

此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

image

b.重新调整结构，使其继续满足堆定义

image

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

image

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

image

再简单总结下堆排序的基本思路：

  • 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
  • 将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
  • 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package sortdemo;

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/17.
 * 堆排序demo
 */
public class HeapSort 
{
    public static void main(String []args)
    {
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr)
    {
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--)
        {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--)
        {
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length)
    {
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1)
        {//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1])
            {//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp)
            {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else
            {
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b)
    {
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

基于PriorityQueue实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public class b_41_medianinstream
{
    public static PriorityQueue<Integer> maxheap,minheap;
    public static int num = 0;

    public void addNumber(int value)
    {
        maxheap.add(value);
        System.out.println(minheap);
        System.out.println(maxheap);
        if(num % 2 == 0)
        {
            if(minheap.isEmpty())
            {
                num++;
                return;
            }
            //新插入的值大于min堆的根（最小值），则应该被插到min堆中
            //交换？min堆最小的给max堆
            else if(maxheap.peek() > minheap.peek())
            {
                int maxheap_root = maxheap.poll();
                int minheap_root = minheap.poll();
                System.out.println("maxheap_root="+maxheap_root+",minheap_root="+minheap_root);
                maxheap.add(minheap_root);
                minheap.add(maxheap_root);
                System.out.println(minheap);
                System.out.println(maxheap);
            }
        }
        else
        {
            minheap.add(maxheap.poll());
        }
        num++;
    }

    public int getMedian()
    {
        if(num % 2 ==0)
            return maxheap.peek();
        else
            return (maxheap.peek() + minheap.peek())/2;
    }
    public static void main(String[] args)
    {
        b_41_medianinstream medianinstream = new b_41_medianinstream();

        Comparator<Integer> mycomparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                /*如果指定的数与参数相等返回0。
                如果指定的数小于参数返回 -1。
                如果指定的数大于参数返回 1
                * */
                return o2.compareTo(o1);
            }
        };


        maxheap = new PriorityQueue<Integer>(20,mycomparator);
        minheap = new PriorityQueue<Integer>(20);


        int a[] = {2,4,6,8,10,5,7,9};
        for(int i =0; i < 8; i++)
        {
            medianinstream.addNumber(a[i]);
           // minheap.add(a[i]);
          //  maxheap.add(a[i]);
          //  System.out.println(minheap);
         //   System.out.println(maxheap);
            System.out.println();
        }
        System.out.println(medianinstream.getMedian());

    }
}

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

归并排序

image

image

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package sortdemo;

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/8.
 */
public class MergeSort 
{
    public static void main(String []args)
    {
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr)
    {
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp)   
    {
        if(left<right)
        {
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp)
    {
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right)
        {
            if(arr[i]<=arr[j])
            {
                temp[t++] = arr[i++];
            }else 
            {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid)
        {//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right)
        {//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right)
        {
            arr[left++] = temp[t++];
        }
    }
}

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。