简单排序算法

Java leetcode
数据结构与算法
发布日期:   2022-09-09

1.选择排序

选择排序是一种让该排序的数到达它应该到的位置的一种排序算法，算法流程如下，数组下标从[0...N-1]，算法开始时从0开始，找到那个应该到0位置的数，然后找到后让它和0进行swap

这样的话，我们认为[0…0]位置就是排好序的了，接下来就是要对[1....N-1]进行排序，注意，这时候查找要交换的值依然是最小值，但是搜索区间从[0...N-1]变成了[1...N-1],搜索区间是[left,right]

package leetcode_2;

import org.junit.Test;

import java.util.Arrays;

public class SelectionSort {
    public void selectionSort(int[] arr){
        //1.处理边界条件
        if(null == arr || arr.length <2){//arr.length ==0 || arr.length == 1
            return;
        }
        //处理从i-N-1
        for(int i = 0 ;i<arr.length;i++){
            int minIdx = i;
            for(int j = i+1;j<arr.length;j++){
                //处理从i-N-1间的最小值
                minIdx = arr[j] < arr[minIdx] ? j:minIdx;
            }
            swap(arr,i,minIdx);
        }
    }

    private void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Test
    public void test(){
        int[] arr = {7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6};
        System.out.println(Arrays.toString(arr));
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

2.冒泡排序

冒泡排序本质上也是一种让该排序的数到达它应该到的位置上的一种排序算法

算法流程如下：首先从0开始，0开始和旁边的数比较，也就是0+1的下标的数进行比较，然后1和1+1位置的数比较，一旦发现这个数比后边的那个数要大，那我就把这个数和后面那个数交换

然后下一次检查开始，以这个数为参照，继续比较，直到把一个数，移到数组的最后面，这个过程中可以保证最大的数被移到了数组的N-1位置，这时候可以确保[N-1,N-1]区间位置上的数已经是排好序的了

package sort;

import org.junit.Test;

import java.util.Arrays;

public class BubbleSort {
    public void bubbleSort(int[] arr){
        if(arr == null || arr.length <2){
            return;
        }
        //0-n-1
        //0-n-2
        //0-n-3
        //...
        //0-0
        //0-end
        for(int end = arr.length-1;end>=0;end--){
            //0~end
            //01 12 23 34 ... end-1:end
            for(int i = 0;i < end;i++){//我以开头为例解这个题
                if(arr[i] > arr[i+1]){
                    swap(arr,i,i+1);
                }
            }
            //for(int k = 1;k<= end;k++){//这是以结尾为例
                //if(arr[k-1] > arr[k]){
                    //swap(arr,k-1,k);
                //}
            //}
        }
    }


    private void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Test
    public void test(){
        int[] arr = {7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6};
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

3.插入排序

插入排序本质上是一种区间化有序数组的算法思路，既然提到了区间化，那么肯定就会有base-case的区间

一开始，有序的区间是[0...0]，这个区间就是有序的了，然后新增一个数，想要把[0...1]区间变得有序，那么就需要将arr[1]和arr[0]进行比较，如果发现arr[0]比arr[1]要小，那么就不动,否则交换arr[1]和arr[0]

接着问题规模扩大，这时候的base-case是[0..1]是有序的，然后我们将[2]添加进来，我们首先将arr[2]和arr[1]进行比较，如果发现arr[1]比arr[2]要小，那么就不动,否则交换arr[1]和arr[2]，注意，此时算法还没有结束，如果发现交换后arr[1]比arr[0]要小，那么肯定还是要交换[1]和[0]的

package sort;

import org.junit.Test;

import java.util.Arrays;

public class InsertSort {
    public void insertSort(int[] arr){
        if(arr == null || arr.length <2){
            return;
        }
        //base-case[0...0]
        //[0...1]
        //[0...2]
        //结尾位置在变!所以我们遍历结尾的数
        //[0...n-1]
        for(int end = 1 ;end < arr.length ;end++){
            int curNumIndex = end;//新来的数,想要加入排序数组
            while (curNumIndex -1 >=0 && arr[curNumIndex-1] > arr[curNumIndex]){//我现在新加的数是end,我要观察的是end-1,什么时候一直执行交换呢
                                   //就是当arr[end-1]>arr[end]的时候,才交换
                                    //左边有数
                swap(arr,curNumIndex,curNumIndex-1);
                curNumIndex--;
            }
        }
    }


    private void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Test
    public void test(){
        int[] arr = {7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6};
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

public void insertSort(int[] arr){
    if(arr == null || arr.length <2){
        return;
    }
    for(int end = 1 ;end < arr.length ;end++){
        //当前的数的前一个位置
        for(int pre = end-1;pre >= 0 && arr[pre] > arr[pre+1] ; pre-- ){
            swap(arr,pre,pre+1);
        }
    }
}

4. 二分法

4.1 在有序数组中找到num

//基础二分法,定义搜索区间为[left,right]
public static boolean isExist(int[] arr,int num){
    if( arr == null || arr.length == 0){
        return false;
    }
    int left = 0,right = arr.length;
    // [left,right]何时不存在?当[1,1]这种情况是可以接受的
    // 但是[2,1]这种情况是不可以接受的
    while (left <= right){
        int mid = left + (right-left)/2;
        if(arr [mid] == num){
            return true;
        }else if(arr[mid] < num){
            //这要做的是区间的缩减
            left = mid+1;
        }else{
            right = mid-1;
        }
    }
    return false;
}

4.2 在有序数组中找到>=num最左边的位置

这种寻找边界的二分来说，由于不确定找到那个数的确切位置(意思是，只要数组没有被搜索完，就有可能存在更合理的数)，在这种情况下，算法结束的条件是搜索区间成为不合法区间(二分结束)

//arr有序,>=num最左的位置,找不到就返回-1
public static int mostLeftNum(int[] arr,int num){
    if(arr == null || arr.length == 0){
        return -1;
    }
    int mostLeft = -1;//中途发生的最早的左边界下标
    int left = 0,right = arr.length-1;
    while (left <= right){
        //mostLeft有可能会更新
        int mid = left + (right-left)/2;
        if(arr[mid] >= num){//符合题目条件的数
            mostLeft = mid;//这时候就更新,然后包含mid和他右边的区间都砍掉
            right = mid-1;
        }else{
            //这时候不更新,把左边连同它自己砍掉
            left = mid+1;
        }
    }
    return mostLeft;
}

4.3 在有序数组中找到<=num最右边的位置

public static int mostRight(int[] arr,int num){
    int mostRight = -1;
    if(arr == null || arr.length == 0){
        return mostRight;
    }
    int left = 0,right = arr.length-1;
    while (left <= right){
        int mid = left + (right - left)/2;
        if(mid <= num){
            mostRight = mid;
            //arr[mid] <= mid,这时候想要找到更右的,连同它自己和左边的全部干掉
            left = mid+1;
        }else{
            //这时候还没有找到比它小的,连同自己和它右边全部干掉
            right = mid-1;
        }
    }
    return mostRight;
}

4.4 局部最小值问题

现在有一个数组，其任意相邻的两个数都不相等，而且是无序的（没有排序）

定义局部最小值

(1)边界:如果[0]<[1]，此时可以称0为局部最小值

(2)边界:如果[N-2]>[N-1]，此时可以称N为局部最小值

(3)普通情况,如果[N-3]>[N-2]<[N-1]，那么可以称N-2为局部最小

只要能够返回一个局部最小值即可

边界情况比较简单，我们从普通情况开始分析，我们假设[0]>[1]而且[N-2]<[N-1]，也就是说，形成了[0]-[1]区间内的局部下降，[N-2]-[N-1]的局部上升，那么依据函数的思想，中间的这一段一定会有一个局部最小值。(如果不懂的话可以试着枚举所有情况来进行验证)

我们假设以一种情况来分析，现在找到一个mid，这个mid并不同时小于mid-1的数和mid+1的数，这时候分为几种情况，我们来列举一下:左边比mid要大，而右边比mid要小、左边比mid要小，而右边比mid要大、左边比mid要小，右边比mid要小

  • 左边比mid要大，而右边比mid要小:这时候就形成了搜索区间的末端是一个上升的趋势的，而mid的右边形成了一个下降的趋势，这种情形不正是一开始的情形吗？那么局部最小值不就是应该会在右边吗?那么是不是可以缩小搜索区间到右边去呢？(把自己连同左边全部干掉)

第二种情况同理

至于两边都是小的情况，我们可以手动规定让它去搜索左边的区间

其中有一个区间边界的问题，我们希望mid-1、mid、mid+1都在[left,right]这个范围之内，也就是说，mid的取值在length>=3的时候，其最小搜索区间至少有3个数，如何来保证这个事情呢，也就是说要left、left+1、right，翻译成不等式就是left<right-1

public static int mostSmallNum(int[] arr){
    if(arr == null || arr.length == 0){
        return -1;
    }
    if(arr.length == 1){
        return 0;
    }
    //边界情况
    if(arr.length == 2 && arr[0]<arr[1]){
        return 0;
    }
    if(arr.length ==2 && arr[arr.length-2] < arr[arr.length-1] ){
        return arr.length-1;
    }
    int left = 0,right =arr.length-1;
    int ans = -1;
    while (left < right-1){
        int mid = left+(right-left)/2;
        //由于涉及到mid-1和mid+1,这里一定要慎重讨论
        if(arr[mid] < arr[mid-1] && arr[mid] <arr[mid+1]){
            return mid;
        }
        if(arr[mid] > arr[mid-1]){
            right = mid-1;
            continue;
        }
        if(arr[mid] > arr[mid+1]){
            left = mid+1;
            continue;
        }
    }
    return arr[left]<arr[right]?left:right;

}
  • 边界问题也可以通过边界问题来进行规避，由于我们已经检查过了(0)这个点和(N-1)，所以我们直接让搜索区间变成(1,N-2)，这样的话就可以规避这个问题了
public static int mostSmallNum(int[] arr){
    if(arr == null || arr.length == 0){
        return -1;
    }
    if(arr.length == 1){
        return 0;
    }
    //边界情况
    if(arr.length == 2 && arr[0]<arr[1]){
        return 0;
    }
    if(arr.length ==2 && arr[arr.length-2] < arr[arr.length-1] ){
        return arr.length-1;
    }
    int left = 1,right =arr.length-2;
    int ans = -1;
    while (left <= right){
        int mid = left+(right-left)/2;
        //由于涉及到mid-1和mid+1,这里一定要慎重讨论
        if(arr[mid] < arr[mid-1] && arr[mid] <arr[mid+1]){
            ans = mid;
            break;
        }
        if(arr[mid] > arr[mid-1]){
            right = mid-1;
            continue;
        }
        if(arr[mid] > arr[mid+1]){
            left = mid+1;
            continue;
        }
    }
    return ans;

}

5. 时间复杂度

时间复杂度是用来描述发生了几次常数操作的指标，如果某个操作与数据量没有关系，就称为常数操作

常见的常数操作有数组寻址、加减乘除

分析时间复杂度有关的关键是找到与数据量有关的操作

分析冒泡排序:冒泡排序的过程一共会有n+(n-1)+(n-2)+...+1次比较交换操作，注意这些操作都是常数操作

根据等差数列求和公式:一共有(a1*n)+(n^2-n)/2次常数操作

那么时间复杂度的估算就是这个式子里面最高阶的元素

常见时间复杂度:O(1)<O(logN)<O(NlogN)<O(n^2)<O(N^3)<O(N^k)<O(2^n)(递归尝试)<O(3^n)<O(k^n)<O(n!)

文章作者: 穿山甲
文章链接: https://lumxi.github.io/2022/09/09/algorithm/zuo-eaasy/simple-sort/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 穿山甲 !
Java leetcode
赏
  目录