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 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> LeetCode算法—排序算法(以升序为例) -> 正文阅读

[数据结构与算法]LeetCode算法—排序算法(以升序为例)

配套视频https://www.bilibili.com/video/BV1PT4y13767?p=2&vd_source=3558fd85254f40ca0361146cc92d2cce

一、归并排序

1. 归并排序原理

执行流程

  1. 不断地将当前序列平均分割成2个子序列,直到不能再分割(序列中只剩一个元素)
  2. 不断地将子序列合并成一个有序序列,直到最终只剩下一个有序序列

在这里插入图片描述

2. 归并排序代码实现

public class Test {

    public static void mergeSort(int [] array,int start,int end){
        if(end-start<2) {
           return;
        }
        int mid = (start + end) >> 1;
        mergeSort(array, start, mid);
        mergeSort(array, mid, end);
        //归并
        merge(array,start,mid,end);
    }


    public static void merge(int [] array,int start,int mid,int end){
        int[] leftArray=new int[mid-start];
        //复制数组左边部分到新数组
        System.arraycopy(array,start,leftArray,0,mid-start);
        int arrayIndex=start;
        int lIndex=0;
        int lEnd=leftArray.length;
        int rIndex=mid;
        int rEnd=end;
        while(lIndex<lEnd) {
            if (rIndex<rEnd) {
                if (leftArray[lIndex] < array[rIndex]) {
                    array[arrayIndex++] = leftArray[lIndex++];
                } else {
                    array[arrayIndex++] = array[rIndex++];
                }
            }else{
                array[arrayIndex++] = leftArray[lIndex++];
            }
        }
    }

    public static void main(String[] args) {
        int [] array={3,2,1};
        mergeSort(array,0,array.length);
        for (int num:array) {
            System.out.print(num +"\t");
        }
    }
}

二、快速排序

1. 快速排序原理

快速排序原理是首先要找到一个中枢,把小于中枢的值放到他前面,大于中枢的值放到他的右边,然后再以此方法对这两部分数据分别进行快速排序。

这里是先用待排数组的第一个作为中枢,把数组划分两部分,小于他的往前挪,那大于他的自然就在后面了,然后再把中枢值放到大于和小于他之间的位置。
在这里插入图片描述

2. 快速排序代码实现

public class Test {

    public static void quickSort(int [] array,int start,int end){
       if (end-start<2){
           return;
       }
        int j=start;
        int key=array[start];
        for (int i = start+1; i < end; i++) {
            if (key>array[i]){
                j++;
                swap(array,j,i);
            }
        }
        swap(array,j,start);
        quickSort(array,start,j);
        quickSort(array,j+1,end);
    }

    public static void swap(int []array,int j,int i){
        int tmp=array[j];
        array[j]=array[i];
        array[i]=tmp;
    }
    public static void main(String[] args) {
        int [] array={7};
        quickSort(array,0,array.length);
        for (int num:array) {
            System.out.print(num +"\t");
        }
    }
}

三、冒泡排序

1. 冒泡排序原理

将第一个元素和第二个元素比较,若前者大于后者,则交换两者的位置,再将第二个元素与第三个元素比较,若前者大于后者则交换两者位置,以此类推直到倒数第二个元素与最后一个元素比较,若前者大于后者,则交换两者位置。这样一轮比较下来将会把序列中最大的元素移至序列末尾,这样就安排好了最大数的位置,接下来只需对剩下的(n-1)个元素,重复上述操作即可。

2. 冒泡排序代码实现

public class Test {

    public static void swap(int []array,int j,int i){
        int tmp=array[j];
        array[j]=array[i];
        array[i]=tmp;
    }

    private static void bubbleSort(int[] array){
        for (int j=array.length-1;j>0;j--){
            for (int i=0;i<j;i++){
                if (array[i]>array[i+1]){
                    swap(array,i,i+1);
                }
            }
        }
    }

    public static void main(String[] args) {
        int [] array={999999998,999999996};
        bubbleSort(array);
        for (int num:array) {
            System.out.print(num +"\t");
        }
    }
}

四、选择排序

1. 选择排序原理

执行流程

  1. 从序列中找出最大的那个元素,然后与最末尾的元素交换位置(执行完一轮后,最末尾的那个元素就是最大的元素)
  2. 忽略1中曾经找到的最大元素,重复执行步骤1

2. 选择排序代码实现

public class Test {

    public static void swap(int []array,int j,int i){
        int tmp=array[j];
        array[j]=array[i];
        array[i]=tmp;
    }

    public static void selectionSort(int []arr){
        for (int j=arr.length;j>1;j--){
            int maxIndex=0;
            for (int i=1;i<j;i++){
                if (arr[maxIndex]<arr[i]){
                   maxIndex=i;
                }
            }
            swap(arr,maxIndex,j-1);
        }
    }

    public static void main(String[] args) {
        int [] array={2,4,1};
        selectionSort(array);
        for (int num:array) {
            System.out.print(num +"\t");
        }
    }
}

