数据结构-----排序的概念、常见排序的实现以及排序算法的特点、非比较排序、排序相关例题

1. 排序的概念及引用

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 排序运用

1.3 常见的排序算法

2. 常见排序算法的实现

2.1 插入排序

2.1.1基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。

2.1.2 直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

具体步骤如下：

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5，直到所有元素都排序完毕。

【代码】：

	public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];//需要插入到有序序列的数据
            int j = i - 1;
            for (; j >= 0; j--) {
                //这里加不加等号 和稳定性有关
                //本身时一个稳定的排序，可以实现为不稳定的排序
                //本身是一个不稳定的排序，是不可能变成一个稳定的排序的
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    // array[j + 1] = tmp;
                    break;
                }
            }
            //当j为-1时，循环结束后，将tmp插入1的位置
            //找到已排序的元素小于或等于tmp的位置,将tmp插入到该位置后面的位置。
            array[j + 1] = tmp;
       }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2.1.3 希尔排序( 缩小增量排序 )

希尔排序法又称缩小增量法。希尔排序法的基本思想是：

先选定一个整数gap，把待排序文件中所有记录分成多个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取下一个整数gap，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

【代码】：

 	public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap >= 1) {
            gap = gap >> 1;
            sort(array, gap);
        }
    }

    /**
     * 对每组进行间隔为gap的插入排序
     * @param array
     * @param gap
     */
    public static void sort(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) { //使每组交替进行插入排序
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
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

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：
   

因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照： $O(n^{1.25}）$ 到 $O(1.6\ast n^{1.25})$来算。
4. 稳定性：不稳定

2.2 选择排序

2.2.1基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

2.2.2 直接选择排序:

具体步骤如下：

1. 在元素集合array[i]- - -array[n-1]中选择关键码最大(小)的数据元素
2. 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
3. 在剩余的array[i]- - -array[n-2]（array[i+1]- - -array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

【代码】：

    private static void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] =  array[y];
        array[y] = tmp;
    }

    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i +1 ; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

在直接选择排序的基础上，可以延伸出来一种双向选择排序，同时确定两个值的位置，分别是最大值和最小值，然后将它们分别放在数组的起始和末尾位置。这样可以减少排序的比较次数，提高排序的效率。

双向选择排序的实现步骤如下：

1. 设置两个指针，一个指向数组的起始位置，一个指向数组的末尾位置。
2. 在每一轮排序中，分别找到当前范围内的最小值和最大值，并将它们分别放在起始位置和末尾位置，如果最大元素的索引 maxIndex 恰好等于左边界 left，说明最大元素原本在最小元素的位置，交换后它已经移动到 minIndex 的位置，因此需要将最大元素的索引更新为 minIndex。
3. 缩小排序范围，起始指针向右移动一位，末尾指针向左移动一位。
4. 重复步骤2和步骤3，直到起始指针大于或等于末尾指针。

【代码】：

    //    双向选择排序
    public static void selectSortPlus(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array, left, minIndex);
            //当最大值为左边界时，要交换的下标应该为上一步交换之后的minIndex（把最大值换到了刚刚最小值的位置）
            if (maxIndex == left) {
                swap(array, right, minIndex);
            } else {
                swap(array, right, maxIndex);
            }
            left++;
            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

双向选择排序的特性总结：

1. 虽然它比普通选择排序效率稍高，但在大规模数据集上仍然不够高效，通常不推荐在实际应用中使用。
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

2.2.3 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。基本思想是将待排序的元素构建成一个最大堆或最小堆，然后逐步将堆顶元素与堆尾元素交换，并重新调整堆，直到所有元素都被排序。需要注意的是排升序要建大堆，排降序建小堆。

排序过程，总共分为两个步骤：

1. 建堆：将待排序的元素依次插入到一个空堆中，或者将待排序的数组调整为一个堆结构。
   升序：建大堆
   降序：建小堆
2. 利用堆删除思想来进行排序
   将堆顶元素与堆尾元素交换位置，然后重新调整堆，使得剩余元素重新构成一个堆。
   

