一、时间复杂度为O(n)的排序(计数排序,基数排序)
以下算法不是基于比较的排序,是基于桶排序思想的排序。
1.计数排序
【1】先根据元素的范围建立相应数量的桶
【2】遍历数组并依次将其放进对应的桶中
【3】依次取出桶中元素,排序完成
import java.util.*; public class CountingSort { public int[] countingSort(int[] A, int n) { if(A == null || n < 2) return A; int max = A[0]; //数组中的最大值 int min = A[0]; //数组中的最小值 int index = 0; //找出最大值和最小值 for(int value : A){ if(max < value) max = value; if(min > value) min = value; } //根据最大值和最小值建立桶 int[] bucket = new int[max - min + 1]; //遍历数组,将元素放入桶中 for(int value : A) bucket[value - min]++; //元素出桶 for(int i = 0; i < bucket.length; i++){ while(bucket[i] > 0){ A[index++] = i + min; bucket[i]--; } } return A; } }
2.基数排序
【1】建立0-9号桶,遍历所有数,根据个位进行桶的放入
【2】根据十位执行【1】,以此类推
【3】最高位执行【1】后,倒出所有元素,排序完成
注:取桶入桶按照队列方式先进先出
import java.util.*; public class RadixSort { public int[] radixSort(int[] A, int n) { // write code here if(A == null || n < 2) return A; ArrayList<Integer> negativeArray = new ArrayList<Integer>(); ArrayList<Integer> positiveArray = new ArrayList<Integer>(); int min = A[0]; int max = A[0]; int index = 0; for(int value : A){ if(value < 0) negativeArray.add(-value); else positiveArray.add(value); if(min > value) min = value; else if(max < value) max = value; } radixSortForPositive(negativeArray, -min); radixSortForPositive(positiveArray, max); for(int i = negativeArray.size()-1; i >= 0; i--){ A[index++] = -negativeArray.get(i); } for(int i =0; i < positiveArray.size(); i++){ A[index++] = positiveArray.get(i); } return A; } private void radixSortForPositive(ArrayList<Integer> positiveArray, int max){ int base = 10; ArrayList<LinkedList> bucket1 = new ArrayList<LinkedList>(); ArrayList<LinkedList> bucket2 = new ArrayList<LinkedList>(); for(int i = 0; i < 10; i++){ bucket1.add(new LinkedList()); bucket2.add(new LinkedList()); } for(int value : positiveArray){ bucket1.get(value % 10).offer(value); } while(base <= max){ for(int i = 0; i < 10; i++){ while(!bucket1.get(i).isEmpty()){ int value = (int) bucket1.get(i).poll(); bucket2.get((value/base) % 10).add(value); } } ArrayList<LinkedList> temp = bucket1; bucket1 = bucket2; bucket2 = temp; base =base*10; } int index = 0; for(int i = 0; i < 10; i++){ while(!bucket1.get(i).isEmpty()) positiveArray.set(index++, (Integer)bucket1.get(i).poll()); } } }