public class CombineQuickSortInsertionSort {
private long[] data;
private int len;
public CombineQuickSortInsertionSort(int max) {
data = new long[max];
len = 0;
}
public void insert(long value) {
data[len] = value;
len++;
}
public void display() {
System.out.print("Data:");
for (int j = 0; j < len; j++)
System.out.print(data[j] + " ");
System.out.println("");
}
public void quickSort() {
recQuickSort(0, len - 1);
}
public void recQuickSort(int left, int right) {
int size = right - left + 1;
if (size < 10) // insertion sort if small
insertionSort(left, right);
else // quicksort if large
{
long median = medianOf3(left, right);
int partition = partitionIt(left, right, median);
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
public long medianOf3(int left, int right) {
int center = (left + right) / 2;
// order left & center
if (data[left] > data[center])
swap(left, center);
// order left & right
if (data[left] > data[right])
swap(left, right);
// order center & right
if (data[center] > data[right])
swap(center, right);
swap(center, right - 1);
return data[right - 1];
}
public void swap(int d1, int d2) {
long temp = data[d1];
data[d1] = data[d2];
data[d2] = temp;
}
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left; // right of first elem
int rightPtr = right - 1; // left of pivot
while (true) {
//find bigger
while (data[++leftPtr] < pivot)
;
//find smaller
while (data[--rightPtr] > pivot)
;
if (leftPtr >= rightPtr) // if pointers cross, partition done
break;
else
swap(leftPtr, rightPtr);
}
swap(leftPtr, right - 1); // restore pivot
return leftPtr; // return pivot location
}
public void insertionSort(int left, int right) {
int in, out;
// sorted on left of out
for (out = left + 1; out <= right; out++) {
long temp = data[out]; // remove marked item
in = out; // start shifts at out
// until one is smaller,
while (in > left && data[in - 1] >= temp) {
data[in] = data[in - 1]; // shift item to right
--in; // go left one position
}
data[in] = temp; // insert marked item
}
}
public static void main(String[] args) {
int maxSize = 16;
CombineQuickSortInsertionSort arr = new CombineQuickSortInsertionSort(maxSize);
for (int j = 0; j < maxSize; j++)
{
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
arr.display();
arr.quickSort();
arr.display();
}
}
http://hi.baidu.com/%D0%C7%C7%E9%C0%E1/blog/item/8b5f54b3d683eaa1d9335ad8.html
先留着,晚上在看 附带的是我改写的排序算法
分享到:
相关推荐
冒泡、快排、插入、合并、选择排序算法集锦
实验进行的是对快排使用插入排序进行优化,并对快排产生的不同的区间内元素个数值进行测试并计算运行时间,进行比较。代码已经进过测试可以使用
数据结构——快排和直接插入算法的性能比较,实现了快排和插入算法的性能比较。
排序算法_插入排序,快排,归并排序【数据结构和算法入门3】
快速排序用的主要是partition函数,在此程序里,快速排序改进,在调用partition将数组进行分组的时候,当子数组个数小于k时,不继续做快速排序...将返回的基本有序的数组进行插入排序,这样大大提高了快速排序的效率!
插入排序,希尔排序,快速排序的源代码,运用递归进行,并在vs2010环境下测试通过
数据结构---直接插入排序/快速排序/选择排序/冒泡排序(详细实现算法和性能比较)
快速排序(包含) 插入排序(包含) 随机版本的快速排序 快速插入排序:先进行快速排序,到基本有序后,用插入排序。 及实验报告
堆排序,快排,希尔,桶排,插入,归并,计数,选择排序,仅供参考。
排序(插入,折半插入,重排,希尔,冒泡,快排,选择,树结构选择,堆,归并,基数)代码和讲解,内容详细全面,通俗易懂,通过测试,代码可以直接使用,方便大家学习.
常用排序效率PK 冒泡 快排 选择排序 基数排序 希尔排序 折半插入排序 等
冒泡,插入,快速和选择排序C源码
用蛮力法实现选择排序,冒泡排序程序;用减治法实现插入排序;分治法应用-快排,合并排序,0-1背包问题;Prim算法求最小生成树。伪代码以及java代码实现
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
课程实验数据结果,C语言实现快排归并插入大顶堆。 内含5W-50W随机生成整数每隔5W数据量排序一次的时间记录,并对其进行了均值和方差的比较。
数据结构,选择,插入,冒泡,快排,堆排序c++实现代码
内含有快排、冒泡、插入排序、merge等多种排序法的实现,并附有测试例子,适合算法学习者
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。
选择排序、插入排序、冒泡排序、希尔排序、快速排序、箱子排序、基数排序、归并排序、堆排序 : 小总结