算法篇-排序算法

时间复杂度

image.png

稳定性：当序列中存在两个或两个以上的关键字相等的时候，如果排序前序列中1领先于2,那么排序后1如果仍旧领先2的话，则是稳定的。（相等的元素排序后相对位置不变）

不稳定性：当序列中存在两个或两个以上的关键字相等的时候，如果排序前序列中1领先于2,那么排序后1如果落后2的话，则是不稳定的。（相等的元素排序后相对位置发生改变）

时间复杂度：T(n)=O(f(n))

渐进时间复杂度（asymptotic time complexity）的概念，官方的定义如下：
若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。
记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。

如何推导出时间复杂度呢？有如下几个原则：
1.如果运行时间是常数量级，用常数1表示；
2.只保留时间函数中的最高阶项；
3.如果最高阶项存在，则省去最高阶项前面的系数。

常数阶O(1) < 对数阶O(logN) < 线性阶O(n) < 线性对数阶O(nlogN) < 平方阶O(n²) < 立方阶O(n³) < K次方阶O(n^k) < 指数阶(2^n)

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)

空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

举例

1
2
3
4
5
6
7
8
9
10

class Solution{
    public static void main(String[] args) {
        int i = 1;
        int j = 2;
        ++i;
        j++;
        int m = i + j;
    }
}

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

空间复杂度 O(n)

举例

我们先看一个代码：

1
2
3
4
5
6
7
8
9
class Solution{
    public static void main(String[] args) {
        int[] m = new int[n];
        for(i=1; i<=n; ++i){
            j = i;
            j++;
        }
    }
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

快速排序 O(nlogn)

1.选择基准(一般取第一个)
2.从右往左查找比基准小的数，进行位置交换
3.从左往右查找比基准大的数，进行位置交换
4.重复执行2、3直到比较完成
5.分别对两边重复执行1-4

双边循环排序法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Sort {
    public static void quicksort(int[] arr,int left,int right){
        if (left < right) {
            int low = left, height = right, x = arr[left];
            while (low < height)
            {
                while(low < height && arr[height] >= x) // 从右向左找第一个小于x的数
                    height--;
                if(low < height)
                    arr[low++] = arr[height];

                while(low < height && arr[low] < x) // 从左向右找第一个大于等于x的数
                    low++;
                if(low < height)
                    arr[height--] = arr[low];
            }
            arr[low] = x;
            quicksort(arr, left, low - 1); // 递归调用
            quicksort(arr, low + 1, right);
        }
    }
}

单边循环排序法

1
//TODO:

非递归方式实现

1
//TODO:

随机基准实现

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
class Solution {
    //函数入口
    public int[] sortArray(int[] nums) {
        randomizedQuicksort(nums, 0, nums.length - 1);
        return nums;
    }

    public void randomizedQuicksort(int[] nums, int l, int r) {
        if (l < r) {
            int pos = randomizedPartition(nums, l, r);
            randomizedQuicksort(nums, l, pos - 1);
            randomizedQuicksort(nums, pos + 1, r);
        }
    }
    //随机分区
    public int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    public int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

插入排序

1.分为有序和无序两段数组
2.从无序中取第一个数插入有序半段中的适合位置
3.重复执行2步骤直到无序数组为长度为零

T(n)=O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Sort{
    public static void straightInsertSort(int[] arr){
        int j = 0;
        int tmp = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]<arr[i-1]){//插入i-1前面
                tmp = arr[i];
                for (j = i - 1; j >= 0 && tmp < arr[j]; j--) {
                    arr[j+1] = arr[j];
                }
                arr[j+1] = tmp;
            }
        }
    }
}

选择排序

1.在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；

2.第二次遍历n-2个数，找到最小的数值与第二个元素交换；

3.第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Sort{
        public static void selectSort(int[] arr){
            int min;
            for (int i = 0; i < arr.length; i++) {
                min=arr[i];
                for (int j = i+1; j <arr.length; j++) {
                    if (arr[j]<min){
                        int tmp = arr[i];
                        min=arr[j];
                        arr[i]=arr[j];
                        arr[j]=tmp;
                    }
            }
       }
   }
}

希尔排序

基本思想：
在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

数据序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1;
数据序列2： 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3;
如果数据序列基本有序，使用插入排序会更加高效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Sort{
    public static void shellSort(int[] arr){

        int incre = arr.length;

        while (true){
            incre = incre>>1;
            for (int i = 0; i < incre; i++) {
                for (int j = i; j <arr.length ; j+=incre) {
                    for (int k = j; k >i ; k-=incre) {
                        if (arr[k]<arr[k-incre]){
                            int tmp = arr[k];
                            arr[k-incre]=arr[k];
                            arr[k]=tmp;
                        }else break;
                    }
                }
            }
            if (incre==1)break;
        }
    }
}

冒泡排序

基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。

过程：

比较相邻的两个数据，如果第二个数小，就交换位置。
从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
继续重复上述过程，依次将第2.3…n-1个最小数排好位置。

时间复杂度: T(n)=O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Sort{
public static void BubbleSort(int [] arr){

     int temp;//临时变量
     for(int i=0; i<arr.length-1; i++){   //表示趟数，一共arr.length-1次。
         for(int j=arr.length-1; j>i; j--){

             if(arr[j] < arr[j-1]){
                 temp = arr[j];
                 arr[j] = arr[j-1];
                 arr[j-1] = temp;
             }
         }
     }
 }
}

归并排序

平均时间复杂度：O(NlogN)

基本思路:

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

