常见的排序算法

稳定的排序算法

  • 冒泡排序 $O(N^2)$
  • 插入排序 $O(N^2)$
  • 桶排序(bucket sort) , $O(N^2)$ , 需要额外 $O(K)$ 的空间
  • 合并排序 (MergeSort ) $O(NlogN)$ ,额外 $O(N)$ 的空间
  • 基数排序 $O(N*K) $ , 需要 $O(N)$ 的空间

不稳定的排序算法

  • 希尔排序 $O(nlogn) $
  • 堆排序 $O(NlogN) $
  • 快速排序 $O(nlogn)$
 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

  /**
     * 堆排序工具类
     */
    private static class HeapSortHelper{
        private static void swap(int[] p,int l,int r)
        {
            if(p[l]==p[r]) return;
            p[l]^=p[r];
            p[r]^=p[l];
            p[l]^=p[r];
        }
        private static void heapify(int[] p,int cur,int heapSize)
        {

            int next = (cur<<1)+1;
            while (next<heapSize)
            {
                //默认选中左孩子
                if((next+1)<heapSize&&p[next+1]>p[next])
                {
                    ++next;//选择右孩子
                }

                if(p[cur]>=p[next])
                {
                    break;
                }
                swap(p,cur,next);
                cur = next;
                next = 1+(next<<1);
            }


        }
        private static void build(int[] p,int rightEnd)
        {
            if(p.length<=1) return;
            for(int i=((rightEnd>>1)-1);i>=0;--i)
            {
                heapify(p,i,rightEnd);
            }
        }


        private static void heapSort(int[] p)
        {
            if(p==null||p.length==0)return;

            build(p,p.length);

            for(int i=(p.length-1);i>=0;--i)
            {
                swap(p,0,i);
                heapify(p,0,i);
            }

        }
    }