排序

  Java   6分钟   1070浏览   0评论

面经

用java写一个冒泡排序？

考察点：冒泡排序

public static void main(String[] args) {
    int[] result = {2,4,1,3,6,5};
    int temp;
    System.out.println("----冒泡排序前顺序----");
    for (int i : result) {
        System.out.print(i);
    }
    for(int i=0;i<result.length-1;i++){
        for(int j = 0;j<result.length-1-i;j++){
            if(result[j+1]<result[j]){
                //后一个比前一个小
                temp = result[j];
                result[j] = result[j+1];
                result[j+1] = temp;
            }
        }
    }
    System.out.println();
    System.out.println("----冒泡排序后结果----");
    for (int i : result) {
        System.out.print(i);
    }
}

介绍一下，排序都有哪几种方法？请列举出来。

考察点：排序

参考回答：

排序的方法有：

插入排序（简单插入排序、希尔排序）

交换排序（冒泡排序、快速排序）

选择排序（简单选择排序、堆排序）

归并排序

分配排序（箱排序、基数排序）

绍一下，归并排序的原理是什么？

考察点：归并排序

参考回答：

（1）归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

（2）首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

（3）解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

介绍一下，堆排序的原理是什么？

考察点：堆排序

参考回答：

堆排序分大顶堆和小顶堆，这里以大顶堆为例讲解。

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

（1）最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。

（2）创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆。

（3）堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

img

谈一谈，如何得到一个数据流中的中位数？

考察点：排序

参考回答：

数据是从一个数据流中读出来的，数据的数目随着时间的变化而增加。如果用一个数据容器来保存从流中读出来的数据，当有新的数据流中读出来时，这些数据就插入到数据容器中。

数组是最简单的容器。如果数组没有排序，可以用 Partition 函数找出数组中的中位数。在没有排序的数组中插入一个数字和找出中位数的时间复杂度是 O(1)和 O(n)。

我们还可以往数组里插入新数据时让数组保持排序，这是由于可能要移动 O(n)个数，因此需要 O(n)时间才能完成插入操作。在已经排好序的数组中找出中位数是一个简单的操作，只需要 O(1)时间即可完成。

排序的链表时另外一个选择。我们需要 O(n)时间才能在链表中找到合适的位置插入新的数据。如果定义两个指针指向链表的中间结点（如果链表的结点数目是奇数，那么这两个指针指向同一个结点），那么可以在 O（1）时间得出中位数。此时时间效率与及基于排序的数组的时间效率一样。

如果能够保证数据容器左边的数据都小于右边的数据，这样即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。如何快速从一个容器中找出最大数？用最大堆实现这个数据容器，因为位于堆顶的就是最大的数据。同样，也可以快速从最小堆中找出最小数。

因此可以用如下思路来解决这个问题：用一个最大堆实现左边的数据容器，用最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是 O(logn)。由于只需 O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间效率是 O(1)。

你知道哪些排序算法，这些算法的时间复杂度分别是多少，解释一下快排？

考察点：快排

参考回答：

img

快排：快速排序有两个方向，左边的i下标一直往右走（当条件a[i] <= a[center_index]时），其中center_index是中枢元素的数组下标，一般取为数组第0个元素。

而右边的j下标一直往左走（当a[j] > a[center_index]时）。

如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2023/03/01 18:08:45

