排序算法

标签：中转   bool   记录   临时   直接   void   小数   cts   空间   

一、冒泡排序

常用的也是简单的排序算法
个人理解：

• 步骤：往后对比、找最值、换最值
  第一层i循环次数就是要排序数组的个数
  第二层j循环可以每次都从第一个数开始往后对比，如果大\小于就交换，保证对比值一直都是最值

第二层循环条件中可以减去i，因为i每次循环后都会得一个最值往后面冒泡，即i下标后面的数已经是排序好的了不用再次对比了

//冒泡排序
public class BubbleSort {
    
    public static void main(String[] args){
        int[] arr = {3,9,-1,10,20};
        System.out.println("原数组："+Arrays.toString(arr));
        bubbleSort(arr);
    }
    
    public static void bubbleSort(int[] arr){
        int temp = 0;
        boolean flag = false;//标识变量，表示一轮对比中是否发生交换

        for (int i=0;i

二、插入排序

个人理解：

• 步骤：往前对比，找合适插入位置、记录当前值、移位、当前值插入合适位置
  第一层i循环次数也是要排序数组的个数

public class InsertSort {
    public static void main(String[] args){
        int[] arr = {3,9,-1,10,20};
        System.out.println("原数组："+ Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }
    
    public static void insertSort(int[] arr){
        int preIndex;
        int current;
        for (int i = 1; i 0  && arr[preIndex-1] > current){
                arr[preIndex] = arr[preIndex-1];//把数往前移动一位
                preIndex--;
            }
            //移动完后把当前值插入到对应位置
            arr[preIndex] = current;
        }
    }
    
}

三、选择排序

• 步骤：往后对比，一轮循环记录最小值和最小值的下标，直接交换最小值到前面
  第一层i循环次数也是要排序数组的个数

//选择排序
public class SelectSort {
    
    public static void main(String[] args){  
        int[] arr = {3,9,-1,10,20};
        System.out.println("原数组："+Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }

    public static void selectSort(int[] arr) {
        if (arr.length

四、归并排序

//归并排序
public class MergetSort {

    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        System.out.println("原数组："+ Arrays.toString(arr));
        int[] temp = new int[arr.length];
        mergetSort(arr,0,arr.length-1,temp);
        System.out.println("排序后："+Arrays.toString(arr));
    }

    //分+合的方法
    public static void mergetSort(int[] arr,int left,int right,int[] temp){
        if (left

五、快速排序

选择一个中轴值，小在左，大在右，一直分治

public class QuickSort2 {
    public static void main(String[] args){
        int[] arr = {101,34,119,1,-1,90,123};
        System.out.println("原数组："+ Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println("排序后："+Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int l = left;//记录最右边
        int r = right;//记录最左边

        // 1-基于基准值交换----快速排序就是找一个基准值，把小的放基准值前面，大的放基准值后面
        int pivot = arr[l];//获取基准值=第一个元素
        int temp = 0;//临时变量，交换使用
        while (l= pivot && l

六、基数排序

//基数排序
public class RadixSort {
    public static void main(String[] args){  
        int[] arr = {53,3,542,748,14,214};
        System.out.println("原数组："+ Arrays.toString(arr));
        radixSort(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }

    //基数排序方法
    public static void radixSort(int[] arr){

        //1-得到最大位数
        int max = arr[0];
        for (int i = 1; i  max){
                max = arr[i];
            }
        }
        //2-得到最大数是几位数
        int maxLength = (max+"").length();

        //定义一个二维数组，表示10个桶.每一行即一维数组表示一个桶
        // 为了防止放入数的时候，数据溢出，则每个一维数组（），大小定位arr.length
        // 明确：基数排序是使用空间换时间。
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中实际存放多少个数据，定义一个一维数组来记录各个桶放入数据的个数
        int[] bucketElementCounts = new int[10]; //对应存放十个桶中，最后一个元素的下标，即桶存储了几个数据

        //3-循环
        for (int i = 0,n=1; i 

七、桶排序

八、希尔排序

//希尔排序
public class ShellSort {
    public static void main(String[] args){
        int[] arr = {8,9,1,7,4,2,3,5,4,6,0};
        System.out.println("原数组："+ Arrays.toString(arr));
        shellSort2(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }

    //希尔排序----交换法
    public static void shellSort(int[] arr){
        int temp;
        for (int gap = arr.length/2; gap > 0; gap /= 2) { // 分组，每组一半
            for (int i = gap; i = 0; j-=gap) { //这里是gap对应的元素
                    //如果当前元素大于加上步长后的那个元素，就要交换
                    if (arr[j] > arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
    }

    //希尔排序----移位法
    public static void shellSort2(int[] arr){
        int temp;
        for (int gap = arr.length/2; gap > 0; gap /= 2) { // 分组，每组一半
            // 从gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i = 0 && arr[j-gap] > temp){
                        //移动
                        arr[j] = arr[j-gap];
                        j-=gap;
                    }
                    //当退出循环，说明找到插入位置
                    arr[j] = temp;
//                }
            }
        }
    }
}

排序算法

标签：中转   bool   记录   临时   直接   void   小数   cts   空间   

原文地址：https://www.cnblogs.com/xiaoaiying/p/14033694.html