【代码】：

    //堆排序
    public static void heapSort(int[] array) {
        initHeap(array);
        int end = array.length - 1;
        while (end != 0) {
            swap(array, 0, end);
            shiftDown(array, 0,end);
            end--;
        }
    }

    //构建堆
    private static void initHeap(int[] array) {
        for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(array, i, array.length);
        }
    }

    //向下调整
    private static void shiftDown(int[] array, int parent,int size) {
        int child = parent * 2 + 1;
        while (child < size) { //说明至少有一个孩子
            if (child + 1 < size && array[child] < array[child + 1]) {//存在右孩子，并且右孩子大于左孩子的值
                child = child + 1;//更新child的值，指向两个孩子中的较大值
            }
            if (array[parent] < array[child]) {
                swap(array, child, parent);
                //更新父节点和孩子结点
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }
    private static void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }
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

【堆排序的特性总结】

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

2.3 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复地进行这个过程直到没有需要交换的元素，这样最大的元素就会“浮”到最后，最小的元素会“沉”到最前。

具体步骤如下：

1. 从序列的第一个元素开始，依次比较相邻的两个元素，比较过程中较大（或较小）的元素会逐渐“浮”到序列的右端（或左端）。
2. 如果当前元素大于（或小于）它的下一个元素，交换这两个元素的位置，使较大（或较小）的元素“浮”到右端（或左端）。
3. 继续进行相邻元素的比较和交换，直到整个序列的最右端（或最左端）已经排序完成。
4. 重复以上步骤，每次遍历时，序列的未排序部分长度减1，直到整个序列排序完成。

【代码】：

   public static void bubbleSort(int[] array) {
       	//i代表的是趟数
        for (int i = 0; i < array.length - 1; i++) {
			//j来比较每个数据的大小
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
    }
    private static void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

冒泡排序方法当数据量较大时效率较低，因此可以对其进行一些优化，以提高排序的效率。设置标志位：在每一轮遍历中，设置一个标志位，如果标志没有被改变，说明本轮没有发生元素交换，则说明列表已经有序，可以提前结束排序。

【代码】：

   public static void bubbleSortPlus(int[] array) {
   		//i代表的是趟数
        for (int i = 0; i < array.length - 1; i++) {
        	//设置标志
            boolean flag = false;
            //j来比较每个数据的大小
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    //当发生交换时，就将标志设置为true
                    flag = true;
                }
            }
            //flag为false时，没有发生交换，可以提前结束排序
            if(!flag) {
                break;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

【冒泡排序的特性总结】
4. 冒泡排序是一种非常容易理解的排序
5. 时间复杂度：冒泡排序的时间复杂度为O(N^2)，其中N是待排序序列的长度。在最坏情况下，即序列是逆序的情况下，冒泡排序需要进行N-1次遍历，每次遍历需要比较和交换相邻元素。如果加了优化之后：最好的情况下，可以达到O（n）
6. 空间复杂度：O(1)
7. 稳定性：稳定。相等元素的相对顺序不会被改变，只有相邻元素之间的比较和交换。

2.3.2 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

具体步骤如下：

1. 选择一个基准元素（pivot），通常选择数组的第一个元素。
2. 分区操作：将数组中小于基准值的元素移到基准值的左边，将大于基准值的元素移到基准值的右边，基准值所在位置就是最终排序后的位置。
3. 对基准值左右两边的子数组分别进行快速排序，直到子数组的长度为1或0，排序完成。
4. 合并结果：将所有子数组的结果合并起来，得到最终排序好的数组。

 /**
     * 时间复杂度：
     *      最好情况:
     *              O(N*logN)   满二叉树/完全二叉树
     *      n--->n    分后，左n/2+右n/2--->n    
     *      分后，左的左n/4+左的右n/4 + 右的左n/4+右的右n/4--->n
     *      最坏情况:
     *            	O(N^2) 单分支的树，每个元素都会当一次基准
     * 空间复杂度：
     *   	最好情况:
     *         	 	O(logN)   满二叉树/完全二叉树，为二叉树的高度
	 *      最坏情况:
     *         		O(N)   单分支的树，高度为N
     * 稳定性：不稳定
     * 
     * @param array
     */
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int[] array, int left, int right){
    if(left >= right)
        return;
    
    // 按照基准值对array数组的 [left, right)区间中的元素进行划分
    int div = partion(array, left, right);
    
    // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
    // 递归排[left, div]
    QuickSort(array, left, div);
    
    // 递归排[div+1, right]
    QuickSort(array, div+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

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

将区间按照基准值划分为左右两半部分的常见方式有：

1. Hoare版

    private static int partition1(int[] array, int i, int j) {
        int left = i;
        int right = j;
        //以第一个元素为基准，对数组进行划分
        int pivot = array[left];

        while (left < right) {
            //从后向前找到比pivot小的值
            while (left < right && array[right] >= pivot) {
                right--;
            }
            //从前向后找到比pivot大的值
            while (left < right && array[left] <= pivot) {
                left++;
            }
            //将两个值进行交换
            swap(array, left, right);
        }
        //再将基准值放到（left = right）结束的位置上
        swap(array, i, left);
        return left;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2. 挖坑法

【代码】：

    private static int partition2(int[] array, int i, int j) {
        int left = i;
        int right = j;
        int pivot = array[i];
        while (left < right) {
            while (left < right && array[right] >= pivot) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= pivot) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;
        return pivot;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

相关问题：

1. “这里为什么要取等号？”：
   拿我们图里面的例子来说，如果最开始的right是 6 ，那么就一直 6 和 6 交换：
   array[right] 为6，不满足大于临时变量 key的情况，将6覆盖到left指向的位置，right指向的位置形成一个坑位，之后array[left]=6,不满足小于临时变量key的情况，将6覆盖到right指向的位置，left指向的位置形成一个坑位，此时代码会陷入死循环。
2. 为什么从右边开始，而不是从左边开始？
   从左边开始，left会指向大于key的值停下来，如果left和right相遇，将key和相遇的值进行交换，那么会把大于key的值放到最前。这样就不能确保在基准值前面的都比其小，在其后面的都比其大。

3. 前后指针
   

【代码】：

    private static int partition3(int[] array, int left, int right) {
        int prev = left;
        int cur = left+1;
        while (cur <= right) {
            //prev指向下一个值为大于pivot的值时停止，当cur指向小于pivot的值，并且prev的下一个值不是cur时，交换两个值，并同时向后移一位
            if(array[cur] < array[left] && array[++prev] != array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,left,prev);
        return prev;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.3.2 快速排序优化

快速排序采用了分治的思想，对于快速排序的优化的出发点就是减少递归次数，实现均匀分割数组：

1. 三数取中法选key：在选择基准值时，不再简单地选择第一个元素作为基准值，而是选择数组中间的元素、第一个元素和最后一个元素中的中间值作为基准值，将中间值和第一个元素进行交换，再以该值进行快速排序，可以减少极端情况，降低树的高度，就这样可以减少最坏情况的出现概率，提高排序效率。
2. 插入排序优化：对于小规模的子数组（此时数据趋于有序），可以采用插入排序来代替快速排序，这样可以减少递归的层次，提高排序效率。

    //快速排序优化：1.三个数的中位数为基准值
    //           2.在较小的子区间内使用直接插入排序（此时已经基本上有序了，适用于直接插入排序)

    public static void quickSortPlus(int[] array, int left, int right) {
        if (left > right) {
            return;
        }

        //当子区间较小时，使用直接插入排序
        if (right - left + 1 <= 15) {
            insertSort(array, left, right);
        } else {
            //按照基准值对array数组中的元素进行划分
            int div = partitionPlus(array, left, right);//划分之后的中间值的下标
            //划分成功以后，以div为界限，把数组划分成了两部分[left,div-1]和[div+1,right]
            //递归排序[left,div-1]
            quickSort1(array, left, div - 1);
            //递归排序[div+1,right]
            quickSort1(array, div + 1, right);
        }
    }

    //插入排序
    private static void insertSort(int[] array, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (tmp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
           	}
            array[j + 1] = tmp;
        }
    }

    //快速排序优化
    private static int partitionPlus(int[] array, int i, int j) {
        int left = i;
        int right = j;


        //以三个值中的中位数为基准，对数组进行划分
        int midNum = getMidNum(array, left, right);
        //将基准值和第一个值进行交换
        swap(array,left,midNum);
        int pivot = array[left];

        while (left < right) {
            //从后向前找到比pivot小的值
            while (left < right && array[right] >= pivot) {
                right--;
            }
            //从前向后找到比pivot大的值
            while (left < right && array[left] <= pivot) {
                left++;
            }
            //将两个值进行交换
            swap(array, left, right);
        }
        //再将基准值放到（left = right）结束的位置上
        swap(array, i, left);
        return left;
    }

    //获取三个数的中位数
    private static int getMidNum(int[] array, int left, int right) {
        int mid = (left + right) >> 1;
        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            } else if (array[right] < array[mid]) {
                return right;
            }else {
                return mid;
            }
        }else {
//            array[left] > array[right]
            if (array[mid] > array[left]) {
                return left;
            } else if (array[right] > array[mid]) {
                return right;
            }else {
                return mid;
            }
        }
    }
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

2.3.3 快速排序非递归

快速排序的非递归实现可以使用栈来辅助实现。具体步骤如下：

1. 创建一个栈，用来存储待排序的子数组的起始和结束位置。

2. 将整个数组的起始位置和结束位置入栈。
   

3. 循环执行以下步骤，直到栈为空：
   a. 出栈得到一个子数组的起始和结束位置。
   

b. 根据这个子数组的起始和结束位置进行一次快速排序，将子数组分割成两部分，并得到分割点的位置。

c. 如果分割点的左侧子数组的长度大于1，则将左侧子数组的起始和结束位置入栈。

d. 如果分割点的右侧子数组的长度大于1，则将右侧子数组的起始和结束位置入栈。

   public static void quickSortNor(int[] array) {
        int start = 0;
        int end = array.length - 1;
        //申请一个栈
        Stack<Integer> stack = new Stack<>();
        //将数组的起点和终点放入栈中
        stack.push(start);
        stack.push(end);
        while (!stack.isEmpty()) {
            //从栈中取出两个栈顶，分别为终点和起点
            end = stack.pop();
            start = stack.pop();
            //对数组进行一次快排
            int div = partition1(array, start, end);
            //如果基准值左边的元素个数以上的元素，就将左边的子区间起点和终点放入栈中
            if (div - 1 > start) {
                stack.push(start);
                stack.push(div - 1);
            }
            //右边同理
            if (div + 1 < end) {
                stack.push(div + 1);
                stack.push(end);
            }
        }
        //重复上述步骤，直到栈为空时，所有元素就已经排好序了
    }
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

2.3.4 快速排序总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)
   

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

2.4 归并排序

2.4.1 基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种分治算法，它将一个数组分成两个子数组，然后分别对这两个子数组进行排序，最后将这两个已经排好序的子数组合并成一个有序的数组。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

具体步骤如下：

1. 分解：将数组分成两个子数组，直到每个子数组只有一个元素。
2. 合并：对这些子数组进行合并，将相邻的两个子数组合并成一个有序的数组，直到所有子数组都被合并成一个数组。归并的规则是将两个已经排好序的序列合并成一个新的有序序列，具体步骤如下：
   a. 比较两个序列的第一个元素，将较小的元素放入新的序列中。
   b. 移动指针，继续比较两个序列中的元素，将较小的元素放入新的序列中。
   c. 重复上述步骤，直到其中一个序列为空。
   d. 将另一个序列中剩余的元素依次放入新的序列中。
   通过以上规则，可以实现将两个有序序列合并成一个新的有序序列。

归并排序核心步骤：

	/**    时间复杂度：严格的二分
    *              O(N*logN)
    *     空间复杂度：
    *              O(N)
    *      稳定性：
    *             本身就是稳定的
    * */
    public static void mergeSort(int[] array) {
        mergeSortFun(array, 0, array.length - 1);
    }

    private static void mergeSortFun(int[] array, int start, int end) {
        //当区间只剩一个数据或者更少的数据，就不需要在进行分解了
        if (start >= end) {
            return;
        }
        //一中间的值将数据分为两个部分
        int mid = (start + end) >> 1;
        mergeSortFun(array, start, mid);
        mergeSortFun(array, mid + 1, end);

        //将分解的数据进行合并，在合并的过程中进行排序
        merge(array, start, mid, end);
    }

    private static void merge(int[] array, int start, int mid, int end) {
        //需要进行合并的第一部分
        int start1 = start;
        int end1 = mid;
        //需要进行合并的第二部分
        int start2 = mid + 1;
        int end2 = end;

        //新创建一个数组放置排序后的数据
        int[] tmp = new int[end - start + 1];//待排序数据的个数：end - start + 1
        int index = 0;

        //对两部分数据进行排序合并成一个数组
        while (start1 <= end1 && start2 <= end2) {
            if (array[start1] <= array[start2]) {
                tmp[index++] = array[start1++];
            } else {
                tmp[index++] = array[start2++];
            }
        }
        while (start1 <= end1) {
            tmp[index++] = array[start1++];
        }
        while (start2 <= end2) {
            tmp[index++] = array[start2++];
        }
		
		//将排好序的数据拷贝回原来的数组
        for (int i = 0; i < tmp.length; i++) {
            array[start + i] = tmp[i];
        }
    }

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

归并排序非递归实现：
归并排序的非递归实现可以通过迭代的方式来实现。具体步骤如下：

1. 将待排序的数组分成若干个长度为1的子数组，作为初始的有序子数组。
2. 依次将相邻的有序子数组进行合并，直到得到一个完整的有序数组。
3. 每次合并时，设置一个步长，表示每次合并的子数组的长度，初始步长为1。
4. 每次合并时，将相邻的两个子数组按照步长合并成一个更大的有序子数组。
5. 不断增加步长，重复上述步骤，直到整个数组合并完成
   

    public static void mergeSortNor(int[] array, int start, int end) {
        int gap = 1;//每组几个元素
        while (gap < array.length) {
            for (int i = 0; i < array.length; i = i + gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                int right = mid + gap;
                if (right >= array.length) {
                    right = array.length - 1;
                }
                merge(array, left, mid, right);
            }
            gap *= 2;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.4.2 归并排序总结

1. 归并的缺点在于需要O(N)的空间复杂度，也就是说，申请的临时数组和原数组一模一样，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)，主要用于存储临时的合并结果。在归并排序过程中，需要额外的O(N)的空间来存储合并操作的中间结果，因此相对于快速排序等原地排序算法，归并排序的空间复杂度较高。
4. 稳定性：归并排序的优点是具有稳定性，相同元素的相对顺序在排序前后保持不变，即它本身就是稳定的。

2.4.3 海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1. 先把文件切分成 200 份，每个 512 M
   

2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以

3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
   

3. 排序算法复杂度及稳定性分析

4. 其他非基于比较排序（了解）

1.计数排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
具体步骤如下：

1. 找出待排序数组中的最大值max和最小值min，并创建一个长度为max-min+1的计数数组count，用来统计每个元素出现的次数。

2. 遍历待排序数组，将每个元素出现的次数记录在计数数组中。

3. 根据计数数组中的值，重新构造排序后的数组。
   

    public static void calculateSort(int[] array) {
        //找出数组中的最大值和最小值
        int maxNum = 0;
        int minNum = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] < minNum) {
                minNum = array[i];
            }
            if (maxNum < array[i]) {
                maxNum = array[i];
            }
        }

        //创建一个临时数组
        int len = maxNum - minNum + 1;
        int[] tmpArray = new int[len];
        //遍历数组将数字对象对应下标的tmpArray数组的内容进行++
        for (int i = 0; i < array.length; i++) {
            tmpArray[array[i] - minNum]++;
        }
        //遍历临时数组，将数据写回到原来的数组
        int index = 0;
        for (int i = 0; i < tmpArray.length; i++) {
            while (tmpArray[i] != 0) {
                array[index] = i + minNum;
                index++;
                tmpArray[i]--;
            }
        }
    }
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

【计数排序的特性总结】

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围)),计数排序的时间复杂度与待排序序列的长度和元素范围有关。
3. 空间复杂度：O(范围)
4. 稳定性：稳定
5. 计数排序的缺点是需要额外的空间来存储计数数组，当待排序数组中元素范围较大时，计数数组会占用大量空间。此外，计数排序只能对整数进行排序，无法对浮点数或字符串进行排序。

