Groupon面经Prepare: Sort given a range && Summary: Bucket Sort - neverlandly - 博客园
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.
首先是如何sort一个只有0和1的数组,要求inplace. follow up是告诉一个range,如何在O(N)时间内sort好
5 public void sorting(int[] arr) { 6 if (arr==null || arr.length==0) return; 7 int l=0, r=arr.length-1; 8 while (l < r) { 9 while (l<r && arr[l]==0) { 10 l++; 11 } 12 while (l<r && arr[r]==1) { 13 r--; 14 } 15 if (l == r) return; 16 swap(arr, l, r); 17 } 18 }
follow up是告诉一个range,如何在O(N)时间内sort好
BucketSort可解
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.
6 public void bucketSort(int[] arr, int min, int max) { 7 int[] bucket = new int[max-min+1]; 8 for (int elem : arr) { 9 bucket[elem-min]++; 10 } 11 int cur = 0; 12 for (int i=0; i<bucket.length; i++) { 13 while (bucket[i] > 0) { 14 arr[cur++] = i+min; 15 bucket[i]--; 16 } 17 } 18 }Read full article from Groupon面经Prepare: Sort given a range && Summary: Bucket Sort - neverlandly - 博客园