Java学习记录 Day11（StringBuffer、排序算法）

超、凢脫俗 2022-04-25 02:56 192阅读 0赞

### 文章目录 ###

*  Day 11
 *   *  StringBuffer类
     *  排序算法

# Day 11 #

2019年4月27日。  
这是我学习Java的第十一天。  
这一天，我学到了以下的知识。

## StringBuffer类 ##

StringBuffer，是一个长度可变的字节容器，可以存储多个字符，也可以不断的往容器中追加内容。

**构造方法：**`public StringBuffer() // 无参构造方法`  
`public StringBuffer(int capacity) // 指定容量的字符串缓冲区对象`  
`public StringBuffer(String str) // 指定字符串内容的字符串缓冲区对象`

**常用的成员方法**

*  **返回功能**
    
     *  `public int capacity()`：返回当前容量  
        \- 默认情况下，初始容量为16
     *  `public int length()`：返回长度（字符数）
 *  **添加功能**
    
     *  `public StringBuffer append(String str)`：可以把任意类型数据添加到字符串缓冲区里面，并返回字符串缓冲区本身
     *  `public StringBuffer insert(int offset,String str)`：在指定位置把任意类型的数据插入到字符串缓冲区里面，并返回字符串缓冲区本身
 *  **删除功能**
    
     *  `public StringBuffer deleteCharAt(int index)`：删除指定位置的字符，并返回本身
     *  `public StringBuffer delete(int start,int end)`：删除从指定位置开始指定位置结束的内容，并返回本身
 *  **替换功能**
    
     *  `public StringBuffer replace(int start,int end,String str)`：从start开始到end用str替换
 *  **反转功能**
    
     *  `public StringBuffer reverse()`：字符串反转
 *  **截取功能**
    
     *  `public String substring(int start)`：从指定位置截取到末尾
     *  `public String substring(int start,int end)`：截取从指定位置开始到结束位置，包括开始位置，不包括结束位置

**StringBuffer和String的相互转换**

*  String – StringBuffer  
    \- 通过构造方法  
    \- 通过append()方法
 *  StringBuffer – String  
    \- 使用substring方法  
    \- 通过构造方法  
    \- 通过toString()方法

## 排序算法 ##

*  **冒泡排序**  
    原理：相邻元素两两比较，大的往后放，第一次完毕，最大值出现在了最大索引处  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70]  
    代码如下

public class Test2 {
    //冒泡排序：元素两两比较，大的往后放，经过一轮比较后，那么最大的元素就会出现在最后面。
        public static void main(String[] args) {
            int arr[] = {24, 69, 80, 57, 13};
            for (int i = 0; i < arr.length - 1; i++) {
                for(int j = 0 ; j < arr.length - i - 1 ; j++){
                    if (arr[j] > arr[j+1]) {
                        int tag = arr[j];
                        arr[j] =arr[j+1];
                        arr[j+1]= tag;
                    }
                }
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
        }
    }

*  **选择排序**  
    原理：从0索引开始，依次和后面元素比较，小的往前放，第一次完毕，最小值出现在了最小索引处  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 1]  
    代码如下

public class Test2 {
    //选择排序：每次拿一个元素，跟他后面的元素，挨个去比，小的往前放，经过一轮比较后，那么最小元素就会放在最前面去
        public static void main(String[] args) {
            int arr[] = {24, 69, 80, 57, 13};
            for (int index = 0; index < arr.length - 1; index++) {
                for(int j = 1 + index; j < arr.length  ; j++){
                    if (arr[index] > arr[j]) {
                        int tag = arr[index];
                        arr[index] =arr[j];
                        arr[j]= tag;
                    }
                }
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
        }
    }

*  **直接插入排序**  
    原理：将后面的元素，插入之前的一个有序列表，使之仍然保持有序
    
    代码如下

public class Test2 {
        public static void main(String[] args) {
            int arr[] = {24, 69, 80, 57, 13};
            for (int i = 1; i < arr.length; i++) {
                for (int j = i; j > 0; j--) {
                    if (arr[j] < arr[j - 1]) {
                        int tag = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = tag;
                    }
                }
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
        }
    }

*  **希尔排序**  
    原理：对直接插入排序的一种改进，它的思想是选择一个合适的增量，然后经过一轮插入排序后，就会让数组大致有序，然后不断的缩小增量，进行插入排序，直到增量为1，整个排序结束。第一次的增量一般取数组长度的一半  
    对于增量，具有许多计算方法。其中常见的，就有**克努特序列**（h=1，h=3\*h+1）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 2]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 3]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 4]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 5]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 6]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 7]  
    代码如下

