从LeetCode215看排序算法_Golang

leetcode215 数组的第k个最大元素

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

① 第一反应：java的内置排序arrays.sort()

arrays.sort的复杂度取决于所使用的排序算法。在java中，arays类中的sort方法使用的是一种优化的快速排序算法或归并排序算法。
对于快速排席算法，其平均时间复杂度为0(nl0gn)，其中n是数组的大小。然而，在最坏情况下，快速排序的时间复杂度可以达到o(n^2)，这发生在数组已经有序的情况下。
对于归并排序算法，其时间复杂度始终为0(nlog n)，不论输入数据的情况如何。
总结起来，arrays.sort方法的平均时间复杂度为0(nlog n)，最坏情况下可能为o(n^2)。

② 冒泡排序

思路：总结来说就是两个for循环。多次遍历数组，每次遍历通过不断比较相邻元素的大小，如果左边大于右边就交换元素顺序，最终会将一个最大（或最小的）元素冒泡到数组的末尾或开头。直到最终没有任何元素需要交换（end一直--）。

第k大只要找到第k个泡泡即可，无需向后比较对整个数组进行排序

class solution {
    public int findkthlargest(int[] nums, int k) {
        return bubblesort(nums, k);
    }

    int bubblesort(int[] nums, int k){
        int n = nums.length;
        int count = 0;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-i-1;j++){
                if(nums[j] > nums[j+1]){
                    int tmp =nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                }
            }
            count++;
            if(count == k){
                break;
            }
        }
        return nums[n-k];
    }
}

③归并排序（先分解再合并）

思路：通过分治法将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。与快速排序相比，快速排序是将序列划分成两个子序列，再递归使子序列有序；而归并排序是先使子序列有序，再进行合并。

不断从中间划分子数组，递归合并

public class mergesort {   
    public static int[] mergesort(int[] nums, int l, int h) {
        if (l == h)
            return new int[] { nums[l] };
         
        int mid = l + (h - l) / 2;
        int[] leftarr = mergesort(nums, l, mid); //左有序数组
        int[] rightarr = mergesort(nums, mid + 1, h); //右有序数组
        int[] newnum = new int[leftarr.length + rightarr.length]; //新有序数组
         
        int m = 0, i = 0, j = 0; 
        while (i < leftarr.length && j < rightarr.length) {
            newnum[m++] = leftarr[i] < rightarr[j] ? leftarr[i++] : rightarr[j++];
        }
        while (i < leftarr.length)
            newnum[m++] = leftarr[i++];
        while (j < rightarr.length)
            newnum[m++] = rightarr[j++];
        return newnum;
    }

leetcode 4：寻找两个正序数组的中位数

这道题就用到了归并排序

class solution {
    public double findmediansortedarrays(int[] nums1, int[] nums2) {
 
        int totallength = nums1.length + nums2.length;
        int[] nums = new int[totallength];
        int i = 0, j = 0;
        int index = 0;
        while (index <= totallength /2) {
            if (i < nums1.length && (j >= nums2.length || nums1[i] < nums2[j])) {
                nums[index] = nums1[i++];
            } else{
                nums[index] = nums2[j++];
            }
            if (index == totallength / 2) {
                //nums数组长度为偶数
                if ((totallength & 1) == 0) {
                    return (nums[index] + nums[index - 1]) / 2.0;
                } else {
                    //nums数组长度是奇数
                    return 1.0 * nums[index];
                }
            }
            index++;
        }
        return 0.0;
    }
}

④快速排序（边分解边排序）

思路：通过分治法将一个数组分成较小的子数组，然后递归地对每个子数组进行排序。

移动左右指针，左指针向右移动，直到找到一个大于等于分界值的元素；右指针向左移动，直到找到一个小于等于分界值的元素。交换这两个元素的位置，然后再次移动左右指针，直到左指针和右指针指向同一个元素，再递归左右子数组。

快速排序找到第k个最大的，就是排序后递增子数组的倒数第k个（序号为n-k）

class solution {
    public int findkthlargest(int[] nums, int k) {
        int n = nums.length;
        return quickselect(nums, 0, n-1, n-k);
    }

    public int quickselect(int[] nums, int l, int r, int k){
        if(l == r)  return nums[k];
        int x = nums[l], i = l-1, j = r+1;
        while(i < j){
            do i++;  while(nums[i] < x);
            do j--;  while(nums[j] > x);
            if(i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        //这个时候i==j==x，要寻找的坐标<=j则说明第k大元素在分界元素左边
        if(k <= j)  return quickselect(nums, l, j, k);
        else return quickselect(nums, j+1, r, k);
    }
}

快排的时间复杂度我们可以认为是o(nlogn),但当遇到原数组本身有序的情况下,其时间复杂度就会退化至o(n^2),这个其实很好理解,举个例子就明白了:

当最优情况下,即每趟选择key时都恰好选择到数组的中间值时(第n层可以确定 $2^{n-1}$ 个数字位置),快排的时间复杂度如下图完全(满)二叉树:

在最坏的情况下，这个树是一个完全的斜树，只有左半边或者右半边，即每趟选择key时都恰好选择到数组最大或最小的值时(即每一层都只能确定一个数字位置)。这时候我们的比较次数就变为∑n−1i=1(n−i)=(n−1)+(n−2)+⋯+1=n∗(n−1)2=o(n^2）

⑤堆排序

java提供了priorityqueue，可以构建小顶堆

class solution {
    public int findkthlargest(int[] nums, int k) {
        priorityqueue<integer> queue = new priorityqueue<>(); //小顶堆
        for(int num : nums){
            queue.add(num);
            if(queue.size() > k){
                queue.poll();
            }
        }
        return queue.peek();
    }
}

自己构建堆

class solution {
    public int findkthlargest(int[] nums, int k) {
        //-------------1.首先，构建最大堆[6,5,4,3,2,1]----------------
        //建大堆：要从堆的最后一个非叶子节点开始向下调整
        for (int i = nums.length/2-1; i >= 0; i--) {
            adjustheap(nums,i,nums.length);
        }
        //---2.每次把最大的换到最后一个位置，调整堆，交换后不把最后一个数看作堆里的数据-------
        for(int i = nums.length-1;i >= nums.length-k ;i--){
            swap(nums,0,i);
            adjustheap(nums,0,i);    //选出次小的数
        }
        return nums[nums.length-k];
    }
        //向下调整算法
        public static void adjustheap(int[] nums,int node,int tail){
        int left = node*2+1;
        int right = node*2+2;
        //-------------大的往上浮，小的往下浮--------------------
        int max = node;
        if(left<tail&&nums[left]>nums[max]){
            max=left;
        }
        if(right<tail&&nums[right]>nums[max]){
            max=right;
        }
        //---------max是父节点和左右子节点中最大的数-------------------
        //max!=node证明左右子节点有比父节点大的数,需要进行交换
        if(max!=node){
            swap(nums,max,node);
            adjustheap(nums,max,tail);
        }
    }
 
    public static void swap(int[] nums, int index1, int index2){
        int tmp = nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=tmp;
    }
}