块状局部有序整体无序数据结构 - FewUniqueKeys

原创
2014/08/19 18:00
阅读数 284
package com.victor.sort.seeds;

import java.util.ArrayList;

public class FewUniqueKeys extends Seeds {

	@Override
	protected ArrayList<Integer> doGenerate(int size) {
		ArrayList<Integer> seedsList = new ArrayList<Integer>();
		int requiredSize = getSize();
		java.util.Random rd = new java.util.Random();
		int numberOfKeys = rd.nextInt(5) + 5;
		int[] values = new int[numberOfKeys];
		for(int i=0;i<numberOfKeys;i++)
		{
			values[i] = rd.nextInt(10000);
		}
		for(int i=0;i<requiredSize;i++)
		{
			int nextValue = rd.nextInt(requiredSize)%numberOfKeys;
			seedsList.add(values[nextValue]);
		}
		return seedsList;
	}

	@Override
	public String getDescriptions() {
		return "Sorting an array that consists of a small number of unique keys is common in practice. " +
				"One would like an algorithm that adapts to O(n) time when the number of unique keys is O(1). " +
				"In this example, there are 4 unique keys. The traditional 2-way partitioning quicksort exhibits " +
				"its worse-case O(n2) behavior here. For this reason, " +
				"any quicksort implementation should use 3-way partitioning, " +
				"where the array is partitioned into values less than, equal, " +
				"and greater than the pivot. Because the pivot values need not be sorted recursively, " +
				"3-way quick sort adapts to O(n) time in this case. Shell sort also adapts to few unique " +
				"keys, though I do not know its time complexity in this case.";
	}

	@Override
	public String getName() {
		return "Few Unique Keys";
	}
	
	public static void main(String[] args)
	{
		Seeds rd = new FewUniqueKeys();
		rd.setSize(100);
		rd.generate();
		rd.print();
	}

}


展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部