public class Test2 {
        public static void main(String[] args) {
                //希尔排序，是对直接插入排序的一种改进，他的思想选择一个合适的增量，然后经过一轮插入排序后，就会让数组大致有序
                //然后不断的缩小增量，进行插入排序，直到增量为1 整个排序结束
                int arr[] = {24, 69, 80, 57, 13};
                shellSort(arr);
                //其实我们的直接插入排序，就是增量为1的希尔排序
    
                //int h = 1;
                //for (int i = h; i < arr.length; i++) {
                //    for (int j = i; j > h - 1; j -= h) {
                //        if (arr[j] < arr[j - h]) {
                //            swapValue(arr, j, j - h);
                //        }
                //    }
                //}
                System.out.println(Arrays.toString(arr));
            }
    
            private static void shellSort(int[] arr) {
                //定义增量为4
           /* int h=4;
            for (int i = h; i < arr.length; i++) {
                for (int j = i; j > h - 1; j-=h) {
                    if (arr[j] < arr[j - h]) {
                        swapValue(arr, j, j - h);
                    }
                }
            }
    
            h = 2;
            for (int i = h; i < arr.length; i++) {
                for (int j = i; j > h - 1; j -= h) {
                    if (arr[j] < arr[j - h]) {
                        swapValue(arr, j, j - h);
                    }
                }
            }
    
            h = 1;
            for (int i = h; i < arr.length; i++) {
                for (int j = i; j > h - 1; j -= h) {
                    if (arr[j] < arr[j - h]) {
                        swapValue(arr, j, j - h);
                    }
                }
            }*/
                //间隔选为4 不是很合理
           /* for (int h = 4; h>0; h/=2) {
                for (int i = h; i < arr.length; i++) {
    
                    for (int j = i; j > h - 1; j -= h) {
    
                        if (arr[j] < arr[j - h]) {
                            swapValue(arr, j, j - h);
                        }
                    }
                }
            }*/
                //间隔得选取合理 ：一般第一次的增量我们选取数组长度的一半
           /* for (int h = arr.length/2; h > 0; h /= 2) {
                for (int i = h; i < arr.length; i++) {
    
                    for (int j = i; j > h - 1; j -= h) {
    
                        if (arr[j] < arr[j - h]) {
                            swapValue(arr, j, j - h);
                        }
                    }
                }
            }
    */
                //克努特序列
                //int h=1;
                //h=3*h+1; // 1,4,13,40,121,364
    
    
                //我要选择一个合适的增量 使用克努特序列来选
    
                int jianGe = 1;
                while (jianGe <= arr.length / 3) {
                    jianGe = 3 * jianGe + 1;
                }
    
                for (int h = jianGe; h > 0; h = (h - 1) / 3) {
                    for (int i = h; i < arr.length; i++) {
    
                        for (int j = i; j > h - 1; j -= h) {
    
                            if (arr[j] < arr[j - h]) {
                                int t = arr[j];
                                arr[j] = arr[j - h];
                                arr[j - h] = t;
                            }
                        }
                    }
                }
    
            }
        }

*  **合并排序**  
    原理：分而治之，递归  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 8]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 9]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 10]  
    代码如下

public class Test2 {
        public static void main(String[] args) {
    
            int arr[] = {24, 69, 80, 57, 13};
            //归并排序
            //分
            chaiFen(arr, 0, arr.length - 1);
    
            //归
            // mergerSort(arr,0,(arr.length/2)-1,arr.length-1);
    
            System.out.println(Arrays.toString(arr));
    
        }
    
