logo标签列表

排序：如何对包含三种类型数字的数组进行排序

arraysalgorithmsortinglanguage-agnosticpseudocode
14
例如：int A[] = {3,2,1,2,3,2,1,3,1,2,3}; 如何高效地对这个数组进行排序？
这是面试需要的，只需要提供一个伪代码。
面试明天，但已经参加过同样面试的某人被问到了这个问题。 - thechmodmaster
1
作弊的方法。如果你真的想了解它们，可以查找排序算法。 - Andre
3
为什么不直接计算每个元素的数量，然后根据数量生成一个新的数组呢？ - Matt Wolfe
1
我学习了所有的排序算法，但因为这个数组只包含3个选项（1、2和3），所以我认为这里有一个诀窍。 - thechmodmaster
Matt Wolf：我不能定义另一个数组。我可以交换单元格（需要尽可能少地交换）。 - thechmodmaster
显示剩余5条评论
16个回答
1
我学习了所有的排序算法，但因为这个数组只包含3个选项（1、2和3），所以我认为这里有一个诀窍。 - thechmodmaster
不需要，每个排序算法都会处理它。但是如果你知道只有三个选项（1、2、3），你可以线性地遍历数组并计算数字1的数量。如果你找到数字1，就把它放在数组的开头；如果你找到数字3，就把它放在数组的末尾；数字2应该放在位置-数字1的数量（你记得它）+1。 - Martin Ch
1
这段代码是用于C#的：
然而，您必须考虑以非特定于语言/框架的方式实现算法。建议使用Bucket set可能是最有效的选择。如果您提供有关问题的详细信息，我会尝试寻找最佳解决方案。 祝你好运...
这是一个C# .NET的代码示例。
int[] intArray = new int[9] {3,2,1,2,3,2,1,3,1 };
Array.Sort(intArray);
// write array
foreach (int i in intArray) Console.Write("{0}, ", i.ToString());
1
我会更具体地说明：你有n个桶，每个桶里面装有一枚硬币，硬币的面值可以是5、10或20。你必须在以下限制下对这些桶进行排序：
  1. 你只能使用以下两个函数： SwitchBaskets(Basket1, Basket2) - 交换两个篮子 GetCoinValue(Basket1) - 返回所选篮子中的硬币价值
  2. 你不能定义大小为n的数组
  3. 尽可能少地使用交换函数。
 - thechmodmaster
这里是我的做法。我会选择硬币，1）如果它是5-将其推到第一位，2）如果它是20-将其推到最后，3）如果是10-保持原位。4）然后查看下一个桶。 - Yusubov
0

让我们来解决这个问题，我们有一个只包含两个数字的数组。[1,2,1,2,2,2,1,1]

我们可以在一次遍历中以O(n)的时间复杂度进行排序，并进行最小交换，如果： 我们从左右两侧开始使用两个指针，直到它们相遇。 如果左边的元素比右边的元素大，则交换左边的元素和右边的元素。（升序排序）

我们可以进行另一次遍历，处理三个数字（k-1次遍历）。在第一次遍历中，我们将1移动到它们的最终位置，在第二次遍历中，我们将2移动到它们的最终位置。

def start = 0, end = array.size() - 1;

// Pass 1, move lowest order element (1) to their final position 
while (start < end) {
    // first element from left which is not 1
    for ( ; Array[start] ==  1 && start < end ; start++);
    // first element from right which IS 1
    for ( ; Array[end] != 1 && start < end ; end--);

    if (start < end) swap(start, end);
}     

// In second pass we can do 10,15

// We can extend this using recurion, for sorting domain = k, we need k-1 recurions
0
def DNF(input,length):
    high = length - 1
    p = 0
    i = 0
    while i <= high:
            if input[i] == 0:
                    input[i],input[p]=input[p],input[i]
                    p = p+1
                    i = i+1
            elif input[i] == 2:
                    input[i],input[high]=input[high],input[i]
                    high = high-1
            else:
                    i = i+1
input = [0,1,2,2,1,0]
print "input: ", input
DNF(input,len(input))
print "output: ", input
0
我会在这里使用递归方法
fun sortNums(smallestIndex,largestIndex,array,currentIndex){
if(currentIndex >= array.size)
   return
if (array[currentIndex] == 1){
You have found the smallest element, now increase the smallestIndex
//You need to put this element to left side of the array at the smallestIndex position.
//You can simply swap(smallestIndex, currentIndex)
// The catch here is you should not swap it if it's already on the left side
//recursive call
sortNums(smallestIndex,largestIndex,array,currentIndex or currentIndex+1)// Now the task of incrementing current Index in recursive call depends on the element at currentIndex. if it's 3, then you might want to let the fate of currentIndex decided by recursive function else simply increment by 1 and move further
} else if (array[currentInde]==3){
// same logic but you need to add it at end
}
}

您可以通过sortNums(smallestIndex=-1, largestIndex=array.size, array, currentIndex=0)启动递归函数

您可以在此处找到示例代码 代码链接

-1
//Bubble sort for unsorted array - algorithm
public void  bubleSort(int arr[], int n) { //n is the length of an array
    int temp;
    for(int i = 0; i <= n-2; i++){
        for(int j = 0; j <= (n-2-i); j++){
            if(arr[j] > arr[j +1]){
                temp = arr[j];
                arr[j] = arr[j +1];
                arr[j + 1] = temp;

            }
        }

    }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接