排序算法

Posted on | In | 次阅读

今日复习任务：实现数据从小到大的排序方式，分别有冒泡、选择、插入、快排、归并

冒泡排序

思想：大的数往往上冒，每遍历一次，后面的几位是排好顺序的。第一次遍历得到最大的数，在末尾，第二次遍历，次大的数在倒数第二位，需要遍历n-1次，所有的才能排好顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
 /**
 * @Description 冒泡排序
 * TODO 时间复杂度 O(n^2)
 **/
public static void maoPaoSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j+1);
            }
        }
    }
}

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @Description 优化的冒泡排序
* TODO 性能优化 对于已经排好序的部分，直接退出外部循环，因为存在重复比较。
**/
public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean isOrder = true;
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                isOrder = false;
            }
        }
        if (isOrder) {
            break;
        }
    }
}

由于有大量的重复比较，在每次比较的时候，用一个变量标识表示这轮遍历是否都已经排好顺序了，如果都排好顺序了，就直接跳出循环。可想而知，当排好序的情况下，是最好的情况，时间复杂度为O(n)。最坏情况是O(n^2),对于同样大小的数是不需要移动的，可以保证之前的顺序，所以是稳定的。

选择排序

思想：有点类似冒泡，每次也是得到一个排好顺序的位置。选择一个数，逐个跟其他的比较大小。比如，取第一个，如果有比它小的数，则交换位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @Description 选择排序
 * TODO 最好,最坏，平均的情况 都是 n^2 【不稳定】
 **/
public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                swap(arr, i, j);
            }
        }
    }
}

选择排序不管是有序无序都会进行选择比较，因此时间复杂度都是O(n^2)，为什么不是稳定的？

因为每次比较都可能会交换问题，比如3，2，2，1，1，相邻的两个2在第一轮遍历的时候顺序就打乱了。

插入排序

思想：把元素分为两部分，前部分是排好队的部分，后部分是还没有排好队的，当第一次遍历时，第一个元素是排好队的，第二个及之后的元素是需要插入到前面的，所以每次遍历的时候，拿第i+1个元素与前面的元素逐个比较，如果小于，交换元素。指针j继续往前移动，直到arr[i]大于arr[j]或者j<=0

1
2
3
4
5
6
7
8
9
10
11
/**
 * @Description 插入排序
 * TODO 时间复杂度 O(n^2) 最坏O(n^2)  最好 O(n) 稳定 
 **/ 
public static void chaRuSort(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j > 0 && arr[j - 1] > arr[j]; j--) {
            swap(arr, j - 1, j);
        }
    }
}

优化

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @Description 插入排序
 * TODO 最好的情况 n^2,最坏的情况，n^2,平均情况 n^2 【稳定】 
 **/
public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        for (int j = i - 1; j >= 0 && key < arr[j]; j--) {
            swap(arr, j + 1, j);
        }
    }
}

原理是一样的，更加容易理解一些，并且性能更好，因为每次比较的时候可以利用局部性缓存原理。

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @Description 插入排序
 * TODO 对swap方法的优化，避免多次数据的赋值交换
 **/
public static void insertSort_improve(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j;
        for (j = i - 1; j >= 0 && arr[j] > key; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = key;
    }
}

跟前一种思想一样，只是没有使用swap方法了，前面遍历，移动位置，最后找到key应该插入的位置，赋值就OK。

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @Description 插入排序
 * TODO 避免不必要的重复，最好情况下时间复杂度为 O(n)
 **/
public static void insertSortImprove(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        for (int j = i - 1; j >= 0; j--) {
            if (key < arr[j]) {
                swap(arr, j + 1, j);
            } else {
                break;
            }
        }
    }
}

避免不必要的重复比较，如果一开始比较比前面的数小，那直接跳出本次内部循环。

快速排序

思想：选择一个哨兵，以这个为基准，对剩余的元素进行比较，小的排左边，大的排右边。当进行完一次遍历后，找到了当前哨兵所应该在的位置。然后对左右两部分递归，选择各自的哨兵，进行排序，当排完之后，就是有序的了。

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
/**
 * @Description 快速排序
 * TODO 使用分而治之的思想,平均时间复杂度为O(nlgn)  不稳定，交换有点类似选排
 *    最坏的情况是选到的哨兵两个极端（最大值/最小值），导致O(n^2)
 **/
public static void quick_sort(int[] arr) {
    quick_Sort(arr, 0, arr.length - 1);

}

private static void quick_Sort(int[] arr, int min, int max) {
    if (max > min) {
        int partIndex = partition(arr, min, max);
        quick_Sort(arr, min, partIndex - 1);
        quick_Sort(arr, partIndex + 1, max);
    }

}


