数据结构与算法Java版-数组分割

问题描述

给定一个数组arr和一个数字num，将数组中小于等于nun的数都放到数组的左边，将大于num的数都放到右边

java代码实现如下：

package problem;

public class ArrayPartition {
public static void swap(int[] arr,int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void printArray(int[] arr)
{
for(int elem:arr)
{
System.out.print(elem+"\t");
}
System.out.println();
}
public static void partition(int[] arr,int num)
{
int right=-1;
for(int i=0;i<arr.length;i++)
{
if(arr[i]<=num)
{
right++;
if (right != i)
{
swap(arr,right,i);
}
}
}
}
public static void main(String[] args) {
int[] arr={1,2,9,8,5,6,7,3,4,5};
printArray(arr);
partition(arr,5);
printArray(arr);

}
}

执行结果如下：

1 2 9 8 5 6 7 3 4 5
1 2 5 3 4 5 7 8 9 6