IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 一篇秒懂八大排序 -> 正文阅读

[数据结构与算法]一篇秒懂八大排序

一、冒泡排序

1、基本思想:依次比较相邻两个数,小的在前,大的在后
2、动态效果图
在这里插入图片描述
3、代码实现

private static void bubbleSort(int[] arr){
        //标识变量,表示是否进行交换
        boolean flag=false;
        int temp=0;
        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]){
        flag=true;
        temp=arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=temp;
        }
        }
        if(!flag){
        break;
        }
        }
        }

二、选择排序

1、基本思想:在序列中找到最小元素,放在第一个位置;从剩余未排序元素中继续找到最小的元素,放在第二个位置…以此类推,直到排序完毕。
2、动态效果图
在这里插入图片描述
3、代码实现

private static void selectSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            int minIndex = i;
            int min = arr[minIndex];
        for(int j = 1 + i;j<arr.length;j++){
        if(min > arr[j]){
        min = arr[j];
        minIndex = j;
        }
        }
        arr[minIndex] = arr[i];
        arr[i] = min;
        }
        }

三、插入排序

1、基本思想:把n个待排序的元素第一位看成有序表,其它的看成无序表,排序过程中,每次从无序表中取出一个数,依次与有序表中的数进行比较,插入到合适的位置。
2、动态效果图
在这里插入图片描述

3、代码实现

public static void insertSort(int[] arr ){
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
        //待插入的数
        insertVal = arr[i];
        insertIndex = i - 1;
        // 给insertVal 找到插入的位置
        // 1. insertIndex >= 0 保证在给insertVal 找插入位置,不越界
        // 2. insertVal < arr[insertIndex] 待插入的数,还没有找到插入位置
        // 3. 将 arr[insertIndex] 后移
        while(insertIndex >= 0 && insertVal < arr[insertIndex]){
        arr[insertIndex+1] = arr[insertIndex];
        insertIndex--;
        }
        // 当退出while循环时,说明插入的位置找到, insertIndex + 1
        if(insertIndex + 1 != i){
        arr[insertIndex+1] = insertVal;
        }
        }
        }

四、希尔排序

1、基本思想:希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。它与插入排序的不同之处在于,它会优先比较较远的元素。
2、效果图
在这里插入图片描述
3、代码实例
a.冒泡版希尔排序

public static void shellSort(int[] arr) {
    for(int step = arr.length/2;step > 0;step /= 2) {
        for(int i = step;i < arr.length;i++) {
            //遍历组中的所有元素(共step组,每组有个元素),步长step组
        for(int j = i - step;j >= 0;j -= step) {
            //如果当前元素大于加上步长后的那个元素,交换
        if(arr[j] > arr[j + step]) {
            int temp = arr[j];
            arr[j] = arr[j + step];
            arr[j + step] = temp;
        }
        }
        }
        }
        }

b.插入版希尔排序

public static void shellSort(int[] arr){
        for(int step=arr.length/2;step>0;step/=2){
        for(int i=step;i<arr.length;i++){
        int j=i;
        int temp=arr[j];
        if(arr[j]<arr[j-step]){
        while(j-step>=0&&temp<arr[j-step]){
        arr[j]=arr[j-step];
        j-=step;
        }
        arr[j]=temp;
        }
        }
        }
        }

五、快速排序

1、基本思想:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录进行排序,以达到整个排序的过程。
2、效果图
在这里插入图片描述
思路:使用分治法把一个串分为两个子串;找一个基准点,暂时选中间点为基准点;重新排序数列,比基准值小的放在基准点前面,大的放在后面;递归的把小于基准值的子数列和大于基准值的子数列排序。
3、代码实现

