重新排列整数数组

Question

我需要在伪代码和 java 中实现以下内容。

输入：整数数组

输出：重新排列数组使其具有以下内容：

假设原始数组中的第一个元素的值为 x
在新数组中，假设x在位置I，即data[I]=x。然后，data[j] <= x for all j x for all j>I。这意味着 x 的 "left" 的所有值都小于或等于 x，并且 "right" 的所有值都大于 x。
举例如下：假设数组中的元素初始顺序为：4,3,9,2,7,6,5。应用你的算法后，你应该得到：3,2,4,5,9,7,6。也就是说，最左边的元素 4 在结果数组中的位置使得所有小于 4 的元素（2 和 3）都在它的左边（没有特定的顺序），所有大于 4 的元素都在它的右边（在无特定顺序）。

算法没有space要求，只要求O(n)时间解决

因此，我的印象是冒泡排序在这里最好。

这种情况下的交换算法不是最佳选择，我想就可以在此处实施的其他方法获得一些反馈。

谢谢！

Answer 1

创建一个包含 space 的数组以容纳所有元素。如果 number < x 则将其放在数组的开头，如果 number > x 则将其放在数组的末尾。如果数字等于 x 则忽略它并继续前进。最后用等于 x 的值填充剩余的点。

Answer 2

java.util.array 做你所说的，但我可能遗漏了一个关键的实现细节：就是这样：

int[] numbers = {4, 9, 1, 3, 2, 8, 7, 0, 6, 5};



System.out.println(Arrays.toString(numbers));

java.util.Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers));

输出：

Before sorting: [4, 9, 1, 3, 2, 8, 7, 0, 6, 5]
After sorting: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

using integer 4 as the reference point, all the conditions you listed are met. the native sorting algorithm will be way faster. but if you need to be in control try the first answer

要得到 4 剩下的所有值，只需找到 4 的索引，假设是 i[nth] 和 return 所有索引都低于 i[nth]。要获得 4 的数字，找到 4 的索引，即 i[nth] 并获得高于 i[nth] 而 I[nth] 小于 [从零开始的数组] [=13= 的数组长度的索引]

Answer 3

考虑到 OP 的小数据集，冒泡排序会起作用，但是“......当 n 很大时，冒泡排序不是一种实用的排序算法。” （参见 bubblesort). An efficient algorithm is quicksort:

...the algorithm takes O(n log n) comparisons to sort n items.

QuickSort 的以下实现是我从 Ideone 获得的分支，并进行了修改以包含数字的 OP 数组，并且代码以数组的 left 值为中心，如下：

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{


    public static void main (String[] args) throws java.lang.Exception
    {
        int b[] = { 4, 3, 9, 2, 7, 6, 5 };
        sort( b, 0, b.length - 1 );
        System.out.println( Arrays.toString( b ) );
    }

    static void sort(int a[], int left, int right)   {  
       if (left < right){
        int i=left, j=right, tmp;    
        int v = a[left]; //pivot

        do {
            while( a[i] < v)
              i++;
            while(a[j]>v) 
              j--;

            if( i <= j){            
               tmp = a[i];
               a[i] = a[j];
               a[j] = tmp;
               i++;            
               j--;
             }
       }  while( i <=  j );        

        if( left < j )  sort( a, left, j );
        if( i < right ) sort(a,i,right);
      }
   }
}

直播code

注意：此解决方案通过让 sort() 调用自身来使用递归，具体取决于 left 和 i 的值分别与j and right.

或者，您可以按照@Maxwell 的建议使用 Java 的原生 sort()，因为它是 QuickSort 的快速实现（参见 here）。

重新排列整数数组

Rearranging an array of integers

arrays

sorting

algorithm

pseudocode