常见排序算法

发表于 | 分类于

常见排序算法

一. 选择排序

在循环中，每次找到剩下数组中最小的元素，并将这个最小的元素与当前元素交换位置。最后，整个数组就是有序的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        //k记录最小元素的下标
        int k = i;
        //在剩下元素中找最小元素的下标
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[k]) {
                k = j;
            }
        }
        //如果最小元素不是自己，则交换位置
        if (k != i) {
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }
    System.out.println("selectSort:");
    for (int value : arr) {
        System.out.println(value);
    }
}

选择排序是最稳定的排序算法，哪怕是已经有序的数组进行选择排序的时间复杂度仍为O(n^2)，其不会利用数组的初始状态。空间复杂度为O(1)。

二. 插入排序

与选择排序一样，插入排序当前索引左侧的所有元素都是有序的，但他们的最终位置不确定。

对于当前元素current，取出上一个元素arr[preIndex]，如果上一个元素大于当前元素则将其移动到其下一个位置，重复此过程。这就相当于将current左侧比current大的元素全部右移一位，给current腾出位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void insertSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int preIndex = i - 1;
        //当前元素
        int current = arr[i];
        //如果上一个元素大于当前元素则将其右移一位，重复此过程
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        //将current插入到该腾出的位置
        arr[preIndex + 1] = current;
    }
    System.out.println("insertSort:");
    for (int value : arr) {
        System.out.print(value + " ");
    }
}

插入排序利用了初始数组部分有序的特点，因此适合于局部有序的情况。

平均时间复杂度为O(n^2)，对于已经有序的数组，时间复杂度为O(n)。空间复杂度为O(1)。

三. 希尔排序

希尔排序是基于插入排序的改进排序算法。对于大规模乱序数组，插入排序很慢，因为它只会移动相邻的元素。希尔排序为了加快速度改进了插入排序，交换不相邻的元素以对数组进行局部排序，并最终用插入排序对局部有序的数组进行排序。

设置h作为间隔，对于每个h，用插入排序将h个子数组进行独立的排序，只需将插入排序中移动元素的距离由1改为h即可。

希尔排序比插入排序高效的原因是其权衡了子数组的规模和有序性。排序之初，子数组都很小，排序后子数组是局部有序的，这都有利于插入排序。

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
private static void shellSort(int[] arr) {
    int n = arr.length;
    int h = 1;
    //h= 1, 4, 13, 40, 121, 364, 1093
    while (h < n / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        //将数组变为h有序
        for (int i = h; i < n; i++) {
            int preIndex = i - h;
            int current = arr[i];
            //将当前元素插入到arr[i-h]、arr[i-2*h]....中去
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + h] = arr[preIndex];
                preIndex -= h;
            }
            arr[preIndex + h] = current;
        }
        h /= 3;
    }
    for (int value : arr) {
        System.out.print(value + " ");
    }
}

在我个人本地随机数组测试中，当数据规模大于等于10000时，希尔排序比插入排序近似快了一倍，且随着数据规模的扩大，速度差距也跟着扩大。

希尔排序的平均复杂度为O(n^1.3)，最坏时间复杂度为O(n^2)，最好时间复杂度为O(n)，空间复杂度为O(1)。

四. 归并排序

归并排序是建立在归并基础上的排序算法。归并时将元素复制到辅助数组aux中，再把归并结果放回到原数组中。

自顶向下的归并排序

自顶向下的归并排序是分治思想的典型示例。要对子数组arr[left, right]进行排序，先将其分为arr[left...mid]和arr[mid+1...right]两部分，分别通过递归调用将他们单独排序，最后将排序好的子数组归并成最终的排序结果。

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
   //用到的辅助数组
static int[] aux;   

public static void mergeSort(int[] arr) {
       int n = arr.length;
       aux = new int[n];
       mergeSort(arr, 0, n - 1);
       for(int value:arr){
           System.out.print(value+" ");
       }
   }
   //进行排序
   private static void mergeSort(int[] arr, int left, int right) {
       //递归终止条件
       if (left >= right) {
           return;
       }
       int mid = left + (right - left) / 2;
       //将左半部分排序
       mergeSort(arr, left, mid);
       //将右半部分排序
       mergeSort(arr, mid + 1, right);
       //归并
       //当arr[mid] <= arr[mid + 1]时已经有序，可以跳过归并
       if (arr[mid] > arr[mid + 1]) {
           merge(arr, left, mid, right);
       }
   }

   private static void merge(int[] arr, int left, int mid, int right) {
       //i,j为两个指针，起始时分别指向两个已经排序序列的起始位置
       int i = left, j = mid + 1;
       //将需要归并部分复制到辅助数组
       for (int k = left; k <= right; k++) {
           aux[k] = arr[k];
       }
       for (int k = left; k <= right; k++) {
           //左半部分用尽，取右半部分元素
           if (i > mid) {
               arr[k] = aux[j++];
               //右半部分用尽，取左半部分元素
           } else if (j > right) {
               arr[k] = aux[i++];
               //左半部分的当前元素小于右半部分的当前元素
           } else if (aux[i] < aux[j]) {
               arr[k] = aux[i++];
               //左半部分的当前元素大于等于右半部分的当前元素
           } else {
               arr[k] = aux[j++];
           }
       }
   }

自底向上的归并排序

自底向上的归并排序使用的是迭代的形式，先归并小数组，再成对归并得到的子数组。

初始时设置步长sz为1，因为是成对归并，所以每次步长长度增长一倍即sz = sz + sz。