public static void quickSort(int[] arr,int left,int right){
    int l = left;
    int r = right;
    int pivot = arr[(left + right) / 2];
    int temp = 0;
    //while循环让比pivot值小的放在左边,比pivot值大的放在右边
        while(l < r) {
            //在pivot的左边一直找,找到大于等于pivot的值,才退出
        while(arr[l] < pivot) {
            l += 1;
        }
        //在pivot的右边一直找,找到小于等于pivot的值,才退出
        while(arr[r] > pivot) {
            r -= 1;
        }
        //如果l>=r说明privot左右两边的值,左边小于等于pivot,右边大于等于pivot
        if(l >= r) {
            break;
        }
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        //如果交换后,arr[l]==privot值相等r--,前移
        if(arr[l] == privot) {
            r -= 1;
        }
        //如果交换后,arr[l]==privot值相等l++,后移
        if(arr[r] == privot) {
        l += 1;
        }
        }
        //如果l==r,必须l++,r--,否则出现栈溢出
        if(l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if(left < r) {
            quickSort(arr,left,r);
        }
        //向右递归
        if(right > l) {
        quickSort(arr,l,right);
        }
        }

六、归并排序

1、基本思想:采用经典的分治策略,分治法将问题分成一些小的问题然后递归解决,则治的阶段就是将分的阶段得到的答案综合在一起,分而治之。
2、效果图

3、代码实现

public static void mergerSort(int[] arr,int left,int right,int[] temp){
        if(left<right){
        int middle = (left + right)/2;
        //向左递归进行分解
        mergerSort(arr,left,middle,temp);
        //向右递归进行分解
        mergerSort(arr,middle + 1,right,temp);
        //合并
        merger(arr, left, middle, right, temp);
        }
        }
//合并
public static void merger(int[] arr,int left,int middle,int right,int[] temp){
        int i = left; // 初始化i, 左边有序序列的初始索引
        int j = middle + 1; //初始化j, 右边有序序列的初始索引
        int t = 0; // 指向temp数组的当前索引
        //先把左右两边(有序)的数据按照规则填充到temp数组,直到左右两边的有序序列,有一边处理完毕为止
        while (i <= middle && j <= right) {
        //如果左边的有序序列的当前元素小于等于右边有序序列的当前元素,将左边的当前元素,填充到 temp数组,然后 t++, i++
        if(arr[i] <= arr[j]){
        temp[t] = arr[i];
        t++;
        i++;
        }else {//将右边有序序列的当前元素,填充到temp数组
        temp[t] = arr[j];
        t++;
        j++;
        }
        }
        //把有剩余数据的一边的数据依次全部填充到temp
        //左边的有序序列还有剩余的元素,就全部填充到temp
        while (i <= middle){
        temp[t] = arr[i];
        t++;
        i++;
        }
        //右边的有序序列还有剩余的元素,就全部填充到temp
        while (j <= right){
        temp[t] = arr[j];
        t++;
        j++;
        }
        //将temp数组的元素拷贝到arr(注意,并不是每次都拷贝所有)
        t = 0;
        int tempLeft = left; //
        while (tempLeft <= right){
        arr[tempLeft] = temp[t];
        t++;
        tempLeft++;
        }
        }

七、基数排序

1、基本思想:将所有带比较数值统一为同样的数位长度,数据较短的数前面补0,然后从最低位开始依次进行依次排序,这样从最低位排序一直到最高位排序完成之后,数列就变成了一个有序序列。
2、代码实现

public static void radixSort(int arr[]){
        System.out.println("基数排序,arr长度:"+arr.length);
        //1. 得到数组中最大的数的位数
        int max = arr[0]; //假设第一数就是最大数
        for(int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
        max = arr[i];
        }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();
        //定义一个二维数组,表示10个桶, 每个桶就是一个一维数组
        //1. 二维数组包含10个一维数组
        //2. 为了防止在放入数的时候,数据溢出,则每个一维数组(桶),大小定为arr.length
        //3.基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //比如:bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];
        for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
        //(针对每个元素的对应位进行排序处理), 第一次是个位,第二次是十位,第三次是百位..
        for(int j = 0; j < arr.length; j++) {
        //取出每个元素的对应位的值
        int digitOfElement = arr[j] / n % 10;
        //放入到对应的桶中
        bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
        bucketElementCounts[digitOfElement]++;
        }
        //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来数组)
        int index = 0;
        //遍历每一桶,并将桶中是数据,放入到原数组
        for(int k = 0; k < bucketElementCounts.length; k++) {
        //如果桶中有数据,我们才放入到原数组
        if(bucketElementCounts[k] != 0) {
        //循环该桶即第k个桶(即第k个一维数组), 放入
        for(int l = 0; l < bucketElementCounts[k]; l++) {
        //取出元素放入到arr
        arr[index++] = bucket[k][l];
        }
        }
        //第i+1轮处理后,需要将每个 bucketElementCounts[k] = 0 
        bucketElementCounts[k] = 0;
        }
        }
        }

