排序算法

冒泡排序

代码：

package com.xiheya.sort;

/**
 * @Author {xiheya}
 * @Date: 2022/03/16/ 17:21
 * @Description
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {1,3,2,6,5,9,4};
        bubbleSort(arr);
        System.out.print("finish: [" );
        for (int x : arr) {
            System.out.print(x + "\t");
        }
        System.out.println("]");
    }

    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length - 1; 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;
                }
            }
        }
    }
}

运行结果

---

冒泡排序的优化

代码

package com.xiheya.sort;

/**
 * @Author {xiheya}
 * @Date: 2022/03/16/ 17:21
 * @Description
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {1,3,2,6,5,9,4};
        bubbleSort(arr);
        System.out.print("finish: [" );
        for (int x : arr) {
            System.out.print(x + "\t");
        }
        System.out.println("]");
    }

    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {              //确定冒泡次数
            //如果在某一次冒泡排序过程中，没有交换元素，则说明该数组已经有序。
            //冒泡步骤
            boolean flag = true;
            for (int j = 0; j < arr.length - 1 -i; j++){
                if (arr[j] > arr[j+1])
                {
                    flag = false;
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if (flag){
                break;
            }
        }
    }
}

运行结果

---

选择排序

代码

package com.xiheya.sort;

/**
 * @Author {xiheya}
 * @Date: 2022/03/16/ 17:40
 * @Description
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {1,3,-2,4,5};
        selectSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {          //开始选择排序
            //初始 min = arr[i]; mindex = i;
            int min = arr[i];
            int mindex = i;
            for (int j = i + 1; j < arr.length - 1 ; j++){
                //将min与其后面的数比较，如果min大于他后面的数  就更新min，及其下标
                if (min > arr[j]){
                    min = arr[j];
                    mindex = j;
                }
            }
            //如果 最小值的下标不等于 i 则交换 这两个元素的值
            if (mindex != i){
                arr[mindex] = arr[i];
                arr[i] = min;
            }
        }
    }
}

运行结果

---

插入排序

代码

package com.xiheya.sort;

/**
 * @Author {xiheya}
 * @Date: 2022/03/16/ 18:08
 * @Description
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {1,3,2,5,4,-1};
        insertSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //初始化insertdex  和  insertvalue
            int insertdex = i;
            int insertvalue = arr[i];
            while (insertdex > 0 && insertvalue < arr[insertdex - 1]){      //while循环，当insertdex > 0 以及 insertvalue 小于 其前一个值时进入循环
                // 将 前一个值 赋值给 下标为 insertdex的数组空间内
                arr[insertdex] = arr[insertdex - 1];
                // 下标往前移一位
                insertdex--;
            }
            //当下标等于0  或者前面的数据均没有比insertvalue小时  结束循环，将insertvalue的值赋给 arr[insertdex]
            arr[insertdex] = insertvalue;
        }
    }
}

运行结果

---

快速排序

代码

package com.xiheya.sort;

/**
 * @Author {xiheya}
 * @Date: 2022/03/16/ 19:34
 * @Description
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr ={1,3,-2,4,5,6};
        quickSort(arr,0,arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void quickSort(int[] arr,int left, int right){
        //递归退出条件
        if (left >= right){
            return;
        }
        //左指针与右指针
        int l = left;
        int r = right;
        while (l < r){
            while (l < r && arr[r] >= arr[left])r--;            //右边的元素与arr[left]比较，直到出现一个比arr[left]小的数，r指针停止左移
            while (l < r && arr[l] <= arr[left])l++;            //左边的元素与arr[left]比较，直到出现一个比arr[left]大的数，l指针停止右移
            if (l == r){                                        //当两个指针相遇时交换 arr[l]（arr[r]） 与 arr[left]的数据
                int temp = arr[l];
                arr[l] = arr[left];
                arr[left] = temp;
            }else{                                              //两个指针不相等时则交换 两指针内的数据 
                int temp = arr[r];
                arr[r] = arr[l];
                arr[l] = temp;
            }
        }
        quickSort(arr,left,l-1);                           //通过递归，将左边的元素进行快排
        quickSort(arr,r+1,right);                           //通过递归，将右边的元素进行快排。
    }
}

运行结果

---

归并排序

代码

package com.xiheya.sort;

import java.util.Arrays;

/**
 * @Author {xiheya}
 * @Date: 2022/03/16/ 23:53
 * @Description
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {1,3,2,6,4,9,7};
        int[] temp = new int[arr.length];
        mergeSort(arr,0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }


    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        if (left < right){
            int mid = (left + right) / 2;
            //分
            mergeSort(arr,0,mid,temp);          //将左边部分继续分
            mergeSort(arr,mid+1,right,temp);    //将右边部分继续分
            //合
            merge(arr,left,mid,right,temp);
        }
    }
    //合
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid+1;
        int t = 0;                          //临时数组下标索引
        //先将两部分合并
        while (i <= mid && j <= right){
            if (arr[i] <= arr[j]){
                temp[t] = arr[i];
                i++;t++;
            }else {
                temp[t] = arr[j];
                j++;t++;
            }
        }
        //如果左边没有合并完全，则接着i继续合并
        while (i <= mid){
            temp[t] = arr[i];
            t++;i++;
        }
        //如果右边没有合并完全，则接着j继续合并
        while (j <= right){
            temp[t] = arr[j];
            t++;j++;
        }
        //接着将temp中的数组填充到指定位置
        t = 0;
        int templeft = left;
        while (templeft <= right){
            arr[templeft] = temp[t];
            t++;templeft++;
        }
    }
}

运行结果

---

基数排序

代码

package com.xiheya.sort;

import java.util.Arrays;

/**
 * @Author {xiheya}
 * @Date: 2022/03/17/ 0:45
 * @Description
 */
public class RedixSort {
    public static void main(String[] args) {
        int[] arr = {10023,3225,302,155,9,3326,33,5987,663,15596};
        redixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void redixSort(int[] arr){
        int[][] bucket = new int[10][arr.length - 1];               //桶里面所存的具体数值
        int[] bucketElementCounts = new int[10];                    //每个桶所存的元素个数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(max < arr[i]) max = arr[i];
        }

        int maxCount = (max + "").length();                         //获取最大数的位数
        for (int i = 0; i < maxCount; i++) {
            //把数组中的数都放在桶里面
            for (int k = 0; k < arr.length; k++) {
                int value = arr[k] / (int) Math.pow(10, i) % 10;

                bucket[value][bucketElementCounts[value]] = arr[k];
                bucketElementCounts[value]++;
            }
            int index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++) {
                if(bucketElementCounts[k] != 0){
                    for (int x = 0; x < bucketElementCounts[k]; x++) {
                        arr[index] = bucket[k][x];
                        index++;
                    }
                }
                bucketElementCounts[k] = 0;
            }
        }

    }
}

运行结果

---