如何对数组进行排序
int[] A = {0,1,1,0,1,0,1,1,0}
问问题
10226 次
17 回答
10
您实际上可以通过仅遍历数组一次来对该数组进行排序。
这是我的代码片段：
int arr[] = {1,1,1,1,0, 0,1,0,1,1,1};
int arrb[] = new int[arr.length];
int zeroInsertIndex = 0;
int oneInsertIndex =arrb.length-1;
for(int i=0; i<arr.length; i++){
if(arr[i] == 1)
arrb[oneInsertIndex--] = 1;
else if (arr[i] == 0)
arrb[zeroInsertIndex++] = 0;
}
for(int i=0;i<arrb.length;i++)
System.out.print(arrb[i] + " ");
于 2016-08-04T10:33:23.220 回答
4
尽管 Arrays.sort 是一个明显、简单的 O(n log n) 解决方案，但对于这种特殊情况有一个 O(n) 解决方案：
- 计算零的个数，zeroCount。
- 用 0 填充第一个 zeroCount 元素，用 1 填充其余元素。
这只需要两次通过数组。
更一般地，任何只有少量不同值的数组都可以通过计算每个值出现的次数来排序，然后相应地填充数组。
于 2013-02-07T07:06:34.593 回答
2
使用任何排序算法来做到这一点。对于初学者使用冒泡排序（易于理解）
参考Wiki
public static void bubble_srt( int a[], int n ){
int i, j,t=0;
for(i = 0; i < n; i++){
for(j = 1; j < (n-i); j++){
if(a[j-1] > a[j]){
t = a[j-1];
a[j-1]=a[j];
a[j]=t;
}
}
}
}
正如@Pradeep
所说：您绝对可以使用 Array.sort()
于 2013-02-07T06:59:52.507 回答
2
您的数组仅包含 0 和 1，因此将数组中的所有元素相加，然后用最后的许多 '1' 重置数组，并在开头休息 '0'。时间复杂度也是 O(n)，空间恒定。所以这似乎是最好和最容易的。
public static void main(String[] args) {
int[] A = { 0, 1, 1, 0, 1, 0, 1, 1, 0 };
int sum = 0;
for (int i = 0; i < A.length; i++)
sum = sum + A[i];
Arrays.fill(A, A.length - sum, A.length, 1);
Arrays.fill(A, 0, A.length - sum, 0);
System.out.println(Arrays.toString(A));
}
试试这个我实现了上面的算法。
输出：
[0, 0, 0, 0, 1, 1, 1, 1, 1]
于 2013-02-07T07:00:09.950 回答
1
您可以使用类中Arrays.sort的方法Arrays：
int[] A = {0,1,1,0,1,0,1,1,0};
Arrays.sort(A);
System.out.println(A);
于 2013-02-07T07:00:42.243 回答
1
实际上，标准的现成排序算法通常适用于 O(n*log(n))。一旦添加了所有值（即 1 的数量），您就可以遍历数组。假设您将其放入count1. 然后再次遍历数组，将第一个count1位置设置为 1，将其余位置设置为 0。它需要 2n 步。
当然，正如其他发帖人所说：这种优化是你一旦检测到瓶颈就会做的事情，而不是在你开始时马上做的事情。
于 2013-02-07T07:05:49.553 回答
0
Arrays.sort(A,Collections.reverseOrder());
于 2013-02-07T07:03:06.413 回答
0
利用
Arrays.sort(A);
对数组进行排序的方法。
于 2013-02-07T07:04:56.747 回答
0
public class Test {
public static void main(String[] args) {
int[] arr = {0, 1, 0, 1, 0, 0, 1, 1, 1, 0};
int start = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
arr[start] = 0;
if (i != start) { // should not override same value with 1
arr[i] = 1;
}
start++;
}
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
//复杂度是O(n)
于 2021-07-07T04:00:05.623 回答
0
public static void sort(int a[]) {
int sum=0;
int b[]= new int [a.length];
for(int i=0;i<a.length;i++) {
sum=sum+a[i];
}
System.out.println(sum);
int j=b.length-1;
while(sum>0) {
b[j]=1;
sum--;
j--;
}
System.out.println(Arrays.toString(b));
}
于 2020-08-12T15:20:27.353 回答
0
Team
Please consider the below program in Swift in o(n) time complexity and constant extra space.
import UIKit
var inputArray = [1,0,1,0,0,0,0,1,1,1,1,1,1]
var leftIndex: Int = 0
var rightIndex: Int = inputArray.count-1
while leftIndex < rightIndex{
while inputArray[leftIndex] == 0 && leftIndex < rightIndex{
leftIndex = leftIndex+1
}
while inputArray[rightIndex] == 1 && rightIndex > leftIndex {
rightIndex = rightIndex-1
}
if leftIndex < rightIndex{
inputArray[leftIndex] = 0
inputArray[rightIndex] = 1
leftIndex = leftIndex+1
rightIndex = rightIndex-1
}
}
print(inputArray)
于 2019-01-27T07:39:46.217 回答
0
使用以下代码对 0 和 1 数组进行排序：
public static int[] sortArray(int[] array){
int first = 0;
int last = array.length-1;
while(first<last){
if(array[first]==0){
first++;
}else if(array[last] == 0){
int temp = array[last];
array[last] = array[first];
array[first] = temp;
first++;
}else{
last--;
}
}
return array;
}
于 2020-06-19T11:02:09.227 回答
0
你也可以这样试试
public static void main(String[] args) {
int inputArray[] = { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0 };
formatInputArray(inputArray);
}
private static void formatInputArray(int[] inputArray) {
int count = 0;
for (int i = 0; i < inputArray.length; i++) {
if (inputArray[i] == 0) {
count++;
}
}
// System.out.println(count);
for (int i = 0; i < inputArray.length; i++) {
if (i < count) {
inputArray[i] = 0;
}
else {
inputArray[i] = 1;
}
}
for (int i = 0; i < inputArray.length; i++) {
System.out.print(inputArray[i] + " , ");
}
}
于 2017-08-16T08:50:12.163 回答
0
以下代码将对您的数组进行排序。请注意，它是这样做的——所以它会修改内存中的对象，而不是返回一个新对象。
在 Python 中
arr=[0,1,0,0,1,1,1,0,1,1,0]
arr.sort()
print(arr)
在 Java 中
public class test{
public static void main(String[] args){
int[] arr= {0,1,0,0,1,1,1,0,1,1,0};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
}}
于 2021-06-15T08:36:50.293 回答
0
var binaryArr = [1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,0,0,0];
//i - starting index
//j - ending index
function binarySort(arr){
var i=0,j=arr.length-1;
for(;i!=j;){
if(arr[i] == 1){
if(arr[j] == 0){
arr[i] = 0;
arr[j] = 1;
j--;
i++;
} else {
j--;
}
}else{
i++;
}
}
}
binarySort(binaryArr);
于 2018-10-23T13:13:56.897 回答
0
仅包含 0,1 和 2 的排序数组
import java.util.*;
public class HelloWorld {
static void sort012(int []a, int length) {
int start = 0;
int mid = 0;
int end = length - 1;
int temp;
while(mid<=end) {
switch(a[mid]) {
case 0:
temp = a[start];
a[start] = a[mid];
a[mid] = temp;
start++;
mid++;
break;
case 1:
mid++;
break;
case 2:
temp = a[end];
a[end] = a[mid];
a[mid] = temp;
end--;
break;
}
}
}
public static void main(String []args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for (int i =0;i<n; i++)
a[i] = sc.nextInt();
HelloWorld.sort012(a, n);
// Print the sorted Array
for (int i =0;i<n; i++)
System.out.println(a[i]);
}
}
于 2018-07-24T13:43:03.960 回答
-1
int[] a = {0,1,1,0,1,0,1,1,0}
在这里，我们使用 i 进行迭代，其中 i 从 1 开始。因此我们可以将之前的索引值与 i 的当前值进行比较。使用交换技术对数组进行排序。
注意：我们也可以使用 Sort/2 指针技术。
public int[] sort(int[] a){
int temp=0;
for(int i=1;i<a.length;i++){
if( a[i-1] > a[i]){
temp = a[i-1];
a[i-1] = a[i];
a[i] = temp;
}
}
return a[i];
}
时间复杂度：O(n)
于 2021-05-23T13:38:00.573 回答