首先是如何sort一个只有0和1的数组，要求inplace. follow up是告诉一个range，如何在O(N)时间内sort好
两个pointer可解
package Sorting;
import java.util.*; public class InplaceSorting {
public void sorting(int[] arr) {
if (arr==null || arr.length==0) return;
int l=0, r=arr.length-1;
while (l < r) {
while (l<r && arr[l]==0) {
l++;
}
while (l<r && arr[r]==1) {
r--;
}
if (l == r) return;
swap(arr, l, r);
}
} public void swap(int[] arr, int l, int r) {
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
} /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
InplaceSorting sol = new InplaceSorting();
int[] arr = new int[]{0,1,1,0,1,0,0,1};
sol.sorting(arr);
System.out.println(Arrays.toString(arr));
} }
BucketSort可解
Best case performance: O(n + k), where k is the size of buckets or the range between min and max in original array
Worst case performance: O(n^2)
Aver case performance: O(n + k)
Worst case space: O(n*k)
BucketSort works as follows:
1. set up an array of initially empty buckets(should know the range)
2. Go over the original array, put each object in its bucket
3. Sort each non-empty bucket.
4. visit the buckets in order and put all elements back into the original array.
package Sorting;
import java.util.Arrays;
public class Solution {
public void bucketSort(int[] arr, int min, int max) {
int[] bucket = new int[max-min+1];
for (int elem : arr) {
bucket[elem-min]++;
}
int cur = 0;
for (int i=0; i<bucket.length; i++) {
while (bucket[i] > 0) {
arr[cur++] = i+min;
bucket[i]--;
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
int[] arr = new int[]{5,6,9,10,4,11,5,7,6,11};
sol.bucketSort(arr, 4, 11);
System.out.println(Arrays.toString(arr));
}
}