常见的排序算法_14.请写出长度为len顺序表a的比较排序伪算法?

常见的排序算法|

关于空间复杂度：冒泡、选择、插入、希尔空间复杂度为O(1)
快排空间复杂度为logn（递归）
基数排序、归并排序空间复杂度为O(n)

冒泡排序

基本思想：俩个数比较大小，大的下沉，小的上浮
冒泡排序的过程想必大家都很清楚了，直接上代码
可食用代码—java版

private static void BubbleSort(int[] arr) {
   
        for (int i = 0; i < arr.length - 1; i++) {
   
            for (int j = arr.length - 1 - i; j > 0; j--) {
   
                if (arr[j] < arr[j - 1]) {
   
                    int tem = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tem;
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

上面就是冒泡排序最简单的做法，但是如果中间某一时刻已经有序了，该算法仍然会继续进行直到比较length次停止。
优化：设置标记flag，如果发生交换则设为true，否则排序结束

private static void BubbleSort_Better(int[] arr) {
   
        boolean flag;
        for (int i = 0; i < arr.length - 1; i++) {
   
            flag = false;//初始化标记
            for (int j = arr.length - 1 - i; j > 0; j--) {
   
                if (arr[j] < arr[j - 1]) {
   
                    int tem = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tem;
                    flag = true;
                }
            }
            if (!flag) {
   
                break;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

适用场景：较少元素时

选择排序

基本思想
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

就是每次找第i小的并交换，直接上代码。

private static void SelctionSort(int[] arr) {
   
        for (int i = 0; i < arr.length; i++) {
   
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
   
                if (arr[j] < arr[min]) {
   
                    min = j;
                }
            }
            if (min != i) {
   
                int tem = arr[min];
                arr[min] = arr[
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15