如果你觉得文章对你有帮助，那就请作者喝杯咖啡吧☕
微信
支付宝
😀
😃
😄
😁
😆
😅
🤣
😂
🙂
🙃
😉
😊
😇
🥰
😍
🤩
😘
😗
☺️
😚
😙
🥲
😋
😛
😜
🤪
😝
🤑
🤗
🤭
🫢
🫣
🤫
🤔
🤨
😐
😑
😶
😏
😒
🙄
😬
😮‍💨
🤤
😪
😴
😷
🤒
🤕
🤢
🤮
🤧
🥵
🥶
🥴
😵
😵‍💫
🤯
🥳
🥺
😠
😡
🤬
🤯
😈
👿
💀
☠️
💩
👻
👽
👾
🤖
😺
😸
😹
😻
😼
😽
🙀
😿
😾
👋
🤚
🖐️
✋️
🖖
🫱
🫲
🫳
🫴
🫷
🫸
👌
🤌
🤏
✌️
🤞
🫰
🤟
🤘
🤙
👈️
👉️
👆️
🖕
👇️
☝️
🫵
👍️
👎️
✊️
👊
🤛
🤜
👏
🙌
👐
🤲
🤝
🙏
✍️
💅
🤳
💪
🦾
🦿
🦵
🦶
👂
🦻
👃
👶
👧
🧒
👦
👩
🧑
👨
👩‍🦱
👨‍🦱
👩‍🦰
👨‍🦰
👱‍♀️
👱‍♂️
👩‍🦳
👨‍🦳
👩‍🦲
👨‍🦲
🧔‍♀️
🧔‍♂️
👵
🧓
👴
👲
👳‍♀️
👳‍♂️
🧕
👮‍♀️
👮‍♂️
👷‍♀️
👷‍♂️
💂‍♀️
💂‍♂️
🕵️‍♀️
🕵️‍♂️
👩‍⚕️
👨‍⚕️
👩‍🌾
👨‍🌾
👩‍🍳
👨‍🍳
🐶
🐱
🐭
🐹
🐰
🦊
🐻
🐼
🐨
🐯
🦁
🐮
🐷
🐸
🐵
🐔
🐧
🐦
🦅
🦉
🐴
🦄
🐝
🪲
🐞
🦋
🐢
🐍
🦖
🦕
🐬
🦭
🐳
🐋
🦈
🐙
🦑
🦀
🦞
🦐
🐚
🐌
🦋
🐛
🦟
🪰
🪱
🦗
🕷️
🕸️
🦂
🐢
🐍
🦎
🦖
🦕
🐊
🐢
🐉
🦕
🦖
🐘
🦏
🦛
🐪
🐫
🦒
🦘
🦬
🐃
🐂
🐄
🐎
🐖
🐏
🐑
🐐
🦌
🐕
🐩
🦮
🐕‍🦺
🐈
🐈‍⬛
🐓
🦃
🦚
🦜
🦢
🦩
🕊️
🐇
🦝
🦨
🦡
🦫
🦦
🦥
🐁
🐀
🐿️
🦔
🌵
🎄
🌲
🌳
🌴
🌱
🌿
☘️
🍀
🎍
🎋
🍃
🍂
🍁
🍄
🌾
💐
🌷
🌹
🥀
🌺
🌸
🌼
🌻
🌞
🌝
🌛
🌜
🌚
🌕
🌖
🌗
🌘
🌑
🌒
🌓
🌔
🌙
🌎
🌍
🌏
🪐
💫
⭐
🌟
✨
⚡
🔥
💥
☄️
☀️
🌤️
⛅
🌥️
🌦️
🌧️
⛈️
🌩️
🌨️
❄️
☃️
⛄
🌬️
💨
💧
💦
☔
🌊
🍇
🍈
🍉
🍊
🍋
🍌
🍍
🥭
🍎
🍏
🍐
🍑
🍒
🍓
🥝
🍅
🥥
🥑
🍆
🥔
🥕
🌽
🌶️
🥒
🥬
🥦
🧄
🧅
🍄
🥜
🍞
🥐
🥖
🥨
🥯
🥞
🧇
🧀
🍖
🍗
🥩
🥓
🍔
🍟
🍕
🌭
🥪
🌮
🌯
🥙
🧆
🥚
🍳
🥘
🍲
🥣
🥗
🍿
🧈
🧂
🥫
🍱
🍘
🍙
🍚
🍛
🍜
🍝
🍠
🍢
🍣
🍤
🍥
🥮
🍡
🥟
🥠
🥡
🦪
🍦
🍧
🍨
🍩
🍪
🎂
🍰
🧁
🥧
🍫
🍬
🍭
🍮
🍯
🍼
🥛
☕
🍵
🍶
🍾
🍷
🍸
🍹
🍺
🍻
🥂
🥃
🥤
🧃
🧉
🧊
🗺️
🏔️
⛰️
🌋
🏕️
🏖️
🏜️
🏝️
🏞️
🏟️
🏛️
🏗️
🏘️
🏙️
🏚️
🏠
🏡
🏢
🏣
🏤
🏥
🏦
🏨
🏩
🏪
🏫
🏬
🏭
🏯
🏰
💒
🗼
🗽
⛪
🕌
🛕
🕍
⛩️
🕋
⛲
⛺
🌁
🌃
🏙️
🌄
🌅
🌆
🌇
🌉
🎠
🎡
🎢
💈
🎪
🚂
🚃
🚄
🚅
🚆
🚇
🚈
🚉
🚊
🚝
🚞
🚋
🚌
🚍
🚎
🚐
🚑
🚒
🚓
🚔
🚕
🚖
🚗
🚘
🚙
🚚
🚛
🚜
🏎️
🏍️
🛵
🦽
🦼
🛺
🚲
🛴
🛹
🚏
🛣️
🛤️
🛢️
⛽
🚨
🚥
🚦
🚧
⚓
⛵
🛶
🚤
🛳️
⛴️
🛥️
🚢
✈️
🛩️
🛫
🛬
🪂
💺
🚁
🚟
🚠
🚡
🛰️
🚀
🛸
🧳
⌚
📱
💻
⌨️
🖥️
🖨️
🖱️
🖲️
💽
💾
📀
📼
🔍
🔎
💡
🔦
🏮
📔
📕
📖
📗
📘
📙
📚
📓
📒
📃
📜
📄
📰
🗞️
📑
🔖
🏷️
💰
💴
💵
💶
💷
💸
💳
🧾
✉️
📧
📨
📩
📤
📥
📦
📫
📪
📬
📭
📮
🗳️
✏️
✒️
🖋️
🖊️
🖌️
🖍️
📝
📁
📂
🗂️
📅
📆
🗒️
🗓️
📇
📈
📉
📊
📋
📌
📍
📎
🖇️
📏
📐
✂️
🗃️
🗄️
🗑️
🔒
🔓
🔏
🔐
🔑
🗝️
🔨
🪓
⛏️
⚒️
🛠️
🗡️
⚔️
🔫
🏹
🛡️
🔧
🔩
⚙️
🗜️
⚗️
🧪
🧫
🧬
🔬
🔭
📡
💉
🩸
💊
🩹
🩺
🚪
🛏️
🛋️
🪑
🚽
🚿
🛁
🧴
🧷
🧹
🧺
🧻
🧼
🧽
🧯
🛒
🚬
⚰️
⚱️
🗿
🏧
🚮
🚰
♿
🚹
🚺
🚻
🚼
🚾
🛂
🛃
🛄
🛅
⚠️
🚸
⛔
🚫
🚳
🚭
🚯
🚱
🚷
📵
🔞
☢️
☣️
❤️
🧡
💛
💚
💙
💜
🖤
💔
❣️
💕
💞
💓
💗
💖
💘
💝
💟
☮️
✝️
☪️
🕉️
☸️
✡️
🔯
🕎
☯️
☦️
🛐
⛎
♈
♉
♊
♋
♌
♍
♎
♏
♐
♑
♒
♓
🆔
⚛️
🉑
☢️
☣️
📴
📳
🈶
🈚
🈸
🈺
🈷️
✴️
🆚
💮
🉐
㊙️
㊗️
🈴
🈵
🈹
🈲
🅰️
🅱️
🆎
🆑
🅾️
🆘
❌
⭕
🛑
💢
💯
💠
♨️
🚷
🚯
🚳
🚱
🔞
📵
🚭
❗
❕
❓
❔
‼️
⁉️
🔅
🔆
🔱
⚜️
〽️
⚠️
🚸
🔰
♻️
✅
🈯
💹
❇️
✳️
❎
🌐
💠
Ⓜ️
🌀
💤
🏧
🚾
♿
🅿️
🈳
🈂️
🛂
🛃
🛄
🛅
  0 条评论