2.基数排序
基数排序是一种非比较排序算法，它根据元素的位数逐个将待排序的数字按照位数上的值进行排序。基数排序的基本思想是将整数按照个位、十位、百位…等位置的值进行排序，直到最高位排序完成为止。每个位数的排序都是利用稳定的排序算法（如计数排序或桶排序）来完成的。
个位：

十位：


基数排序的过程如下：

1. 首先，确定最大值的位数，以确定需要多少轮排序。例如，如果最大值是3位数，则需要进行3轮排序。

2. 对每一位进行排序，从最低位开始到最高位。在每一轮排序中，将元素按照当前位的值分配到对应的桶中。

3. 按照当前位的值的顺序，将所有元素从桶中取出，按照顺序重新放回原数组中。

4. 重复以上步骤，直到所有位都被排序。

/**
 * 基数排序
 * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}
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

基数排序的特点包括：

1. 稳定性：基数排序是一种稳定的排序算法，相同元素的相对位置不会改变。

2. 时间复杂度：基数排序的时间复杂度为O(d*(n+r))，其中d为最大值的位数，n为元素个数，r为基数（桶的个数）。在最坏情况下，基数排序的时间复杂度为O(n^2)。

3. 空间复杂度：基数排序的空间复杂度为O(n+r)，其中n为元素个数，r为基数。

4. 适用范围：基数排序适用于元素为非负整数的情况，且元素的范围不宜过大。当元素范围较大时，基数排序的空间复杂度会变得很大。

3.桶排序
一句话总结：划分多个范围相同的区间，每个子区间自排序，最后合并。

桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。

桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。

以下是桶排序的具体步骤：

1. 确定桶的数量和范围：根据待排序数组的特点和分布情况，确定需要的桶的数量。将待排序的元素分散到不同的桶中，可以根据元素的大小范围将桶的大小设置为合适的值。

2. 将待排序数组中的元素分配到各个桶中：遍历待排序数组，根据元素的大小将其分配到对应的桶中。可以使用简单的映射函数，将元素映射到桶的索引上。

3. 对每个非空桶中的元素进行排序：对每个非空桶中的元素使用其他排序算法进行排序，可以选择插入排序、快速排序等。如果桶的数量较少，也可以使用递归地应用桶排序来进行排序。

4. 按照桶的顺序依次取出各个桶中的元素：按照桶的顺序将每个非空桶中的元素取出，并放入最终的排序结果数组中。

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;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    
    // 将每个元素放入桶
    for(int i = 0; i < arr.length; i++){
        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);
		}
	}  
}

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

桶排序的特点包括：

1. 适用于均匀分布的数据：桶排序在数据分布较均匀的情况下效果较好，可以使每个桶中的元素数量尽量接近，减少后续排序的时间。

当输入的数据可以均匀的分配到每一个桶中，最快
当输入的数据被分配到了同一个桶中，最慢

2. 需要额外的空间：桶排序需要额外的空间来存储桶和分配元素，因此它的空间复杂度较高。

3. 对数据范围要求较高：桶排序对数据的范围要求较高，需要事先确定数据的范围并设置合适的桶的数量和大小。

4. 时间复杂度：桶排序的时间复杂度主要取决于对每个非空桶中元素的排序算法的复杂度。如果桶的数量接近待排序数组的长度，那么桶排序的时间复杂度将接近O(nlogn)。

5. 选择题

1. 快速排序算法是基于()的一个排序算法。
A：分治法 B：贪心法 C：递归法 D：动态规划法
解：A

2. 对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入 位置需比较()次？（采用从后往前比较）
A: 3 B: 4 C: 5 D: 6
解：C
当第第8个记录45插入到有序表时，前7个数据已经有序，该记录此事为（15，23，38，54，60，72，96，45，83），在比较过程中45和96比较，45 < 96，继续向前；45和72比较，45 < 72，继续向前；45和60比较，45 < 60，继续向前；45和54比较，45 < 54，继续向前；45和38比较，45 > 38,45应该插入到38的后面，插入位置找到。因此，插入45时需要比较5次。

3. 以下排序方式中占用O(n)辅助存储空间的是()
A: 简单排序 B: 快速排序 C: 堆排序 D: 归并排序
解：D
占用O(n)辅助存储空间的排序算法是归并排序。在归并排序中，需要额外的存储空间来存储临时的中间结果，以便进行合并操作。这样的辅助存储空间大小与待排序数组的大小成线性关系，即O(n)。

4. 下列排序算法中稳定且时间复杂度为O(n^2)的是()
A: 快速排序 B: 冒泡排序 C: 直接选择排序 D: 归并排序
解：B
根据下列表格，排序算法中稳定且时间复杂度为O(n^2)的为冒泡排序。

5. 关于排序，下面说法不正确的是()
A: 快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
B: 归并排序是一种稳定的排序,堆排序和快排均不稳定
C: 序列基本有序时，快排退化成 “冒泡排序”，直接插入排序最快
D:归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)
解：D
归并排序的空间复杂度为O(N)，因为在归并排序中需要额外的空间来存储临时的数组。而堆排序的空间复杂度为O(1)，因为堆排序是原地排序算法，不需要额外的空间来存储临时数据。

6. 设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排序结果是（）
A: 34，56，25，65，86，99，72，66
B: 25，34，56，65，99，86，72，66
C: 34，56，25，65，66，99，86，72
D: 34，56，25，65，99，86，72，66
解：A
采用挖坑法实现划分数据，得到的一趟快速排序结果是34，56，25，65，86，99，72，66