算法与数据结构复习——排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法与数据结构复习——排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4329字，纯文字阅读大概需要7分钟。

内容图文

力扣题：

1.选择排序

思路：由两个嵌套的for循环组成，内层for循环从i~nums.length中寻找最小值，外层for循环用于交换数据并且排好0~i的数据。

class Solution {
    public int[] sortArray(int[] nums) {
        int min = 0,temp = 0;
        for(int i = 0;i < nums.length;i++){
            for(int j = i;j < nums.length;j++){
                if(nums[min] > nums[j]) min = j;
            }
            temp = nums[i];
            nums[i] = nums[min];
            nums[min] = temp;
            min = i + 1;
        }
        return nums;
    }
}

2.插入排序

思路：从头开始排序，0~i为已排好，i~nums.length为待排序的，其中陆续加进来的每一项都被插入到对应顺序的位置。

class Solution {
    public int[] sortArray(int[] nums) {
        int min = 0,temp = 0;
        for(int i = 0;i < nums.length;i++){
            temp = nums[i];
            int j = i;
            while(j > 0 && nums[j - 1] > temp){
                nums[j] = nums[j-1];
                j--;
            }
            nums[j] = temp;
        }
        return nums;
    }
}

题目：在链表中如何使用插入排序？

思路：两个指针，一个指向前面搜索已排好序的链表，一个后移添加新的节点

public ListNode insertionSortList(ListNode head) {
        ListNode myhead = new ListNode(0), pre;
        myhead.next = head;
        
        while(head != null && head.next != null) {
            if(head.val <= head.next.val) {
                head = head.next;
                continue;
            }
            pre = myhead;
            
            while (pre.next.val < head.next.val) pre = pre.next;
            
            ListNode temp = head.next;
            head.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return myhead.next;
    }

3.冒泡排序

思路：循环数组，不断把大数冒泡到最顶端，最后所有的数都排序完毕。（力扣超时）

class Solution {
    public int[] sortArray(int[] nums) {
        for(int i = 0;i < nums.length;i++){
            boolean isSorted = false;
            for(int j = 0;j < nums.length - i -1;j++){
                if(nums[j] > nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                    isSorted = true;
                }
            }
            if(!isSorted){
                break;
            }
        }
        return nums;
    }
}

4.归并排序

思路：将一个数组不断二等分，分为更小的序列，直到所有的序列长度都为1；再进行合并，先两两合并，再带有两个元素的数组两两合并，两个数组空间上直接相连，通过分别比较二者第一个元素和第二个元素这样插入合并（类似合并两个有序数组），后面的以此类推。

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0 ,nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums, int s, int t){
        int[] r1 = new int[1000];
        int m = 0;
        if(s == t) return;
        else{
            m = (s + t) / 2;
            mergeSort(nums, s, m - 1);
            mergeSort(nums, m + 1, t);
            merge(nums, r1, s, m, t);
            for(int i = s;i <= t;i++){
                r1[i] = nums[i];
            }
            
        }
    }

    public void merge(int[] nums, int[] r1, int s, int m, int t){
        int i = s, j = m + 1, k = s;
        while(i <= m && j <= t){
            if(nums[i] < nums[j]) r1[k++] = nums[i++];
            else{
                r1[k++] = nums[j++];
            }
        }
        while(i<=m){
            r1[i++] = nums[i++];
        }
        while(j<=t){
            r1[j++] = nums[j++];
        }
    }
}

912题用归并排序说超出了内存限制，因为我规定了r1的大小申请蛮多的，但是题设大小超过50000，理论上如果能用归并排序则也能申请50000大小的数组，可惜不行？

5.快速排序

思路：分别用两个变量指向数组头和尾向中间进行比较，值到两个变量相等（表示下标）；比较的依据是如果左边的指针对应的值大于右边的，则进行对换；

当指针相等后，在分别在两个分组中进行同样的操作，依次类推（递归），直到分组大小为1，即所有的左指针都等于右指针。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums.length >= 1){
            quickSort(nums, 0, nums.length - 1);
            if(k <= nums.length){
                // for(int i = 0;i < nums.length;i++){
                //    System.out.print(nums[i] + "  ");
                // }
                return nums[nums.length - k];
            }
        }
        // for(int i = 0;i < nums.length;i++){
        //     System.out.print(nums[i] + "  ");
        // }
        return -1;
    }

    public int partitions(int[] nums, int first, int end){
        int i = first, j = end, temp = 0;
        while(i < j){
            while(i < j && nums[i] <= nums[j]){
                j--;
            }
            if(i < j){
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
            }
            while(i < j && nums[i] <= nums[j]){
                i++;
            }
            if(i < j){
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j--;
            }
        }
        return i;
    }

    public void quickSort(int[] nums, int first, int end){
        if(first < end){
            int mid = partitions(nums, first, end);
            quickSort(nums, first, mid - 1);
            quickSort(nums, mid + 1, end);
        }
    }
}

 

 

6.堆排序

思路：首先将数组转化成大根堆，再通过不断移除根节点（和叶子节点交换）的方式进行排序，最终的数组即为排好序的数组。

class Solution {
    public int[] sortArray(int[] nums) {
        int len = nums.length;
        for(int i = (len-1)/2;i >= 0;i--){
            nums = siftHeap(nums, i, len);
        }
        for(int i = 1;i < len;i++){
            int temp = nums[0];
            nums[0] = nums[len-i];
            nums[len-i] = temp;
            nums = siftHeap(nums, 0, len-i);
        }

        return nums;
    }

    public int[] siftHeap(int[] nums, int k, int n){
        int len = n;
        int i = k, j = 2*i+1;
        while(j < len){
            if(j+1 < len && nums[j] < nums[j+1]){
                j++;
            }
            if(nums[i] < nums[j]){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }else{
                break;
            }
        }
        return nums;
    }
}

 

 

内容总结

以上是互联网集市为您收集整理的算法与数据结构复习——排序全部内容，希望文章能够帮你解决算法与数据结构复习——排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---