您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

面试过程中常见的排序算法问题你见个?附常见排序算法源代码

时间:2023-10-09 16:44:25  来源:今日头条  作者:架构师老卢

在面试过程中,排序算法常常是一个重要的考点。排序算法的熟练掌握不仅能展现出候选人对基本数据结构的理解,也能展示出他们的算法设计和问题解决能力。下面我们将详细讨论几种常见的排序算法及其在面试中的应用。

一、选择排序(Selection Sort)

选择排序是一种简单直观的排序算法,它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

JAVA源代码示例

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

二、冒泡排序(Bubble Sort)

冒泡排序的工作原理是,对相邻的元素进行两两比较,顺序相反则进行交换,这样每一轮过后最小(或最大)的元素会被移到序列的最后。

Java源代码示例

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

三、插入排序(Insertion Sort)

插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

Java源代码示例

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

四、快速排序(Quick Sort)

快速排序是一种分治的排序算法,它将原始数据分割成两个或更多的子序列,然后对每个子序列进行排序,最后将有序的子序列合并为整体有序序列。

Java源代码示例

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high]; 
    int i = (low - 1); 
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

五、归并排序(Merge Sort)
归并排序也是一种分治的排序算法,它将原始数据分割成两个或更多的子序列,然后对每个子序列进行排序,最后将有序的子序列合并为整体有序序列。但是,归并排序采用了分治与合并相互独立的方式进行设计。在每一步的处理上,归并排序将序列分为两部分进行独立的排序,然后合并成一个有序的序列。这种设计方式使得归并排序在处理大数据量的情况下表现得更好。

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        sortProcess(arr, 0, arr.length - 1);
    }

    public static int[] getSubArray(int[] arr, int l, int r) {
        int[] subArr = new int[r - l + 1];
        for (int i = 0; i < subArr.length; i++) {
            subArr[i] = arr[l + i];
        }
        return subArr;
    }

    public static void sortProcess(int[] arr, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sortProcess(arr, l, m);
            sortProcess(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

    public static void merge(int[] arr, int l, int m, int r) {
        int[] leftArr = getSubArray(arr, l, m);
        int[] rightArr = getSubArray(arr, m + 1, r);
        int left = 0;
        int right = 0;
        int index = l;
        while (left < leftArr.length && right < rightArr.length) {
            if (leftArr[left] <= rightArr[right]) {
                arr[index] = leftArr[left];
                left++;
            } else {
                arr[index] = rightArr[right];
                right++;
            }
            index++;
        }
        while (left < leftArr.length) {
            arr[index] = leftArr[left];
            left++;
            index++;
        }
        while (right < rightArr.length) {
            arr[index] = rightArr[right];
            right++;
            index++;
        }
    }
}

使用方法:

public static void mAIn(String[] args) {
    int[] arr = {5, 3, 2, 6, 8, 1};
    MergeSort mergeSort = new MergeSort();
    mergeSort.mergeSort(arr);
    for (int i : arr) {
        System.out.print(i + " ");
    }
}

这个程序会对数组进行归并排序,排序后的数组会打印出来。注意,这是一个基本的归并排序实现,它可能不适用于所有可能的输入。如果你有特定的排序需求或大型数据集,可能需要优化该算法或使用其他算法。



Tags:排序算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
我们一起聊聊C#堆排序算法
前言堆排序是一种高效的排序算法,基于二叉堆数据结构实现。它具有稳定性、时间复杂度为O(nlogn)和空间复杂度为O(1)的特点。堆排序实现原理 构建最大堆:将待排序数组构建成一...【详细内容】
2023-10-10  Search: 排序算法  点击:(280)  评论:(0)  加入收藏
面试过程中常见的排序算法问题你见个?附常见排序算法源代码
在面试过程中,排序算法常常是一个重要的考点。排序算法的熟练掌握不仅能展现出候选人对基本数据结构的理解,也能展示出他们的算法设计和问题解决能力。下面我们将详细讨论几种...【详细内容】
2023-10-09  Search: 排序算法  点击:(87)  评论:(0)  加入收藏
目前世界上最快的排序算法-Timsort算法思想原理及C代码实现
排序算法在计算机科学中扮演着重要的角色,影响着各种应用程序的性能和效率。其中,Timsort 算法因其高效的性能和广泛的应用而备受瞩目。在本文中,我们将深入探究 Timsort 算法...【详细内容】
2023-08-05  Search: 排序算法  点击:(283)  评论:(0)  加入收藏
详解 DeepMind 排序算法
作者 | Justine Tunney译者 | 弯月责编 | 夏萌出品 | CSDN(ID:CSDNnews)近日,DeepMind 在博客发表了一篇阐述排序算法内核的论文。他们借鉴了构建 AlphaGo 积累的有关深度学习的...【详细内容】
2023-06-20  Search: 排序算法  点击:(187)  评论:(0)  加入收藏
AlphaDev将排序算法提速70%!C语言库作者一文详解DeepMind最新AI
图片来源:由无界 AI&zwnj; 生成几天前,DeepMind推出了AlphaDev,直接把排序算法提速70%。这一全新AI系统,便是基于下棋高手AlphaGo打造。而这项研究恰恰激起了前谷歌研究人员Just...【详细内容】
2023-06-20  Search: 排序算法  点击:(150)  评论:(0)  加入收藏
AI重写排序算法,速度快70%:DeepMind AlphaDev革新计算基础
计算的基础就此改变了。「通过交换和复制移动,AlphaDev 跳过了一个步骤,以一种看似错误,但实际上是捷径的方式连接项目。」这种前所未见、违反直觉的思想不禁让人回忆起 2016...【详细内容】
2023-06-08  Search: 排序算法  点击:(371)  评论:(0)  加入收藏
Go 语言实现快速排序算法
快速排序是由东尼&middot;霍尔所发明的一种排序算法,时间复杂度是 O(nlogn), 是不稳定排序算法。快速排序使用分治思想,通过一趟排序将要排序的数据分割成独立的两部分,其中一部...【详细内容】
2023-05-08  Search: 排序算法  点击:(356)  评论:(0)  加入收藏
看动图学算法:冒泡排序算法的原理和Java讲解
冒泡算法是一种简单的排序算法,它的基本思想是通过相邻元素之间的比较和交换,将大的元素慢慢地“冒泡”到数组的最后一个位置。冒泡算法在实现上非常简单,但它的时间复杂度较高...【详细内容】
2023-05-06  Search: 排序算法  点击:(365)  评论:(0)  加入收藏
常用的排序算法
排序算法是计算机科学领域中非常重要的基础算法之一,主要应用于数据处理中,将未排序的数据按照一定规则排列,以便后续的计算和数据分析。目前常用的排序算法有多种,包括冒泡排...【详细内容】
2023-04-27  Search: 排序算法  点击:(352)  评论:(0)  加入收藏
简述几种常用的排序算法
本文分享自华为云社区《深入浅出八种排序算法-云社区-华为云》,作者:嵌入式视觉 。归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,...【详细内容】
2023-03-27  Search: 排序算法  点击:(150)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(12)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(49)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(43)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(73)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(87)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(88)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(62)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(107)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(78)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(164)  评论:(0)  加入收藏
站内最新
站内热门
站内头条