八、堆排序

1、基本思想
大顶堆:每个节点的值都大于或者等于它的左右子节点的值。
小顶堆:每个节点的值都小于或者等于它的左右子节点的值。
2、效果图

3、思路(大根堆)
a.首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端
b.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1
c.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组
注意:升序用大根堆,降序就用小根堆(默认为升序)
4、代码实现
大根堆

package Sort;
import java.util.Arrays;
public class HeapSort {
    //调整大顶堆
    /**
     * @param arr     待调整数组
     * @param i       非叶子结点在数组中的索引
     * @param length  调整元素个数(length在逐渐减少)
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];//取出当前元素i
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始,即2i+1处开始
            if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点,则k指向右子结点(arr[k]表示左子结点,arr[k+1]表示右子结点)
                k++;
            }
            if (arr[k] > temp) {//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                arr[i] = arr[k];
                i = k;//i指向k,即将较小值放在较大值下方
            } else {
                break;//我们是自下而上进行调整即可保证下方子树已为大顶堆
            }
        }//当for循环结束后,我们将以i为父结点的树的最大值放在局部堆顶
        arr[i] = temp;//将temp值放到调整后的位置
    }

    public static  void swap(int[] arr,int a,int b) {//交换元素
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

    public static void heapsort(int[] arr) {
        for(int i=arr.length/2-1;i>=0;i--) {//从第一个非叶子结点从下至上,从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }

        for(int j=arr.length-1;j>0;j--) {
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }
    }
    public static void main(String[] args) {
        int[] arr= {2,10,8,22,34,5,12,28,21,11};
        System.out.println("堆排序前:");
        System.out.println(Arrays.toString(arr));
        heapsort(arr);
        System.out.println("堆排序后:");
        System.out.println(Arrays.toString(arr));
    }
}

在这里插入图片描述
小根堆

package Sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class HeapSort {
    //调整小顶堆
    /**
     * @param arr     待调整数组
     * @param i       非叶子结点在数组中的索引
     * @param length  调整元素个数(length在逐渐减少)
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];//取出当前元素i
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始,即2i+1处开始
            if (k + 1 < length && arr[k] > arr[k + 1]) {//如果左子结点大于右子结点,则k指向左子结点(arr[k]表示左子结点,arr[k+1]表示右子结点)
                k++;
            }
            if (arr[k] < temp) {//如果子节点小于父节点,将子节点值赋给父节点(不用进行交换)
                arr[i] = arr[k];
                i = k;//i指向k,即将较大值放在较小值下方
            } else {
                break;//我们是自下而上进行调整即可保证下方子树已为小顶堆
            }
        }//当for循环结束后,我们将以i为父结点的树的最小值放在局部堆顶
        arr[i] = temp;//将temp值放到调整后的位置
    }
    public static  void swap(int[] arr,int a,int b) {//交换元素
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
    public static void heapsort(int[] arr) {
        for(int i=arr.length/2-1;i>=0;i--) {//从第一个非叶子结点从下至上,从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }

        for(int j=arr.length-1;j>0;j--) {
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }
    }
    public static void main(String[] args) {
        int[] arr= {2,10,8,22,34,5,12,28,21,11};
        System.out.println("堆排序前:");
        System.out.println(Arrays.toString(arr));
        heapsort(arr);
        System.out.println("堆排序后:");
        System.out.println(Arrays.toString(arr));
    }
}

在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-06-08 19:12:50  更:2022-06-08 19:14:48 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 1:31:41-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码