常见排序算法总结

| 分类 algorithm-sort  | 标签 sort 

排序依赖的方法和数据结构

1 交换和比较

1) 使用一个临时元素保存中间值，空间复杂度是O(1)。

1
2
3
4
5
6
7
private void swap(int[] nums,int i ,int j){
        if(i == j) return;
        if(nums[i] == nums[j]) return;
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

2) 不使用临时元素,但需要注意当i==j时会出错，所以需要先处理这种情况。 当i==j 或者nums[i]==nums[j]时无需交换，快速返回

1
2
3
4
5
6
7
 private void swap(int[] nums,int i, int j){
            if(i == j) return;
            if(nums[i] == nums[j]) return;
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }

3) 比较大小

1
2
3
 private boolean less(int[] a, int i, int j){
        return a[i] < a[j];
     }

2 链表结构

1
2
3
4
5
6
public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
      ListNode(){}
 }

2 选择排序

每次从剩余元素选择一个最小的，排在当前位置.

1
2
3
4
5
6
7
8
9
10
11
  public void selectionSort(int[] nums){
        if(nums == null || nums.length <= 1) return;
        int n = nums.length;
         for(int i = 0; i < n; i++){
            int min = i;
            for(int j = i+1; j < n; j++){
                if(less(nums,j,min)) min = j;
            }
            swap(nums,i,min);
        }
     }

3 插入排序

1 数组

每次都把一个元素插入到已经有序的序列里。

1
2
3
4
5
6
7
8
9
10
 public void insertionSort(int[] nums){
        if(nums == null || nums.length <= 1) return;
        int n = nums.length;
        //i之前的已经有序
        for(int i = 1; i < n ; i++){
            for(int j = i; j >= 1 && less(nums,j,j-1); j--){
                swap(nums,j,j-1);
            }
        }
     }

2 链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode insertionSort(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode dummyHead = new ListNode();
        ListNode pre;
        while(head != null){
            pre = dummyHead;
            while(pre.next != null && pre.next.val < head.val){
                pre = pre.next;
            }
            ListNode tmp = head.next;
            head.next = pre.next;
            pre.next = head;
            head = tmp;
        }
        return dummyHead.next;
    }

4 希尔排序

选择的序列h = 1,4,13,40....
希尔排序可以这样理解，每次排序间隔为h的元素。
比如
0 1 2 3 4 5 6 7 8 9 10
h = 4 时：排序0 4 8,1 5 9, 2 6 10, 3 7
h = 1 时 排序 0 1 2 3 4 5 6 7 8 9 10
代码可以更清晰的表现出希尔排序和插入排序的关系。
仔细比较可以看出，插入排序仅仅是希尔排序当h=1时的特殊情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void shellSort(int[] nums){
        if(nums == null || nums.length <= 1) return;
        int n = nums.length;
        int h = 1;
        while(h < n / 3) h = 3 * h + 1;
        while(h >= 1){
            for(int i = h; i < n; i++){
                for(int j = i; j >= h && less(nums,j,j-h); j-=h){
                    swap(nums,j,j-h);
                }
            }
            h = h / 3;
        }      

     }

5 快速排序

