【算法&数据结构初阶篇】：排序算法

叁歲伎倆 2024-03-29 15:04 100阅读 0赞

> 业务中我们经常会用到排序，以下作为排序入门，手写练练coding能力，选择、冒泡、插入三种排序算法。

**1.选择排序**

>     选择排序，从左往右取最小值arr[minValueIndex]，
>     然后与arr[0]交换，此时arr[0]得到最小值，接着从arr[1]，从左往右取最小值，再交换...

**2.冒泡排序**

>     冒泡排序，arr[0]与arr[1]比较，如果>,则交换，否则不交换；接着
>     arr[1]与arr[2]比较，如果>,则交换，否则不交换...直到遍历完第一轮，
>     此时arr[length-1]得到最大值，接着第二轮，[0 ~ length-2],得到第二大
>     arr[length -2]...

**3.插入排序**

>     插入排序，从左往右的时候就把前面的顺序都排好了，arr[0]与arr[1]
>     比较，如果>，则交换，然后到arr[2]，如果小于arr[1]，则交换，再接着与
>     arr[0]比较，小于则交换，如果没有比前面的小，则这一轮结束，此时0~2就升序
>     排好序，接着arr[3]，与arr[2]比较，如果大于，则直接结束，否则接着和前面三
>     个比较...

**4.代码如下：**

package class01;
    
    import java.util.Arrays;
    
    public class Code03_Sort {
        public static void swap(int[] arr, int i ,int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    
        /*
        1.选择排序，从左往右取最小值arr[minValueIndex]，
        然后与arr[0]交换，此时arr[0]得到最小值，接着从arr[1]，从左往右取最小值，再交换...
         */
        public static void selectSort(int[] arr){
            if(arr == null || arr.length == 0) {
                return;
            }
            for(int i = 0; i < arr.length; i++){
                //定义每一轮开始为当前最小值索引
                int minValueIndex = i;
                for(int j = i+1; j < arr.length; j++){
                    minValueIndex = arr[minValueIndex] > arr[j] ? j : minValueIndex;
                }
                swap(arr, i, minValueIndex);
            }
        }
    
        /*
        2.冒泡排序，arr[0]与arr[1]比较，如果>,则交换，否则不交换；接着
        arr[1]与arr[2]比较，如果>,则交换，否则不交换...直到遍历完第一轮，
        此时arr[length-1]得到最大值，接着第二轮，[0 ~ length-2],得到第二大
        arr[length -2]...
         */
        public static void bubbleSort(int[] arr){
            if(arr == null || arr.length == 0) {
                return;
            }
            for(int i = arr.length - 1; i >= 0; i--){
                for(int j = 0; j < i; j++){
                    if(arr[j] > arr[j+1]){
                        swap(arr, i, j);
                    }
                }
            }
        }
    
        /*
        3.插入排序，从左往右的时候就把前面的顺序都排好了，arr[0]与arr[1]
        比较，如果>，则交换，然后到arr[2]，如果小于arr[1]，则交换，再接着与
        arr[0]比较，小于则交换，如果没有比前面的小，则这一轮结束，此时0~2就升序
        排好序，接着arr[3]，与arr[2]比较，如果大于，则直接结束，否则接着和前面三
        个比较...
         */
        public static void insertSort(int[] arr){
            //从第二个元素开始比较
            for(int i = 1; i < arr.length; i++){
                //如果前一个元素没有越界，且大于当前元素，则交换。
                for(int j = i - 1; j>=0 && arr[j] > arr[j+1] ; j--){
                    swap(arr, j, j+1);
                }
            }
        }
    
        public static void main(String[] args) {
            int[] arr = {1,5,6,4,8,4,9,3,5,11,2};
            System.out.println(Arrays.toString(arr));
            //selectSort(arr);
    //        bubbleSort(arr);
            insertSort(arr);
            System.out.println(Arrays.toString(arr));
    
        }
    }