在没有额外空间的情况下对队列进行排序


难度级别 易得奖学金
经常问 贝尔扎巴尔 GE医疗集团 马恒达康维瓦 空气质量 Nvidia公司 高通公司 ServiceNow
队列 排序

在排序没有额外空间问题的队列时,我们给出了一个 队列,请使用标准队列操作对其进行排序,而无需额外的空间。

例子

输入
队列= 10-> 7-> 2-> 8-> 6
输出
队列= 2-> 6-> 7-> 8-> 10

输入
队列= 56-> 66-> 1-> 18-> 23-> 39
输出
队列= 1-> 18-> 23-> 39-> 56-> 66

输入
队列= 5-> 4-> 3-> 2-> 1
输出
队列= 1-> 2-> 3-> 4-> 5

无多余空间的队列排序算法

考虑队列由两部分组成,一个部分已排序,另一部分未排序。 最初,所有元素都存在于未排序的部分中。
在每一步中,从未排序的队列中查找最小元素的索引,然后将其移至队列的末尾,即已排序的部分。
重复此步骤,直到所有元素都没有出现在已排序的队列中。

  1. 对i = 0到n(不包括在内)运行一个循环,其中n是队列的大小。
  2. 在每次迭代时,将minIndex初始化为-1,将minValue初始化为-infinity。
  3. 使用变量j运行另一个循环,该循环从未排序的队列中查找最小元素的索引。 对于i的特定值,存在从索引0到索引(n – i)的未排序队列。 在每次迭代中,如果当前元素小于minValue,则将minValue更新为当前元素,并将minIndex更新为j。
  4. 遍历队列并删除元素minIndex处的元素,然后将其推入队列的末尾。
  5. 队列被排序,打印其元素。

无需额外空间即可对队列进行排序的说明

考虑一个例子,
队列= 10-> 7-> 2-> 8-> 6

最初,所有元素都存在于未排序的部分中,也就是说,

在没有额外空间的情况下对队列进行排序

在每一步中,找到未排序部分中最小元素的索引,并将其移至队列的末尾,即已排序部分。

在没有额外空间的情况下对队列进行排序

所有元素都存在于已排序的部分中,因此我们停止。

JAVA代码,用于在没有额外空间的情况下对队列进行排序

import java.util.LinkedList;
import java.util.Queue;

public class SortingAQueueWithoutExtraSpace {
    private static void sortQueue(Queue<Integer> queue) {
        int n = queue.size();

        for (int i = 0; i < n; i++) {
            // Find the index of smallest element from the unsorted queue
            int minIndex = -1;
            int minValue = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                int currValue = queue.poll();
                // Find the minimum value index only from unsorted queue
                if (currValue < minValue && j < (n - i)) {
                    minValue = currValue;
                    minIndex = j;
                }
                queue.add(currValue);
            }

            // Remove min value from queue
            for (int j = 0; j < n; j++) {
                int currValue = queue.poll();
                if (j != minIndex) {
                    queue.add(currValue);
                }
            }
            // Add min value to the end of the queue
            queue.add(minValue);
        }

        // Print the sorted queue
        for (Integer i : queue) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        q1.add(10);
        q1.add(7);
        q1.add(2);
        q1.add(8);
        q1.add(6);
        sortQueue(q1);

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(56);
        q2.add(66);
        q2.add(1);
        q2.add(18);
        q2.add(23);
        q2.add(39);
        sortQueue(q2);
    }
}
2 6 7 8 10 
1 18 23 39 56 66

无需额外空间即可对队列进行排序的C ++代码

#include<bits/stdc++.h> 
using namespace std;

void sortQueue(queue<int> &queue) {
    int n = queue.size();
    
    for (int i = 0; i < n; i++) {
        // Find the index of smallest element from the unsorted queue
        int minIndex = -1;
        int minValue = INT_MAX;
        for (int j = 0; j < n; j++) {
            int currValue = queue.front();
            queue.pop();
            // Find the minimum value index only from unsorted queue
            if (currValue < minValue && j < (n - i)) {
                minValue = currValue;
                minIndex = j;
            }
            queue.push(currValue);
        }Nvidia
Belzabar
        
        // Remove min value from queue
        for (int j = 0; j < n; j++) {
            int currValue = queue.front();
            queue.pop();
            if (j != minIndex) {
                queue.push(currValue);
            }
        }
        // Add min value to the end of the queue
        queue.push(minValue);
    }
    
    // Print the sorted queue
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        cout<<curr<<" ";
        queue.push(curr);
    }
    cout<<endl;
}

int main() {
    // Example 1
    queue<int> q1;
    q1.push(10);
    q1.push(7);
    q1.push(2);
    q1.push(8);
    q1.push(6);
    sortQueue(q1);

    // Example 2
    queue<int> q2;
    q2.push(56);
    q2.push(66);
    q2.push(1);
    q2.push(18);
    q2.push(23);
    q2.push(39);
    sortQueue(q2);
}
2 6 7 8 10 
1 18 23 39 56 66

复杂度分析

时间复杂度= 2)
空间复杂度= O(1)
其中n是队列中元素的数量。

參考資料