每趟排序时选定一个元素，将小于该元素的放在元素左边，大于该元素的放在右边，然后 递归的处理左右两边。

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
public void quickSort(int[] nums){
        if(nums == null || nums.length <= 1) return;
        int hi = nums.length - 1;
        quickSort(nums,0,hi);
     }
     private void quickSort(int[] nums,int lo,int hi){
        if(lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        int j = partition(nums,lo,hi);
        quickSort(nums,lo,j-1);
        quickSort(nums,j+1,hi);
     }
     private int partition(int[] nums,int lo,int hi){
        int i = lo;
        int j = hi+1;
        int v = nums[lo];
        while(true){
            while(less(nums,++i,lo)) if(i == hi) break;
            while(less(nums,lo,--j)) if(j == lo) break;
            if(i >= j) break;
            swap(nums,i,j);
        }
        swap(nums,lo,j);
        return j;
     }

6 归并排序

1 数组

归并排序的基本思路就是先排序左半部分，在排序有半部分，然后将两部分合并。 下面代码

mergeSort(nums,lo,mid);
mergeSort(nums,mid+1,hi);
merge(nums,lo,mid,hi);

就是这个思路。

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
public void mergeSort(int[] nums){
        if(nums == null || nums.length <= 1) return;
        //aux是辅助数组
        aux = new int[nums.length];
        mergeSort(nums,0,nums.length-1);
     }
     private void mergeSort(int[] nums,int lo, int hi){
        if(lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums,lo,mid);
        mergeSort(nums,mid+1,hi);
        merge(nums,lo,mid,hi);
     }
     private void merge(int[] nums,int lo,int mid,int hi){
        //将nums[lo..mid]和nums[mid+1,hi]合并
        int i = lo;
        int j = mid + 1;
        for(int k = lo; k <= hi; k++){
            aux[k] = nums[k];
        }
        for(int k = lo; k <= hi; k++){
            if(i > mid) nums[k] = aux[j++];
            else if(j > hi) nums[k] = aux[i++];
            else if(less(aux,i,j)) nums[k] = aux[i++];
            else nums[k] = aux[j++];
        }
     }

2 链表

其中看下找链表中点的方法findMid(),设定两个指针，一个slow,一个fast， slow每次移动一步，fast一次移动两步，当fast.next==null 或者fast.next.next==null时，此时slow指向的即是链表中点.

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
public ListNode mergeSort(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode mid = findMid(head);
        ListNode r = mid.next;
        mid.next = null;
        ListNode left = mergeSort(head);
        ListNode right = mergeSort(r);
        return merge(left,right);
    }
    private ListNode merge(ListNode left,ListNode right){
        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        while(left != null && right != null){
            if(left.val < right.val){
                cur.next = left;
                left = left.next;
            }else{
                cur.next = right;
                right = right.next;
            }
            cur  = cur.next;
        }
        cur.next = (left == null) ? right : left;
        return dummyHead.next;
    }
    private ListNode findMid(ListNode head){
        ListNode slow,fast;
        slow = fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

3 自底向上的归并排序

1
2
3
4
5
6
7
8
9
10
public void mergeSortBU(int[] nums){
        if(nums == null || nums.length <= 1) return;
        int n = nums.length;
        aux = new int[n];
        for(int  sz = 1; sz < n; sz += sz){
            for(int lo = 0; lo < n - sz; lo += sz + sz){
                merge(nums,lo,lo+sz-1,Math.min(lo+sz+sz-1,n-1));
            }
        }  

    }

7 堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void heapSort(int[] nums){
        if(nums == null || nums.length <= 1) return;
        int hi = nums.length - 1;
        for(int k = hi / 2; k >= 0; k--){
            sink(nums,k,hi);
        }
        while(hi > 0){
            swap(nums,0,hi--);
            sink(nums,0,hi);
        }
    }
    private void sink(int[] nums,int i,int hi){
        while(2i+1 <= hi){
            int j = 2i+1;
            if(j < hi && less(nums,j,j+1)) j = j + 1;
            if(less(nums,j,i)) break;
            swap(nums,i,j);
            i = j;
        }
    }

8 冒泡排序

冒泡排序时比较简单的入门级排序算法。

1
2
3
4
5
6
7
8
9
10
public void bubbleSort(int[] nums){
        if(nums == null || nums.length <= 1) return;
        for(int i = 0; i < nums.length; i++){
            for (int j = 0; j < nums.length-1-i ; j++) {
                if(!less(nums,j,j+1)){
                    swap(nums,j,j+1);
                }
            }
        }
    }

以上都是基于比较的排序,下面的是三种非比较算法。(后续补完)

9计数排序

顾名思义，通过计数来排列元素的位置。通俗来讲，就是通过计算其中元素比多少个数大来排列位置， 虽然说是非比较算法，但个人感觉只是没有明显的用到比较，但在构造数组的过程中已经隐含了大小的概念。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] countSort(int[] nums,int max){
        if(nums == null || nums.length <= 1) return;
        int n = nums.length;
        //计数数组
        int[] c = new int[max+1];
        //存储数组
        int[] r = new int[n];
        //初始化计数数组
        for(int i = 0; i < n; i++){
            c[nums[i]]++;
        }
        //计算
        for(int i = 1; i < n; i++){
            c[i] = c[i] + c[i-1];
        }
        //排列元素
        for(int i = n-1; i >= 0; i--){
            r[--c[nums[i]]] = nums[i];
        }
        return r;
    }

2基数排序

其中用到了计数排序

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
public void radixSort(int[] nums,int radix,int digits){
        if(nums == null || nums.length <= 1) return;
        int n = nums.length;
        //暂存中间排序结果
        int[] tmp = new int[n];
        //计数排序中的count数组
        int[] count = new int[radix];
        int divide = 1;
        for(int i = 0; i < digits; i++){
            for(int j = 0; j < n; j++){
                tmp[j] = nums[j];
            }
            for(int j = 0; j < radix ; j++){
                count[j]  = 0;
            }
            for(int j = 0; j < n; j++){
                int t = (tmp[j] / divide) % radix;
                count[t]++;
            }
            for(int j = 1; j < radix ; j++){
                count[j]  = count[j] + count[j-1];
            }
            for(int j = n-1; j >= 0; j--){
                int t = (nums[j] / divide) % radix;
                tmp[--count[t]] = nums[j];
            }
            divide = divide * radix;
        }
        System.err.println(Arrays.toString(tmp));
    }

桶排序

这个让我想起我收拾一个小图书馆的书架的事情。当时有1000多本的图书，要根据类型和序号进行排序，我首先看了下书籍大概分块放的，然后就闷头开始做。一会就发现这种方法行不通，然后就想到可以先把范围变小，我先腾出一块空地方，将图书按类别放在对应的位置，然后再按序号进行排序。桶排序也差不多是这个意思。 比如对于[0-99)的数据，可以分成10个桶[0-10),[10-20),[20-30),[30-40),[40-50),[50-60),[60-70),[70-80),[80-90),[90-100)。然后将待排序的数字扔到对应的桶里，桶内排序，然后依次取出即可。我看网上的桶排序的有的用二维数组来做，感觉比较麻烦，用链表来做就很简单了，也很明了。

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
public void bucketSort(int[] nums){
        if(nums == null || nums.length <= 1) return;
        int n = nums.length;
        bucketNode[] bucket = new bucketNode[100];
        for(int i = 0; i < bucket.length; i++){
            bucketNode node = new bucketNode();
            bucket[i]= node;
        }
        for(int i = 0; i < n; i++){
            int tmp = nums[i] / 10;
            bucketNode node = new bucketNode();
            node.val = nums[i];
            bucketNode pre = bucket[tmp];
            while(pre.next != null && pre.next.val < nums[i]){
                pre = pre.next;
            }
            node.next = pre.next;
            pre.next = node;
        }
        for(int i = 0; i < bucket.length; i++){
            bucketNode tmp  = bucket[i].next;
            while(tmp != null){
                System.err.println(tmp.val);
                tmp = tmp.next;
            }
        }



<span class="o">}</span>


<span class="kd">class</span> <span class="nc">bucketNode</span><span class="o">{</span>
    <span class="kt">int</span> <span class="n">val</span><span class="o">;</span>
    <span class="n">bucketNode</span> <span class="n">next</span><span class="o">;</span>
<span class="o">}</span><span class="w">

排序算法比较

维基百科-排序算法

名称 数据对象 稳定性
时间复杂度
平均 最坏
空间复杂度 简要描述
冒泡排序 数组 稳定
O(n^2)
O(1) （无序区，有序区）。从无序区通过交换找出最大元素放到有序区前端
选择排序
数组
链表
不稳定
稳定
O(n^2)
O(1) （有序区，无序区）。在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少。
插入排序 数组 链表 稳定 O(n^2) O(1) (有序区，无序区）。把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。
堆排序 数组 不稳定 O(nlogn) O(1) (最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。
归并排序
数组
链表
稳定 O(nlogn)
O(n)+O(logn) 如果不是从下到上
O(1)
把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。
快速排序 数组 不稳定
O(nlogn) O(n^2)
O(logn),O(n) (小数，枢纽元，大数）
希尔排序 数组 不稳定
O(nlog^2n) O(n^2)
O(1) 每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是1。
计数排序 数组 链表 稳定 O(n+m) O(n+m) 统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）
桶排序 数组链表 稳定 O(n) O(m) 将值为i的元素放入i号桶，桶内进行排序，最后依次把桶里的元素倒出来。
基数排序 数组 链表 稳定
O(k*n) O(n^2)
一种多关键字的排序算法，可用桶排序实现。

上一篇     下一篇