private static int partition(int[] arr, int min, int max) {
    int key = arr[min];

    while (max > min) {
        while (max > min && arr[max] >= key) {
            max--;
        }
        // 将从右往左数比哨兵第一小的数赋值给左侧第一个数
        arr[min] = arr[max];

        while (max > min && arr[min] <= key) {
            min++;
        }
        // 将从左往右数第一个比哨兵大的数，赋值给max处的下标，再比较min与max的大小
      	// 进入下一次循环，直到min=max
        arr[max] = arr[min];
    }
    arr[max] = key;
    return max;
}

程序有两处容易犯错的地方，第一处是quick_Sort()方法的递归调用，调用外部递归是因为，每次要使的左右两边有序。第二处是partition()方法有两处while循环，当内部循环之后，两处的交换赋值，需要注意。

快排的平均时间复杂度为O(nlogn)，对于排好序（升序或者倒序）的数组，表现的性能最差，因为每次遍历，选择到的哨兵是最大的或者最小的，导致每次遍历完，左侧的要么全是最大的或是最小的，导致没有二分的效果，时间复杂度接近于O(n^2)。

为了避免这种情况，重点在于选择哨兵的方法，我们可以选择数组的中间的那个数做哨兵，也能使用随机数选择，避免出现最快的情况。

三位数取中

1
2
int index = (min + max) / 2;
int key = arr[index];

随机选择哨兵

1
2
3
Random random = new Random(47);
int index = random.nextInt(max - min) + min;
int key = arr[index];

归并排序

思想：使用分而治之的思想，对一个大的任务分解成多个子任务，进行处理，将子任务处理完得到的解合并，就是所求问题的解。在归并排序中，将带排序的元素分成大小大致相同的两个子集合，分别对子集合进行排序（其实对子集合排序很简单，再对子集合进行分，分，分，直到分成单个元素，然后将单个元素进行从小到大合并，得到的就是有序的子集合），最终将排好序的子集合合并成所要排好序的集合。

其分而治之思想实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @return void
 * @Author chenjianrong-lhq
 * @Description 平均时间复杂度 nlogn 稳定
 * @Date 2020-04-05 18:26
 * @Param [arr, left, right]
 **/
public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int middle = (left + right) >> 1;
        mergeSort(arr, left, middle);                   // 分
        mergeSort(arr, middle + 1, right);
        merge(arr, left, middle, right);                // 治、合
    }
}

上面一步很容易理解，也有点类似快排。其重要的实现在于将单个元素进行从小到大合并，其中间的过程会产生多个有序的子集合，因为涉及到递归，必会开辟多个栈空间进行方法的运算和存储，所以相比于非递归，递归算法的运算效率较低，在计算时间上和占用空间上都差于非递归实现。当然，可以想一想如何消除递归，用非递归方法实现归并排序？

将单个元素进行从小到大合并实现，可以简单的抽象为有两个排好序的长度为n/2数组，现在要按照从小到大组合成长度为n的数组，这组合的过程中要考虑多个不同的情况，共以下三 种：

  1. 左边的数全部比右边小

  2. 右边的数全部比左边的小

  3. 左边的数有比右边的小，也有比右边的大的（这个时候先取小的，再遍历比较）

具体 实现如下：

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
private static void merge(int[] arr, int low, int middle, int high) {
    // 定义组合后的数组
    int[] temp = new int[arr.length];
    // 组合数组的下标标识
    int k = low;
    
    // 左部分的开始下标
    int i = low;
    // 右部分的开始下标
    int j = middle + 1;
    
    // 从左至右开始遍历
    for (int m = low; m < high; m++) {
        if (m > middle) {
            // 表示左边元素已经处理
            temp[k] = arr[j];
            k++;
            j++;
        } else if (j > high) {
            // 表示右边的元素已经处理
            temp[k] = arr[i];
            k++;
            i++;
        } else if (arr[i] > arr[j]) {
            // 表示左边的数大于右边，取右边
            temp[k] = arr[j];
            k++;
            j++;
        } else {
            // 表示左边的数小于右边，取左边
            temp[k] = arr[i];
            k++;
            i++;
        }
    }
    // 数组的拷贝
    for (int n = 0; n < temp.length; n++) {
        arr[n] = temp[n];
    }
}

总结

以上几种排序是我们最熟悉的排序，也是面试时候经常会问到的排序，理解每种排序的思想远远比记住代码更重要。

最后我们总结归纳：

稳定的排序有三种：冒泡、插入、归并

在已经排好序的情况下 ，应该选择哪几种排序：优化的冒泡、插入