枚举数组左边界lo，lo从0开始，每次增长一对sz的大小，将这一对sz大小的区间进行归并。

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
public static void mergeSortIterator(int[] arr) {
    int n = arr.length;
    aux = new int[n];
    //步长增长一倍
    for (int sz = 1; sz < n; sz = sz + sz) {
        //子数组一对一对的归并
        for (int lo = 0; lo < n - sz; lo = lo + sz + sz) {
            //注意右边界要小于等于n-1
            merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, n - 1));
        }
    }
    for (int value : arr) {
        System.out.print(value + " ");
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int i = left, j = mid + 1;
    //将需要归并部分复制到辅助数组
    for (int k = left; k <= right; k++) {
        aux[k] = arr[k];
    }
    for (int k = left; k <= right; k++) {
        //左半部分用尽，取右半部分元素
        if (i > mid) {
            arr[k] = aux[j++];
            //右半部分用尽，取左半部分元素
        } else if (j > right) {
            arr[k] = aux[i++];
            //左半部分的当前元素小于右半部分的当前元素
        } else if (aux[i] < aux[j]) {
            arr[k] = aux[i++];
            //左半部分的当前元素大于等于右半部分的当前元素
        } else {
            arr[k] = aux[j++];
        }
    }
}

归并排序的时间复杂度为O(nlogn), 空间复杂度为O(n)。

在归并排序中使用了全局辅助数组aux，更好的做法是把aux作为mergeSort方法的局部变量，并把它作为参数每次传递给merge方法。

Wiki-归并排序

五. 快速排序

快速排序也是一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立的排序。快速排序与归并排序是互补的：归并排序将数组分成两部分分别排序，并将有序的子数组归并来将整个数组排序；而快速排序则是当两个子数组都有序时整个数组就有序了。归并排序的递归调用发生在处理整个数组之前；快速排序的递归调用发生在处理整个数组之后。

快速排序通过递归调用切分来排序。先排定一个基准元素，一般是arr[left]，然后从数组左端开始扫描直到找到一个比他大的元素，再从数组右端进行扫描直到找到一个比他小的元素。交换他们的位置，直到左右指针相遇，再将基准元素与相遇位置的元素交换位置。

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 static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        System.out.println("quickSort:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        //切分
        int j = partition(arr, left, right);
        quickSort(arr, left, j - 1);
        quickSort(arr, j + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        //i，j为左右扫描指针
        int i = left;
        int j = right + 1;
        //key为基准元素
        int key = arr[left];
        while (true) {
            //向右扫描直到遇到一个大于等于基准的元素
            while (arr[++i] < key) {
                if (i == right) {
                    break;
                }
            }
            //向左扫描直到遇到一个小于等于基准的元素
            while (arr[--j] > key) {
                if (j == left) {
                    break;
                }
            }
            //指针相遇时结束
            if (i >= j) {
                break;
            }
            //交换i，j位置
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //交换基准元素与相遇时元素位置
        int temp = arr[left];
        arr[left] = arr[j];
        arr[j] = temp;
        return j;
    }

快速排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)，空间复杂度为O(nlogn)。

六. 堆排序

堆是一种近似二叉树的结构，一般用一维数组表示，且子节点的键值或索引总小于(或者大于)他的父节点。若按升序排列，则把数组换成最大堆。重复从最大堆取出数值最大的结点(把根结点和最后一个结点交换，把交换后的最后一个结点移出堆)，并让残余的堆维持最大堆性质。

对于起始索引为0的数组来说，节点索引为i的节点：

  • 左子节点为2*i+1；
  • 右子节点为2*i+2;
  • 父节点为floor((i-1)/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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
   public static void heapSort(int[] arr) {
       int len = arr.length - 1;
       //将数组堆化， beginIndex为第一个非叶子节点索引，叶子节点可以看成满足堆结构的节点
       int beginIndex = (arr.length >> 1) - 1;
       for (int i = beginIndex; i >= 0; i--) {
           maxHeapify(i, len, arr);
       }
       //对堆化数据排序
       //每次都移出最顶层的根节点与最尾部节点进行交换，同时遍历长度减一
       //然后重新整理被交换到根节点的元素进行下沉操作使其满足堆的结构
       //直到未排序堆的长度为0
       for (int i = len; i > 0; i--) {
           int temp = arr[0];
           arr[0] = arr[i];
           arr[i] = temp;
           maxHeapify(0, i - 1, arr);
       }
       System.out.println("HeapSort:");
       for (int value : arr) {
           System.out.print(value + " ");
       }
   }
//调整索引为index处的元素，使其满足堆结构，len为未排序堆的长度
   private static void maxHeapify(int index, int len, int[] arr) {
       //左子节点索引
       int li = (index << 1) + 1;
       //右子节点索引
       int ri = li + 1;
       //左子节点超出计算范围
       if (li > len) {
           return;
       }
       //子节点最大值索引，初始默认为左节点
       int maxIndex = li;
       if (ri <= len && arr[li] < arr[ri]) {
           maxIndex = ri;
       }
       //如果子节点最大值大于父节点，交换，并继续递归调用直到满足堆结构
       if (arr[maxIndex] > arr[index]) {
           int temp = arr[index];
           arr[index] = arr[maxIndex];
           arr[maxIndex] = temp;
           maxHeapify(maxIndex, len - 1, arr);
       }
   }

堆排序的时间复杂度为O(nlogn)。

-------------本文结束感谢您的阅读-------------