归并排序的效率是比较高的，设数列长为 N，将数列分开成小数列一共要 logN 步，每步都是一个合并有序数列的过程，时间复杂度可以记为 O(N)，故一共为 O(N_logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在 O(N_logN) 的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

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 Sort{
    /**
    *程序入口
    * @param arr
    */
    void MergeSort(int[] arr){
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
    }
    /**
    * 递归
    * @param a
    * @param first
    * @param last
    * @param temp
    */
    public static void mergeSort(int[] a, int first, int last, int[] temp) {
        if (first < last) {
            int mid = (first + last) / 2;
            mergeSort(a, first, mid, temp);
            mergeSort(a, mid + 1, last, temp);
            mergeArray(a, first, mid, last, temp);
        }
    }
    /**
    * 合并数组
    * @param a
    * @param first
    * @param mid
    * @param last
    * @param temp
    */
    private static void mergeArray(int[] a, int first, int mid, int last, int[] temp) {
        int i = first, j = mid + 1;
        int m = mid, n = last;
        int k = 0;
        while (i <= m && j <= n) {
            if (a[i] <= a[j]) temp[k++] = a[i++];
            else temp[k++] = a[j++];
        }
        while (i <= m) temp[k++] = a[i++];
        while (j <= n) temp[k++] = a[j++];
        for (int l = 0; l < k; l++) a[first + i] = temp[i];
    }
}

堆外排序

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

原文链接
预备知识
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。
堆
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
image.png
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
image.png
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：
堆排序基本思想及步骤

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

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
a.假设给定无序序列结构如下
image.png
2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
image.png
4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
image.png
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
image.png
此时，我们就将一个无需序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换
image.png
b.重新调整结构，使其继续满足堆定义
image.png
c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
image.png
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
image.png
再简单总结下堆排序的基本思路：
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

代码实现

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;

/**
 * 堆排序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;
    }
}

结果

1
[1, 2, 3, 4, 5, 6, 7, 8, 9]

最后

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

桶外排序 O(n+k)

桶排序的基本思想是: 把数组 arr 划分为 n 个大小相同子区间(桶),每个子区间各自排序,最后合并 。计数排序是桶排序的一种特殊情况,可以把计数排序当成每个桶里只有一个元素的情况。

1.找出待排序数组中的最大值 max、最小值 min（用于计算需要多少个桶）
2.我们使用 动态数组 ArrayList 作为桶,桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
3.遍历数组 arr,计算每个元素 arr[i] 放的桶，(arr[i] - min) / (arr.length)
4.每个桶各自排序
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    /**
     * 桶排序
     * @param arr
     */
        public static void bucketSort(int[] arr){
        // 计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        // 计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        List<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<>());
        }
        // 将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            //计算其在哪个桶中
            //1,3,4,9 （9-1）/4+1=3个桶
            //1-1/4= 0 在第0个桶
            //3-1/4 = 0 在第0个桶
            //4-1/4 = 0 在第0个桶
            //9-1/4 = 2 在第2个桶
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
        // 对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }
        // 将桶中的元素赋值到原序列
        int index = 0;
        for(int i = 0; i < bucketArr.size(); i++){
            for(int j = 0; j < bucketArr.get(i).size(); j++){
                arr[index++] = bucketArr.get(i).get(j);
            }
        }
    }
}

计数排序 O(n+k)

思路： 把每个出现的数值都做一个计数，然后根据计数从小到大输出得到有序数组。

代码实现

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
public class Solution {

    // 计数排序

    private static final int OFFSET = 50000;

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        // 由于 -50000 <= A[i] <= 50000
        // 因此"桶" 的大小为 50000 - (-50000) = 10_0000
        // 并且设置偏移 OFFSET = 50000，目的是让每一个数都能够大于等于 0
        // 这样就可以作为 count 数组的下标，查询这个数的计数
        int size = 10_0000;

        // 计数数组
        int[] count = new int[size];
        // 计算计数数组
        for (int num : nums) {
            count[num + OFFSET]++;
        }

        // 把 count 数组变成前缀和数组
        for (int i = 1; i < size; i++) {
            count[i] += count[i - 1];
        }

        // 先把原始数组赋值到一个临时数组里，然后回写数据
        int[] temp = new int[len];
        System.arraycopy(nums, 0, temp, 0, len);

        // 为了保证稳定性，从后向前赋值
        for (int i = len - 1; i >= 0; i--) {
            int index = count[temp[i] + OFFSET] - 1;
            nums[index] = temp[i];
            count[temp[i] + OFFSET]--;
        }
        return nums;
    }
}

基数排序

将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

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
class Solution{
public void radixSort(int a[]) {
        sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    public void sort(int[] array) {
        //首先确定排序的趟数;
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        int time = 0;
        //判断位数;
        while (max > 0) {
            max /= 10;
            time++;
        }
        //建立 10 个队列;
        List<ArrayList> queue = new ArrayList<ArrayList>();
        for (int i = 0; i < 10; i++) {
            ArrayList<Integer> queue1 = new ArrayList<Integer>();
            queue.add(queue1);
        }
        //进行 time 次分配和收集;
        for (int i = 0; i < time; i++) {
        //分配数组元素;
            for (int j = 0; j < array.length; j++) {
        //得到数字的第 time+1 位数;
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue2 = queue.get(x);
                queue2.add(array[j]);
                queue.set(x, queue2);
            }
            int count = 0;//元素计数器;
            //收集队列元素;
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    ArrayList<Integer> queue3 = queue.get(k);
                    array[count] = queue3.get(0);
                    queue3.remove(0);
                    count++;
                }
            }
        }
    }
}

参考资料

经典排序算法全攻略

基础算法 > 算法笔记
#算法
算法篇-排序算法
https://mikeygithub.github.io/2019/07/25/yuque/算法篇-排序算法/
作者
Mikey
发布于
2019年7月25日
许可协议