首页 > 编程语言 >八大排序算法

八大排序算法

时间:2023-07-28 20:33:45浏览次数:37  
标签:arr 八大 int param 算法 static array 排序

1. 冒泡排序

排序原理:数组元素两两比较,交换位置,大元素往后放,那么经过一轮比较后,最大的元素,就会出现在最大素引处。

/**
 * @description 冒泡排序
 * @author: PeiChen
 * @version 1.0
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {1, 24, 16, 8, 36, 5};
        BubbleSort.bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 排序原理:数组元素两两比较,交换位置,大元素往后放,那么经过一轮比较后,最大的元素,就会出现在最大素引处。
     * @param array 待排序数组
     */
    private static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
}

排序结果:

[1, 5, 8, 16, 24, 36]
2. 选择排序

排序原理:从0索引处开始,依次和后面的元素进行比较,小的元素往前放,经过一轮比较后,最小的元素就出现在了最小索引处。

/**
 * @description 选择排序
 * @author: PeiChen
 * @version 1.0
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {1, 24, 16, 8, 36, 5};
        SelectSort.selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 排序原理:从0索引处开始,依次和后面的元素进行比较,小的元素往前放,经过一轮比较后,最小的元素就出现在了最小索引处。
     * @param array 待排序数组
     */
    private static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
}

排序结果:

[1, 5, 8, 16, 24, 36]
3. 插入排序

直接插入排序:从 1 索引处开始,将后面的元素依次插入到之前的有序列表中使之仍保持有序。

/**
 * @description 直接插入排序
 * @author: PeiChen
 * @version 1.0
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {1, 24, 16, 8, 36, 5};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 直接插入排序:从 1 索引处开始,将后面的元素依次插入到之前的有序列表中使之仍保持有序。
     * @param array 待排序数组
     */
    private static void insertSort(int[] array) {
        //控制循环的次数
        for (int i = 1; i < array.length; i++) {
            int j = i;
            //升序排列直接插入,否则交换元素插入
            while (j > 0 && array[j] < array[j - 1]) {
                int temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                j--;
            }
        }
    }
}

排序结果:

[1, 5, 8, 16, 24, 36]
4. 希尔排序

希尔排序:它是对直接插入排序的一个优化,核心的思想就是合理的选取增量,经过一轮排序后,就会让序列大致有序,然后再不断的缩小增量,进行插入排序,直到增量为 1 ,即整个排序结束。

/**
 * @description 希尔排序
 * @author: PeiChen
 * @version 1.0
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {1, 24, 16, 8, 36, 5, 21, -2, 52};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 希尔排序:它是对直接插入排序的一个优化,核心的思想就是合理的选取增量,经过一轮排序后,就会让序列大致有序,
     * 然后再不断的缩小增量,进行插入排序,直到增量为 1 ,即整个排序结束。
     * @param array 待排序数组
     */
    private static void shellSort(int[] array) {
        //根据克努特序列选取我们第一次的增量
        int interval = 1;
        while (interval <= array.length / 3) {
            interval = interval * 3 + 1;
        }
        //控制增量步长
        for (int step = interval; step > 0; step = (step - 1) / 3) {
            //控制循环次数
            for (int i = step; i < array.length; i++) {
                //控制插入元素
                for (int j = i; j >= step; j -= step) {
                    if (array[j] < array[j - step]) {
                        int temp = array[j];
                        array[j] = array[j - step];
                        array[j - step] = temp;
                    }
                }
            }
        }
    }
}

排序结果:

[-2, 1, 5, 8, 16, 21, 24, 36, 52]
5. 快速排序

分治法:比大小,再分区

  1. 从数组中取出一个数,作为基准数。
  2. 分区:将比这个数大或等于的数全放到他的右边,小于它的数全放到它的左边。
  3. 再对左右区间重复第二步,直到各区间只有一个数。