        private static void chaiFen(int[] arr, int startIndex, int endIndex) {
            //计算中间索引
            int centerIndex = (startIndex + endIndex) / 2;
            //递归来拆
            if (startIndex < endIndex) {
                //拆分左边
                chaiFen(arr, startIndex, centerIndex);
                //拆分右边
                chaiFen(arr, centerIndex + 1, endIndex);
                //归并
                mergerSort(arr, startIndex, centerIndex, endIndex);
            }
        }
    
    
        /**
         * @param arr         要归并的数组
         * @param startIndex  起始索引
         * @param centerIndex 中间索引
         * @param endIndex    结束索引
         */
        private static void mergerSort(int[] arr, int startIndex, int centerIndex, int endIndex) {
            //定义一个临时数组
            int[] tempArray = new int[endIndex - startIndex + 1];
            //定义临时数组的起始索引
            int index = 0;
            //定义左边数组的起始索引
            int i = startIndex;
            //定义右边数组的起始索引
            int j = centerIndex + 1;
            //循环比较左右两边数组的元素，往临时数组里面方法
            while (i <= centerIndex && j <= endIndex) {
                //进来比较
                if (arr[i] <= arr[j]) {
                    tempArray[index] = arr[i];
                    i++; //记得递增索引
                } else {
                    tempArray[index] = arr[j];
                    j++;//记得递增索引
                }
    
                index++; //临时数组的索引
    
            }
    
            //处理左边剩余元素
    
            while (i <= centerIndex) {
                tempArray[index] = arr[i];
                i++; //记得递增索引
                index++;
            }
    
            //处理右边剩余元素
    
    
            while (j <= endIndex) {
                tempArray[index] = arr[j];
                j++; //记得递增索引
                index++;
            }
    
            //这个时候我们的临时数组里面的元素已经排序好了
    
            //  System.out.println(Arrays.toString(tempArray));
            //遍历临时数组，将临时数组中的元素，放到原数组里面去
            for (int k = 0; k < tempArray.length; k++) {
                arr[k + startIndex] = tempArray[k];
            }
    
    
        }
    }

*  **快速排序**  
    原理：先比大小，再分区
    
    代码如下

public class Test2 {
        public static void main(String[] args) {
            int arr[] = {24, 69, 80, 57, 13};
            QuickSortUtils.quickSort(arr,0,arr.length-1);
            System.out.println(Arrays.toString(arr));
        }
    }
    
    class QuickSortUtils {
    
        private QuickSortUtils() {
        }
    
        /**
         *
         * @param arr 要排序的数组
         * @param startIndex 开始索引
         * @param endIndex 结束索引
         */
        public static void quickSort(int[] arr,int startIndex,int endIndex){
            if(startIndex<endIndex){
                //找到基准数的索引
                int index=getIndex(arr,startIndex,endIndex);
                //对左右两边进行递归调用
    
                quickSort(arr,startIndex,index);
                quickSort(arr,index+1,endIndex);
    
            }
        }
    
        //
        //将基准数挖出形成第一个坑。
        //由后向前找比他小的数，找到后挖出此数填到前一个坑中。
        //由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。
        //再重复执行2，3两步骤。
    
    
        //挖坑填数
        private static int getIndex(int[] arr, int startIndex, int endIndex) {
            //定义三个变量
            int i=startIndex;
            int j=endIndex;
            //定义基准数
            int x=arr[i];
            while (i<j){
                //1. 由后向前找比他小的数，找到后挖出此数填到前一个坑中。
                while (i<j&&arr[j]>=x){
                    j--;
    
                }
                //填坑
                if(i<j){
                    arr[i]=arr[j];
                    i++;//顺便让i增一下
                }
                //2,由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中
                while (i<j&&arr[i]<x){
    
                    i++;
                }
    
                //填坑
                if (i < j) {
                    arr[j] = arr[i];
                    j--; //顺便让j减一下
                }
    
    
            }
            //以上循环完毕之后，将基准数填到最后一个坑里面去
            arr[i]=x;
    
            return i;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70]: /images/20220210/3b0829fb4c8342dcbbd5b319eadcc760.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 1]: /images/20220210/be87370cf84c416e8ce6a98776967a99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 2]: /images/20220210/9c45d744315148ae9d96c54f739bb654.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 3]: /images/20220210/4b23991b6af74d888e30c1c2246f341c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 4]: /images/20220210/b38ccd01a2f843b9bdf754e1c90ab9b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 5]: /images/20220210/22e80b4a93d64b8db10e9fb0666a7f22.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 6]: /images/20220210/31fba3998ee34678ae43b24da941f21e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 7]: /images/20220210/c5f7390d2d2c443081ecff8d44fb32a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 8]: /images/20220210/c3e2886a977e4d6783c1a52e03276078.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 9]: /images/20220210/807713303b30499fa72587ef20c7854a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTUxNjU5_size_16_color_FFFFFF_t_70 10]: /images/20220210/cafc434ef77f4e88beca59129b2d518c.png