五、插入排序

1. 插入排序原理

插入排序非常类似于扑克牌的排序
在这里插入图片描述执行流程

  1. 在执行过程中,插入排序会将序列分为2部分(头部是已经排好序的,尾部是待排序的)
  2. 从头开始扫描每一个元素(每当扫描到一个元素,就将它插入到头部合适的位置,使得头部数据依然保持有序)
    在这里插入图片描述

2. 插入排序代码实现

public class Test {

    public static void swap(int []array,int j,int i){
        int tmp=array[j];
        array[j]=array[i];
        array[i]=tmp;
    }

	//第一种方式(优先)
 	public static void insertionSort(int []array){
        for (int begin=1;begin<array.length;begin++){
            int cur=begin;
            while (cur>0 && array[cur]<array[cur-1]){
                swap(array,cur,cur-1);
                cur--;
            }
        }
    }

		//第二种方式
		//用的插入扑克牌的方式写的
    public static void insertionSort(int []array){
        int j=0;
        for (int i=1;i<array.length;i++){
            int end=j;
            while (j>=0){
                if (array[j] < array[i]) {
                    break;
                }
                if (j-1>=0) {
                    if (array[j] > array[i] && array[i] > array[j - 1]) {
                        int tmp=array[i];
                        System.arraycopy(array, j, array, j + 1, end - j + 1);
                        array[j]=tmp;
                        break;
                    }
                }
                if(j==0) {
                    int tmp=array[i];
                    System.arraycopy(array, j, array, j + 1, end - j + 1);
                    array[j] = tmp;
                    break;
                }
                j--;
            }
            j=end+1;
        }
    }

    public static void main(String[] args) {
        int [] array={5,2,1,4};
        insertionSort(array);
        for (int num:array) {
            System.out.print(num +"\t");
        }
    }
}

希尔排序

1. 希尔排序原理

2. 希尔排序代码实现

public class Test {

    public static void swap(int []array,int j,int i){
        int tmp=array[j];
        array[j]=array[i];
        array[i]=tmp;
    }

    public static void shellSort(int array[]){
        List<Integer> stepList=new ArrayList();
        stepList=shellStepSequence(array);
        for (int step:stepList){
            for (int col = 0; col < step; col++) {
                for (int i = col+step ; i < array.length ; i+=step) {
                    for (int cur=i;cur>=col+step;cur-=step) {
                        if (array[cur] < array[cur - step]) {
                            swap(array, cur, cur - step);
                        }else{
                            break;
                        }
                    }
                }
            }
        }
    }

    public static List shellStepSequence(int [] array){
        List stepList=new ArrayList();
        int step=array.length;
        while ((step>>=1)>=1){
            stepList.add(step);
        }
        return stepList;
    }

    public static void main(String[] args) {
        int [] array={5,2,3,1,4};
        shellSort(array);
        for (int num:array) {
            System.out.print(num +"\t");
        }
    }
}

希尔排序

希尔排序把序列看做是一个矩阵,分成m列,逐列进行排序

  1. m从某个整数逐渐减为1
  2. 当m为1时,整个序列将完全有序

矩阵的列数取决于步长序列

  • 比如,如果步长序列为{1,5,19,41,109},就代表依次分成109列,41列,19列,5列,1列。
  • 不同的步长序列,执行效率也不同。
    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述插入排序的时间复杂度与逆序对的数量成正比关系,逆序对的数量越多,插入排序的时间复杂度越高。

七、计数排序

1. 计数排序原理

冒泡、选择、插入、归并、快速、希尔、堆排序都是基于比较的排序,平均时间复杂度目前最低是O(nlogn)

计数排序、桶排序、基数排序都不是基于比较的排序,它们是典型的空间换时间,在某些时候,平均复杂度可以比O(nlogn)更低。

计数排序适合一定范围内的整数进行排序

计数排序的核心思想统计每个整数在序列中出现的次数,进而推导出每个整数在有序序列中的索引。

在这里插入图片描述

2. 计数排序代码实现

public class Test {

    public static void swap(int []array,int j,int i){
        int tmp=array[j];
        array[j]=array[i];
        array[i]=tmp;
    }

    public static void countSort(int arr[]){
        int max=arr[0];
        for (int i=1;i<arr.length;i++){
            if (max<arr[i]){
                max=arr[i];
            }
        }
        int []countArr=new int[max+1];
        for (int i=0;i<arr.length;i++){
            countArr[arr[i]]++;
        }
        int i=0;
        for(int index=0;index<countArr.length;index++){
            while (countArr[index]-->0){
                arr[i++]=index;
            }
        }
    }

    public static void main(String[] args) {
        int [] array={1,2};
        countSort(array);
        for (int num:array) {
            System.out.print(num +"\t");
        }
    }
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-07-04 23:13:18  更:2022-07-04 23:13:41 
 
开发: 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年12日历 -2024/12/29 8:04:13-

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