/**
 * @description 快速排序
 * @author: PeiChen
 * @version 1.0
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {1, 24, 16, 8, 36, 5, 21, -2, 52};
        quickSort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    private static void quickSort(int[] array, int start, int end) {
        //找出分开左右分区的索引位置,然后分别对左右两区进行递归排序
        if (start < end) {
            int index = partition(array, start, end);
            quickSort(array,start,index - 1);
            quickSort(array,index + 1,end);
        }
    }

    /**
     * 1.将基准数挖出形成第一个坑
     * 2.由后向前找比他小的数,找到后挖出此数填到前一个坑中
     * 3.由前向后找比他大或等于的数,找到后也挖出此数填到前一个坑中
     * 4.再重复执行2,3两步骤。
     * @param array 待分区数组
     * @param start 起始位置
     * @param end 终止位置
     * @return 分区的索引
     */
    private static int partition(int[] array, int start, int end) {
        int i = start;
        int j = end;
        //将基准数挖出形成第一个坑
        int baseVal = array[i];
        while (i < j) {
            //由后向前找比较小的数,找到后挖出此数填到一个坑中
            while (i < j && array[j] >= baseVal) {
                j--;
            }
            if (i < j) {
                array[i] = array[j];
                i++;
            }
            //由前向后找比较大或等于的数,找到后也挖出此数填到前一个坑中
            while (i < j && array[i] < baseVal) {
                i++;
            }
            if (i < j) {
                array[j] = array[i];
                j--;
            }
            //把基准数填到最后一个坑中
            array[i] = baseVal;
        }
        return i;
    }
}

排序结果:

[-2, 1, 5, 8, 16, 21, 24, 36, 52]
6. 归并排序

归并排序( Merge Sort)就是利用归并的思想实现排序的方法。它的原理是假设初始序列有N个记录,则可以看成是N个有序的子序列,每个子序列的长度为 1 ,然后两两归并得到N/2个长度为2或1的有序子序列,再两两归并... 如此重复直至得到一个长度为N的有序序列为止,这种排序方法称为2路归并排序。

/**
 * @description 归并排序
 * @author: PeiChen
 * @version 1.0
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {1, 24, 16, 8, 36, 5, 21, -2, 52};
        split(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 拆分数组
     * @param arr 原始数组
     * @param startIndex 起始索引
     * @param endIndex 结束索引
     */
    private static void split(int[] arr, int startIndex, int endIndex) {
        //寻找中间索引
        int centerIndex = (startIndex + endIndex) / 2;
        if (startIndex < endIndex) {
            split(arr,startIndex,centerIndex);
            split(arr,centerIndex + 1,endIndex);
            merge(arr,startIndex,centerIndex,endIndex);
        }
    }

    /**
     * 归并数组
     * @param arr 原始数组
     * @param startIndex 起始索引
     * @param centerIndex 中间索引
     * @param endIndex 结束索引
     */
    private static void merge(int[] arr, int startIndex, int centerIndex, int endIndex) {
        int[] tempArr = new int[endIndex - startIndex + 1];
        //定义左边数组的起始索引
        int i = startIndex;
        //定义右边数组的起始索引
        int j = centerIndex + 1;
        //临时数组的起始索引
        int index = 0;
        //比较两个数组中的元素大小,然后往临时数组里添加
        while (i <= centerIndex && j <= endIndex) {
            if (arr[i] <= arr[j]) {
                tempArr[index] = arr[i];
                i++;
            } else {
                tempArr[index] = arr[j];
                j++;
            }
            index++;
        }
        //处理剩余元素
        while (i <= centerIndex) {
            tempArr[index] = arr[i];
            i++;
            index++;
        }
        while (j <= endIndex) {
            tempArr[index] = arr[j];
            j++;
            index++;
        }
        //将临时数组的元素取到原始数组中
        for (int k = 0; k < tempArr.length; k++) {
            arr[startIndex + k] = tempArr[k];
        }
    }
}

排序结果:

[-2, 1, 5, 8, 16, 21, 24, 36, 52]
7. 基数排序

