美文网首页知识点
算法:冒泡、选择、插入、快速

算法:冒泡、选择、插入、快速

作者: SupKing_a520 | 来源:发表于2020-05-07 19:41 被阅读0次

    冒泡排序


    它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。以此类推,直到所有元素均排序完毕。

    • 时间复杂度:O(n2)
    • 空间复杂度:O(1)
    public int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }
    

    选择排序


    首先在未排序序列中找到最小(大)元素,存放到起始位置,然后再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

    • 时间复杂度:O(n2)
    • 空间复杂度:O(1)
    public int[] selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
        return arr;
    }
    

    插入排序


    它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

    • 时间复杂度:O(n2)
    • 空间复杂度:O(1)
    public int[] insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int preIndex = i - 1;
            int current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
        return arr;
    }
    

    快速排序


    通过一趟排序将待排数据录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

    1. 算法步骤:
    • 从数列中挑出一个元素,称为 “基准”(pivot)
    • 将所有比基准值小的元素摆放在基准值前面,所有比基准值大的元素摆在基准值的后面(相同的数可以到任一边)
    • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序
    1. 复杂度:
    • 时间复杂度:O(nlogn)
    • 空间复杂度:O(logn)
    public void quickSort(int[] arr, int start, int end) {
        //递归出口
        if (start > end) return;
        int left = start;
        int right = end;
        int pivot = arr[left];
        while (left != right) {
            //从后向前找到比基准数小的位置
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            //从前向后找到比基准数大的位置
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //如果不是同一个位置则交换两个数
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        //调整基准数的位置
        arr[start] = arr[left];
        arr[left] = pivot;
        quickSort(arr, 0, left - 1);
        quickSort(arr, left + 1, end);
    }
    

    相关文章

      网友评论

        本文标题:算法:冒泡、选择、插入、快速

        本文链接:https://www.haomeiwen.com/subject/pldzghtx.html