目录

归并排序

---

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

如何记忆稳定算法：冒插归稳          冒冒失失插到最前面面试，神气归来，稳了

 

 

快速排序

最坏情况下（例如前面所说，数组倒序，枢纽元选第一位）快速排序将花费O(N2)时间。
最好情况下，快速排序和归并排序一样，花费O(NlogN)时间。
平均情况下，快速排序花费O(NlogN)时间。

快速排序最优的情况就是每一次取到的元素都刚好平分整个数组

此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；

最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)

     这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;

     综上所述：快速排序最差的情况下时间复杂度为：O( n^2 )

 

归并排序

参考：https://blog.csdn.net/m0_38056893/article/details/79461901

参考：https://www.cnblogs.com/shudonghe/p/3302888.html

 

归并排序采用的是分治(divide-and-conquer)法思想。

（1）基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

（2）执行过程：

 

（3）算法思路：

（4）Java代码：

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr= {6,5,3,9,4,1,2,7,8,0};
        System.out.println("排序前：" + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int low, int high){
        if(low >= high){
            return ;
        }

        int mid = low + (high-low)/2;
        mergeSort(arr, low, mid);          //对左边序列进行归并排序
        mergeSort(arr, mid+1, high);  //对右边序列进行归并排序
        merge(arr, low, mid, high);        //合并两个有序序列

    }

    public static void merge(int[] arr, int low, int mid, int high){
        int i = low;     //左边序列起始索引
        int j = mid+1;   //右边序列起始索引
        int[] tmp = new int[arr.length];
        int k = low;      //tmp的下标

        while(i <= mid && j <= high){
            if(arr[i] < arr[j]){
                tmp[k++] = arr[i++];
            }else{
                tmp[k++] = arr[j++];
            }
        }

        //若左边序列还有剩余，则将其全部拷贝进tmp[]中
        while(i <= mid){
            tmp[k++] = arr[i++];
        }
        //若右边序列还有剩余，则将其全部拷贝进tmp[]中
        while(j <= high){
            tmp[k++] = arr[j++];
        }

        for(int t = low; t < k; t++){
            arr[t] = tmp[t];
        }

    }
}

（6）复杂度分析：

 

堆排序