基数排序不同于之前所介绍的各类排序,前边介绍到的排序方法或多或少的是通过使用比较和移动记录来实现排序。而基数排序的实现不需要进行对关键字的比较,只需要对关键字进行"分配"与"收集"两种操作即可完成。

/**
 * @description 基数排序(桶排序)(此案例只适用于非负数,负数再加一个判断即可)
 * @author: PeiChen
 * @version 1.0
 */
public class BaseSort {
    public static void main(String[] args) {
        int[] arr = {1, 24, 16, 8, 36, 28, 5, 21, 2, 52, 666, 127, 520, 68};
        baseSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 基数排序:先分配再收集
     * @param arr 待排序数组
     */
    private static void baseSort(int[] arr) {
        //定义二维数组,放10个桶
        int[][] tempArr = new int[10][arr.length];
        //定义统计数组
        int[] counts = new int[10];
        //计算最大数的位数
        int maxLength = getMaxLength(arr);
        //循环次数
        for (int i = 0, k = 1; i < maxLength; i++, k*= 10) {
            //分配
            for (int value : arr) {
                //获取每位上的数字
                int everyNum = value / k % 10;
                //放到对应的桶内,并且对每个桶中的元素计数
                tempArr[everyNum][counts[everyNum]++] = value;
            }
            //收集
            int index = 0;
            for (int m = 0; m < counts.length; m++) {
                if (counts[m] != 0) {
                    for (int n = 0; n < counts[m]; n++) {
                        //从桶中取出元素放入原数组
                        arr[index++] = tempArr[m][n];
                    }
                    //清空上一次统计的个数
                    counts[m] = 0;
                }
            }
        }
    }

    private static int getMaxLength(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return String.valueOf(max).length();
    }

}

排序结果:

[1, 2, 5, 8, 16, 21, 24, 28, 36, 52, 68, 127, 520, 666]
8. 堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序。 堆排序的基本思想:

  1. 将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。
  2. 将其与末尾元素进行交换,此时末尾就为最大值。
  3. 然后将剩余 n-1 个元素重新构造成一个堆,这样会得到 n 个元素的次小值。
  4. 如此反复执行,便能得到一个有序序列了。
/**
 * @description 堆排序
 * @author: PeiChen
 * @version 1.0
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {1, 24, 16, 8, 36, 28, 5, 21, 2, 52, 666, 127, 520, 68};
        //开始调整的位置
        int startIndex = (arr.length - 1) / 2;
        //循环调整大顶堆
        for (int i = startIndex; i >= 0; i--) {
            toBigHeap(arr,arr.length,i);
        }
        //循环把根元素与最后一个元素进行交换
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //调整完之后继续把剩余元素调整为大顶堆
            toBigHeap(arr,i,0);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 把一个数组转换成大顶堆
     * @param arr 原始数组
     * @param size 调整的元素个数
     * @param index 开始调整的位置
     */
    private static void toBigHeap(int[] arr, int size, int index) {
        //获取左右子节点的索引
        int leftNodeIndex = index * 2 + 1;
        int rightNodeIndex = index * 2 + 2;
        //查找最大节点所对应的索引
        int maxIndex = index;
        if (leftNodeIndex < size && arr[leftNodeIndex] > arr[maxIndex]) {
            maxIndex = leftNodeIndex;
        }
        if (rightNodeIndex < size && arr[rightNodeIndex] > arr[maxIndex]) {
            maxIndex = rightNodeIndex;
        }
        //如果最大元素不是当前元素,则需调换位置
        if (maxIndex != index) {
            int temp = arr[maxIndex];
            arr[maxIndex] = arr[index];
            arr[index] = temp;
            //交换完位置以后很有可能会破坏原先大顶堆结构,所以还需重新调换
            toBigHeap(arr,size,maxIndex);
        }
    }
}

排序结果:

[1, 2, 5, 8, 16, 21, 24, 28, 36, 52, 68, 127, 520, 666]

标签:arr,八大,int,param,算法,static,array,排序
From: https://blog.51cto.com/u_16167640/6886757

