排序算法总结(Java语言版)

发表于 | 分类于 | | 热度: °C
字数统计: 4,280 | 阅读时长 ≈ 22

简介：从基本的O(n^2)时间复杂度的冒泡排序、选择排序、插入排序以及希尔排序到高级的O(nlogn)时间复杂度的归并排序、快速排序、堆排序。分析各个算法的时间复杂度，空间复杂度等。

排序算法比较

基本排序算法

一、冒泡排序(BubbleSort)

基本思想

相邻两个元素比较大小，大的元素下沉，小的元素上浮

过程

  1. 从前往后比较相邻两个元素，如果后面的元素小，则交换位置，遍历完数组，最大元素将被放在数组尾部。
  2. 重复上述循环，遍历数组第1到n-i(i=1,2,…n-2)个元素，依次将第2,3,…,n-1大的元素放在数组尾部，循环结束，最小的元素自然就在数组头部。

冒泡排序

算法分析

  • 平均时间复杂度：O(n^2)

    推导：外层循环n-1次 ,内层循环n-i-1(i=0,1,2,…n-2)次,故时间复杂度为： (n-1)+(n-2)+…1=(n-1)n/2=O(n^2)

  • 空间复杂度：O(1)

  • 稳定排序

    由于下沉中遇到相等元素，不交换位置，故属于稳定排序

  • 原地排序

代码实现

BubbleSort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class BubbleSort {
    public static <T extends Comparable<? super T>>
    void sort(T[] a){
        int n=a.length;
        for(int i=0;i<n-1;i++){
            for(int j=1;j<n-i;j++){
                if(a[j].compareTo(a[j-1])<0){
                    swap(a,j-1, j);
                }
            }
        }
    }

    public static<T extends Comparable<? super T>>
    void swap(T[] a,int m,int n){
        T temp=a[m];
        a[m]=a[n];
        a[n]=temp;
    }
}

二、选择排序(SelectionSort)

基本思想

每次选择未排好序中最小的元素与当前未排好序的第一个元素交换位置，不断遍历，直到整个数组有序

过程

  1. 从前往后遍历整个数组，找到最小的那个元素，并与第1个元素交换位置
  2. 重复上述过程，遍历数组中第i(i=2,3,…n-1)个到第n个元素，找到其中最小的元素与第i个元素交换位置

选择排序

算法分析

  • 平均时间复杂度：O(n^2)

  • 空间复杂度：O(1)

  • 稳定排序

  • 原地排序

代码实现