相关文章

  • 对称加密算法
    对称加密算法:指加密和解密都是同一个密钥。  包括DES,DES3,AES 参考这篇博文:(50条消息)什么是对称加密(对称加密简介)_AtlanSI的博客-CSDN博客......
  • 洛谷 P1347 排序 - 拓扑排序
    P1347排序题意依次给一些具有排序关系的序列,问你在能否在若干个序列之后确定元素的顺序、判断元素关系存在矛盾、判断无法确认元素顺序思路对于每一个排序关系均进行toposort,后面就是toposort判环(出现矛盾),toposort判顺序,无法确认唯一关系。详见代码或看洛谷题解区代码......
  • 【C语言】二分查找算法
    在⼀个升序的数组中查找制定的数字n,很容易想到的⽅法就是遍历数组,但是这种⽅法效率⽐较低,⽐如我买了⼀双鞋,你好奇问我多少钱,我说不超过300元。你还是好奇,你想知道到底多少,我就让你猜,你会怎么猜?你会1,2,3,4...这样猜吗?显然很慢;⼀般你都会猜中间数字,⽐如:150,然后看⼤了还是⼩了,这就是......
  • 关于异或算法找唯一
    1.公式: a⊕b=b⊕a(交换律)a⊕b⊕c=a⊕(b⊕c)(结合律)a⊕0=a(恒等率)a⊕a=0 2.应用场景:给出一些数字,这些数字里面只有一个是不重复的,请问怎么找到他?其实,就是用异或的交换律和结合律,把这些数字n1n2.....nk异或起来,会发现最终结......
  • 高手算法专项训练-期望问题
    高手算法专项训练-期望问题T1猫抓老鼠​ 我们可以设猫在点\(u\)老鼠在\(v\)点时猫抓到老鼠的期望时间为\(f_{u,v}\),设此时猫的目标点为\(next_{u,v}\),而这个\(next_{u,v}\)很显然可以在跑\(n\)便BFS。注意\(f\)的转移顺序显然由\(u,v\)的距离来决定。所以......
  • 3.2 排序 参考代码
    P1059[NOIP2006普及组]明明的随机数计数排序#include<cstdio>inta[1005];intmain(){ intn,cnt=0; scanf("%d",&n); for(inti=1;i<=n;i++){ intx;scanf("%d",&x); if(a[x]==0){//这个数没出现过(第一次出现) a[x]=......
  • 拓扑排序
    拓扑排序给定一张有向无环图,排出所有顶点的一个序列A满足:对于图中的每条有向边(x,y)x在A中的出现都在y之前,则称A是改图的顶点的一个拓扑序。如图所示,{2351746},{3215764}都是合法的拓扑序。用途:可以判断有向图中是否有环,可以生成拓扑排序Kahn算法实现拓扑排序e......
  • 【实践篇】推荐算法PaaS化探索与实践
    作者:京东零售崔宁1.背景说明目前,推荐算法部支持了主站、企业业务、全渠道等20+业务线的900+推荐场景,通过梳理大促运营、各垂直业务线推荐场景的共性需求,对现有推荐算法能力进行沉淀和积累,并通过算法PaaS化打造通用化的推荐能力,提升各业务场景推荐赋能效率,高效赋能业务需求。......
  • 代码随想录算法训练营第四十天| 300.最长递增子序列 674. 最长连续递增序列 718.
    300.最长递增子序列要求:可以删减任意个节点,最后保存最大的递增长度难点:410489如何保证全局的视角,看到很前面的节点是否大于当前的节点,而不是仅仅记录状态思路:dp[n],当子序列的末尾为N时,它的最大子序列长度也就意味着,N在它的子序列中是最大的,遍历这个N之前的所有序......
  • SHA1签名算法,JAVA和C#
    java:publicstaticvoidmain(String[]args)throwsNoSuchAlgorithmException{Stringtoken="31a4a1aa-cffc-4aca-9ef6-0497edf7fbed";Stringnonce="Rzem0rlz19e6GZuZuFKyDzaxiS4baaqn8uvxVnntXKS";Stringtimestamp="1646......