SelectionSort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class SelectionSort {
    public static void sort(Comparable[] arr){
        int n=arr.length;
        for(int i=0;i<n-1;i++){
            int minIndex=i;
            for(int j=i+1;j<n;j++){
                if(arr[j].compareTo(arr[minIndex])<0){
                    minIndex=j;
                }
            }
           swap(arr,i,minIndex);
        }
    }

    private static void swap(Comparable[] arr, int i, int j) {
        Comparable t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

三、插入排序(InsertionSort)

基本思想

从前往后访问数组元素，每次保证所访问元素插入到之前数组的合适位置。

过程

  1. 第2个元素与第1个元素比较大小，如果比第1个元素小，则交换两个元素位置
  2. 访问第i(i=3,4,….n)个元素，将该元素插入到前面数组中的合适位置，访问完数组所有元素，则排序完成

插入排序

算法分析

  • 平均时间复杂度：O(n^2)

  • 空间复杂度：O(1)

  • 稳定排序

  • 原地排序

代码实现

InsertionSort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class InsertionSort {
    public static<T extends Comparable<? super T>>
    void sort(T[] a){
        int n=a.length;
        int j;
        for(int i=0;i<n;i++){
            T temp=a[i];
            for( j=i;j>0&&temp.compareTo(a[j-1])<0;j--){
                a[j]=a[j-1];
            }
            a[j]=temp;
        }
    }
}

四、希尔排序(ShellSort)

基本思想

给定增量序列，按照增量由大到小，直到增量为1，将数组依照增量序列分为k个序列，对所有序列进行插入排序。完成数组排序。

过程

  1. 对于最大增量m，对序列（1,1+m,…,1+km),…,(a,a+m,…,a+km),…, (n-km,n-(k-1)m,…,n)进行插入排序
  2. 减小增量，重复上述过程，直到增量为1，对整个数组进行一次插入排序，使数组有序

希尔排序

算法分析

  • 平均时间复杂度：

    希尔增量( ht=[N/2] hk=[hk-1 /2] )：O(n^2)

    Hibbard增量(hk=2k-1)：O(n^(3/2))

  • 空间复杂度：O(1)

  • 不稳定排序

  • 原地排序

代码实现

ShellSort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class ShellSort {
    public static <T extends Comparable<? super T>>
    void sort(T[] a){
        int n=a.length;
        int j;
        // 希尔增量
        for(int gap=n/2;gap>0;gap/=2){
            for(int i=gap;i<n;i++){
                T temp=a[i];
                for(j=i;j>=gap && temp.compareTo(a[j-gap])<0;j-=gap){
                    a[j]=a[j-gap];
                }
                a[j]=temp;
            }
        }
    }
}

高级排序算法

五、归并排序(MergeSort)

基本思想

先递归的分解数列:一分为二，二分为四…,最后再合并数列，完成归并过程。待归并完成后，数组排序完成

过程

  1. 将数组从中间分为两部分，分别对左边右边数组进行归并排序，然后对两部分进行归并。
  2. 归并过程，额外开辟大小为n的数组空间，将每一次归并的结果放入新的数组，从头到尾依次访问两部分数组元素，较小的元素优先进行归并操作

归并排序

算法复杂度分析

  • 平均时间复杂度：O(nlogn)

    推导：数组不断对分，递归层数logn, 每层遍历n个数组元素。故时间复杂度为nlogn

  • 空间复杂度：O(n)

    需要开辟和数组同样大小的空间n,放置归并操作的元素，以及递归层数logn，占用栈空间.故空间复杂度为n+logn=O(n)

  • 稳定排序

  • 非原地排序

代码实现

1. 自顶向下的归并排序（递归实现）
MergeSort.java
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
import java.util.Arrays;
public class MergeSort {
    public static <T extends Comparable<? super T>>
    void sort(T[] a){
        int n=a.length;
        T [] temp=(T[]) new Comparable[n];
        mergeSort(a,temp,0,n-1);
    }

    private static<T extends Comparable<? super T>>
    void mergeSort(T[] a, T[] temp, int l, int r) {
        // 可优化 ，小数据进行插入排序
        if(l<r) {
            int mid = l + (r - l) / 2;
            mergeSort(a, temp, l, mid);
            mergeSort(a, temp, mid + 1, r);
            // 近乎有序时 能优化
            // 如果已经有序，不进行merge
            if(a[mid].compareTo(a[mid+1])>0) {
                merge(a, temp, l, mid + 1, r);
            }
        }
    }

    private static<T extends Comparable<? super T>>
    void merge(T[] a, T[] temp, int leftPos, int rightPos,int rightEnd) {

        int leftEnd=rightPos-1; // the end pos of left arr
        int tmpPos=leftPos;     // current pos of merge arr
        int numElements=rightEnd-leftPos+1;  // the number of elements of merge arr

        // main loop
        // the left and right arr are both incompletely sorted
        while(leftPos<=leftEnd && rightPos<=rightEnd){
            if(a[leftPos].compareTo(a[rightPos])<=0){
                temp[tmpPos++]=a[leftPos++];
            }
            else{
                temp[tmpPos++]=a[rightPos++];
            }
        }

        // the left arr is incompletely sorted
        while (leftPos<=leftEnd){
            temp[tmpPos++]=a[leftPos++];
        }

        // the right arr is incompletely sorted
        while (rightPos<=rightEnd){
            temp[tmpPos++]=a[rightPos++];
        }

        // copy the elements of temp arr to a
        for(int i=0;i<numElements;i++,rightEnd--){
            a[rightEnd]=temp[rightEnd];
        }
    }
}
2. 自底向上的归并排序（非递归实现）
MergeSortBU.java
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
public class MergeSortBU {
    public static <T extends Comparable<? super T>>
    void sort(T[] a){
        int n=a.length;
        T [] temp=(T[]) new Comparable[n];

        // 可优化 ，小数据进行插入排序
        // sz 从某一个数起
        for(int sz=1;sz<n;sz*=2){
            for(int i=0;i<n-sz;i+=2*sz){
                // 如果已经有序，不进行merge
                if(a[i + sz-1].compareTo(a[i+sz])>0) {
                    merge(a, temp, i, i + sz, Math.min(i + 2 * sz - 1, n - 1));
                }
            }
        }
    }

    private static<T extends Comparable<? super T>>
    void merge(T[] a, T[] temp, int leftPos, int rightPos,int rightEnd) {

        int leftEnd=rightPos-1; // the end pos of left arr
        int tmpPos=leftPos;     // current pos of merge arr
        int numElements=rightEnd-leftPos+1;  // the number of elements of merge arr

        // main loop
        // the left and right arr are both incompletely sorted
        while(leftPos<=leftEnd && rightPos<=rightEnd){
            if(a[leftPos].compareTo(a[rightPos])<=0){
                temp[tmpPos++]=a[leftPos++];
            }
            else{
                temp[tmpPos++]=a[rightPos++];
            }
        }

        // the left arr is incompletely sorted
        while (leftPos<=leftEnd){
            temp[tmpPos++]=a[leftPos++];
        }

        // the right arr is incompletely sorted
        while (rightPos<=rightEnd){
            temp[tmpPos++]=a[rightPos++];
        }

        // copy the elements of temp arr to a
        for(int i=0;i<numElements;i++,rightEnd--){
            a[rightEnd]=temp[rightEnd];
        }
    }
}
3. 基于链表的归并排序
MergeSortList.java
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
public class MergeSortList {
    public static<T extends Comparable<? super T>>
    ListNode<T> sort(ListNode<T> head){

        if(head==null || head.getNext()==null){
            return head;
        }

        ListNode p1=head; // locate the half of the list
        ListNode p2=head.getNext();

        while(p2!=null && p2.getNext()!=null){
            p1=p1.getNext();
            p2=p2.getNext().getNext();
        }

        // the right half list
        ListNode<T> r=sort(p1.getNext());

        // cut off the list
        p1.setNext(null);

        // the left half list
        ListNode<T> l=sort(head);

        return merge(l,r);
    }

    private static <T extends Comparable<? super T>>
    ListNode<T> merge(ListNode<T> l, ListNode<T> r) {
        while(l!=null && r!=null){
            if (l.getVal().compareTo(r.getVal())<=0){
                l.setNext(merge(l.getNext(),r));
                return l;
            }
            else{
                r.setNext(merge(l,r.getNext()));
                return r;
            }
        }
        if (l==null)
            return r;
        return l;
    }
}

六、快速排序(QuickSort)

基本思想

从数组中随机选定枢纽元(pivot)v，将数组其他元素分为

  1. < v 和 >=v的两部分或者<=和>v的两部分，分别对两部分进行快速排序——单路快排
  2. <=v和>=v的两部分，分别对两部分进行快速排序——双路快排
  3. <v、==v以及>v的三部分，分别对<v和>v两部分进行快速排序——三路快排

过程

主要是三类的分割(Partition)的过程

算法分析

  • 平均时间复杂度：O(nlogn)

  • 空间复杂度：O(logn)

    递归层数平均为logn，占用栈空间

  • 不稳定排序

  • 原地排序

代码实现

1. 单路快排
QuickSort.java
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
public class QuickSort {
    public static <T extends Comparable<? super T>>
    void sort(T[] a){
        quickSort(a,0,a.length-1);
    }

    // 对a[l...r]部分进行快速排序
    private static <T extends Comparable<? super T>>
    void quickSort(T[] a,int l,int r){
        if(l>=r)
            return;
        int p=partition(a,l,r);
        quickSort(a,l,p-1);
        quickSort(a,p+1,r);
    }

    // 对a[l...r]部分进行partition操作
    // 返回p,使得a[l...p-1]<a[p]<=a[p+1...r]
    private static <T extends Comparable<? super T>>
    int partition(T[] a, int l, int r) {
        int n=l+(int)(Math.random()*(r-l+1));
        swap(a,l,n);
        T v=a[l];
        // a[l+1...j]<v<a[j+1...i)
        int j=l;
        for(int i=l+1;i<=r;i++){
            if(a[i].compareTo(v)<0){
                swap(a,i,j+1);
                j++;
            }
        }
        swap(a,l,j);
        return j;
    }

    public static<T extends Comparable<? super T>>
    void swap(T[] a,int m,int n){
        T temp=a[m];
        a[m]=a[n];
        a[n]=temp;
    }
}
2. 双路快排
QuickSort2Ways.java
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
public class QuickSort2Ways {
    public static <T extends Comparable<? super T>>
    void sort(T[] a){
        quickSort2Ways(a,0,a.length-1);
    }

    // 对a[l...r]部分进行快速排序
    private static <T extends Comparable<? super T>>
    void quickSort2Ways(T[] a,int l,int r){
        if(l>=r)
            return;
        int p=partition(a,l,r);
        quickSort2Ways(a,l,p-1);
        quickSort2Ways(a,p+1,r);
    }

    // 对a[l...r]部分进行partition操作
    // 返回p,使得a[l...p-1]<=a[p]<=a[p+1...r]
    private static <T extends Comparable<? super T>>
    int partition(T[] a, int l, int r) {
        int n=l+(int)(Math.random()*(r-l+1));
        swap(a, l, n);

        //a[l+1..i)<=v<=a(j...r]
        int i = l+1;
        int j = r;
        T v = a[l];
        while (true) {
            while (i<=r && a[i].compareTo(v) < 0) {
                i++;
            }
            while (j>=l+1 && a[j].compareTo(v) > 0) {
                j--;
            }
            if(i>j) break;
            swap(a, i, j);
            i++;
            j--;
        }
        // a[i]>=v,a[j]<=v   a[l]=v
        swap(a, l, j);
        return j;
    }

    public static<T extends Comparable<? super T>>
    void swap(T[] a,int m,int n){
        T temp=a[m];
        a[m]=a[n];
        a[n]=temp;
    }
}
3. 三路快排
QuickSort3Ways.java
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
public class QuickSort3Ways {
    public static <T extends Comparable<? super T>>
    void sort(T[] a){
        quickSort3Ways(a,0,a.length-1);
    }

    // 对a[l...r]部分进行快速排序
    private static <T extends Comparable<? super T>>
    void quickSort3Ways(T[] a,int l,int r){
        if(l>=r)
            return;
        // partition
        int n=l+(int)(Math.random()*(r-l+1));
        swap(a, l, n);
        T v = a[l];
        int lt = l; //a[l+1...lt]<v
        int gt = r+1; //a[gt...r]>v
        int i=l+1; // a[lt+1...i)==v

        while (i<gt) {
            if(a[i].compareTo(v)<0){
                swap(a,i,lt+1);
                i++;
                lt++;
            }
            else if(a[i].compareTo(v)>0){
                swap(a,i,gt-1);
                gt--;
            }
            else{
                i++;
            }
        }
        swap(a,l,lt);
        lt--;
        quickSort3Ways(a,l,lt);
        quickSort3Ways(a,gt,r);
    }

    public static<T extends Comparable<? super T>>
    void swap(T[] a,int m,int n){
        T temp=a[m];
        a[m]=a[n];
        a[n]=temp;
    }
}

七、堆排序(HeapSort)

基本思想

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

过程

  1. 构造初始堆。将给定无序序列构造成一个最大堆，动态建堆-（参考基础堆排序以及优化堆排序代码）和静态建堆（参考原地堆排序）
    建堆
  2. 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
    原地堆排序
    原地堆排序

算法分析

  • 平均时间复杂度：O(nlogn)

  • 空间复杂度：O(1)

  • 不稳定排序

  • 原地排序

代码实现

1. 建堆
MaxHeap.java
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
public class MaxHeap <T extends Comparable<? super T>> {
    protected T[] data;
    protected int count;
    protected int capacity;

    public MaxHeap(int capacity){
        data=(T[])new Comparable[capacity+1];
        count=0;
        this.capacity=capacity;
    }

    public MaxHeap(T[] a){
        int n=a.length;
        data=(T[])new Comparable[n+1];
        this.capacity=n;
        for (int i=0;i<n;i++){
            data[i+1]=a[i];
        }
        count=n;

        for(int i=count/2;i>0;i--){
            ShiftDown2(i);
        }
    }

    public int size(){
        return count;
    }

    public boolean isEmpty(){
        return count==0;
    }
    
    public void insert(T a){
        assert (count+1<=capacity);
        data[++count]=a;
        ShiftUp(count);
    }

    private void ShiftUp(int k) {
        while(k>1 && data[k/2].compareTo(data[k])<0){
            swap(k/2,k);
            k/=2;
        }
    }

    public T extractMax(){
        assert (count>0);
        T max=data[1];
        swap(1,count);
        count--;
        ShiftDown2(1);
        return max;
    }
    // 原始的shiftDown过程
    private void ShiftDown(int k) {
        while(2*k<=count){
            int j=2*k; // data[k]和data[j]交换位置
            if(j+1<=count && data[j].compareTo(data[j + 1]) < 0) {
                j++;
            }
            if(data[k].compareTo(data[j])>0){
                break;
            }
            swap(k,j);
            k=j;
        }
    }
	// 优化的shiftDown过程, 使用赋值的方式取代不断的swap,
    private void ShiftDown2(int k) {
        T e=data[k];
        while(2*k<=count){
            int j=2*k; // data[k]和data[j]交换位置
            if(j+1<=count && data[j].compareTo(data[j + 1]) < 0) {
                j++;
            }
            if(e.compareTo(data[j])>0){
                break;
            }
            data[k]=data[j];
            k=j;
        }
        data[k]=e;
    }

    private void swap(int m,int n){
        T temp=data[m];
        data[m]=data[n];
        data[n]=temp;
    }

    public static void main(String[] args){
        MaxHeap<Integer> maxHeap=new MaxHeap<>(100);
        System.out.println(maxHeap.size());
        for(int i=0;i<15;i++){
            maxHeap.insert((int)(Math.random()*100));
        }
        for(int i=0;i<15;i++){
            System.out.print(maxHeap.extractMax()+" ");
        }
        System.out.println();
}
2. 基本堆排序
HeapSort1.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class HeapSort1 {
	// 不允许产生任何实例
    private HeapSort1(){}

    public static<T extends Comparable<? super T>>
    void sort(T[] a){
        int n=a.length;
        MaxHeap<T> maxHeap=new MaxHeap<>(n);
        for(int i=0;i<n;i++) {
            maxHeap.insert(a[i]);
        }
        for(int i=n-1;i>=0;i--) {
            a[i]=maxHeap.extractMax();
        }
    }

    public static void main(String[] args){
        int N = 100;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100);
        SortTestHelper.printArray(arr);
        SortTestHelper.testSort("algorithm.heap.HeapSort1", arr);
        SortTestHelper.printArray(arr);
    }
}
3. 优化堆排序
HeapSort2.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class HeapSort2 {
    // 不允许产生任何实例
    private HeapSort2(){}

    public static<T extends Comparable<? super T>>
    void sort(T[] a){
        int n=a.length;
        MaxHeap<T> maxHeap=new MaxHeap<>(a);

        for(int i=n-1;i>=0;i--) {
            a[i]=maxHeap.extractMax();
        }
    }
}
3. 原地堆排序
HeapSort.java
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
public class HeapSort {
    // 不允许产生任何实例
    private HeapSort(){}

    public static<T extends Comparable<? super T>>
    void sort(T[] a){
        int n=a.length;
        // 从第一个非叶子节点开始进行ShiftDown操作
        for(int i=(n-1-1)/2;i>=0;i--){
            ShiftDown2(a,n,i);
        }
        for(int i=n-1;i>0;i--){
            swap(a,0,i);
            ShiftDown2(a,i,0);
        }
    }

    private static<T extends Comparable<? super T>>
    void swap(T[] a, int i, int j) {
        T temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

    private static<T extends Comparable<? super T>>
    void ShiftDown1(T[] a, int n, int k) {
        while(2*k+1<=n-1){
            int j=2*k+1; // data[k]和data[j]交换位置
            if(j+1<=n-1 && a[j].compareTo(a[j + 1]) < 0) {
                j++;
            }
            if(a[k].compareTo(a[j])>0){
                break;
            }
            swap(a,k,j);
            k=j;
        }
    }

    private static<T extends Comparable<? super T>>
    void ShiftDown2(T[] a, int n, int k) {
        T e=a[k];
        while(2*k+1<=n-1){
            int j=2*k+1; // data[k]和data[j]交换位置
            if(j+1<=n-1 && a[j].compareTo(a[j + 1]) < 0) {
                j++;
            }
            if(e.compareTo(a[j])>0){
                break;
            }
            a[k]=a[j];
            k=j;
        }
        a[k]=e;
    }
}
-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！