//SortUtil
package sort;
import sort.BubbleSort;
import sort.HeapSort;
import sort.ImprovedMergeSort;
import sort.ImprovedQuickSort;
import sort.InsertSort;
import sort.MergeSort;
import sort.QuickSort;
import sort.SelectionSort;
import sort.ShellSort;
/**
* aa
*
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class SortUtil
{
/**
* aa
*/
public static final int INSERT = 1;
/**
* aa
*/
public static final int BUBBLE = 2;
/**
* aa
*/
public static final int SELECTION = 3;
/**
* aa
*/
public static final int SHELL = 4;
/**
* aa
*/
public static final int QUICK = 5;
/**
* aa
*/
public static final int IMPROVED_QUICK = 6;
/**
* aa
*/
public static final int MERGE = 7;
/**
* aa
*/
public static final int IMPROVED_MERGE = 8;
/**
* aa
*/
public static final int HEAP = 9;
/**
* aa
*/
private static String[] name =
{"insert", "bubble", "selection", "shell", "quick", "improved_quick", "merge", "improved_merge", "heap"};
/**
* aa
*/
private static Sort[] impl =
new Sort[] {new InsertSort(), new BubbleSort(), new SelectionSort(), new ShellSort(), new QuickSort(),
new ImprovedQuickSort(), new MergeSort(), new ImprovedMergeSort(), new HeapSort()};
/**
* aa
*
* @param data int[]
*/
public static void sort(int[] data)
{
sort(data, IMPROVED_QUICK);
}
/**
* aa
*
* @param algorithm int
* @return String
*/
public static String toString(int algorithm)
{
return name[algorithm - 1];
}
/**
* aa
*
* @param data int[]
* @param algorithm int
*/
public static void sort(int[] data, int algorithm)
{
impl[algorithm - 1].sort(data);
}
/**
* aa
*/
public static interface Sort
{
/**
* aa
*
* @param data int[]
*/
public void sort(int[] data);
}
/**
* aa
*
* @param data int[]
* @param i int
* @param j int
*/
public static void swap(int[] data, int i, int j)
{
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
//Sort
package sort;
public class Sort
{
/**
* 交换i、j位置的元素
*
* @param a int[]
* @param i int
* @param j int
*/
public void swap(int a[], int i, int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
/**
* 返回起始位置元素排序后的位置
*
* @param a int[]
* @param low int 起始位置
* @param high int 结束位置
* @return 排序后的位置
*/
public int partition(int a[], int low, int high)
{
int pivot, p_pos, i;
p_pos = low;
pivot = a[p_pos];
for (i = low + 1; i <= high; i++)
{
if (a[i] > pivot)
{
p_pos++;
swap(a, p_pos, i);
}
}
swap(a, low, p_pos);
return p_pos;
}
/**
* 递归实现快速排序
*
* @param a int[]待排序数组
* @param low int
* @param high int
*/
public void quicksort(int a[], int low, int high)
{
int pivot;
if (low < high)
{
pivot = partition(a, low, high);
quicksort(a, low, pivot - 1);
quicksort(a, pivot + 1, high);
}
}
/**
* 主方法
*
* @param args String[]
*/
public static void main(String args[])
{
int vec[] = new int[] {37, 47, 23, -5, 19, 56};
int temp;
/** 选择排序法(Selection Sort) */
long begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++)
{
for (int i = 0; i < vec.length; i++)
{
for (int j = i; j < vec.length; j++)
{
if (vec[j] > vec[i])
{
temp = vec[i];
vec[i] = vec[j];
vec[j] = temp;
}
}
}
}
long end = System.currentTimeMillis();
System.out.println("选择法用时为：" + (end - begin));
/** 打印排序好的结果 */
for (int i = 0; i < vec.length; i++)
{
System.out.println(vec[i]);
}
/** 冒泡排序法(Bubble Sort) */
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++)
{
for (int i = 0; i < vec.length; i++)
{
for (int j = i; j < vec.length - 1; j++)
{
if (vec[j + 1] > vec[j])
{
temp = vec[j + 1];
vec[j + 1] = vec[j];
vec[j] = temp;
}
}
}
}
end = System.currentTimeMillis();
System.out.println("冒泡法用时为：" + (end - begin));
/** 打印排序好的结果 */
for (int i = 0; i < vec.length; i++)
{
System.out.println(vec[i]);
}
/** 插入排序法(Insertion Sort) */
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++)
{
for (int i = 1; i < vec.length; i++)
{
int j = i;
while (vec[j - 1] < vec[i])
{
vec[j] = vec[j - 1];//元素后移
j--;
if (j <= 0)
{
break;
}
}
vec[j] = vec[i];//将i处元素插入
}
}
end = System.currentTimeMillis();
System.out.println("插入法用时为：" + (end - begin));
/** 打印排序好的结果 */
for (int i = 0; i < vec.length; i++)
{
System.out.println(vec[i]);
}
/** 快速排序法(Quick Sort) */
Sort s = new Sort();
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++)
{
s.quicksort(vec, 0, 5);
}
end = System.currentTimeMillis();
System.out.println("快速法用时为：" + (end - begin));
/** 打印排序好的结果 */
for (int i = 0; i < vec.length; i++)
{
System.out.println(vec[i]);
}
}
}
//BubbleSort
package sort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class BubbleSort implements SortUtil.Sort
{
/**
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data)
{
for (int i = 0; i < data.length; i++)
{
for (int j = data.length - 1; j > i; j--)
{
if (data[j] < data[j - 1])
{
SortUtil.swap(data, j, j - 1);
}
}
}
}
public static void main(String[] args)
{
int[] data = {12, 32, 45, 5, 6, 8, 23, 18, 10};
System.out.println(System.currentTimeMillis());
new BubbleSort().sort(data);
System.out.println(System.currentTimeMillis());
for (int i = 0; i < data.length; i++)
{
System.out.print(data[i] + " ");
}
}
}
//HeapSort
package sort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class HeapSort implements SortUtil.Sort
{
/*
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data)
{
MaxHeap h = new MaxHeap();
h.init(data);
for (int i = 0; i < data.length; i++)
h.remove();
System.arraycopy(h.queue, 1, data, 0, data.length);
}
private static class MaxHeap
{
void init(int[] data)
{
this.queue = new int[data.length + 1];
for (int i = 0; i < data.length; i++)
{
queue[++size] = data[i];
fixUp(size);
}
}
private int size = 0;
private int[] queue;
public int get()
{
return queue[1];
}
public void remove()
{
SortUtil.swap(queue, 1, size--);
fixDown(1);
}
// fixdown
private void fixDown(int k)
{
int j;
while ((j = k << 1) <= size)
{
if (j < size && queue[j] < queue[j + 1])
j++;
if (queue[k] > queue[j]) // 不用交换
break;
SortUtil.swap(queue, j, k);
k = j;
}
}
private void fixUp(int k)
{
while (k > 1)
{
int j = k >> 1;
if (queue[j] > queue[k])
break;
SortUtil.swap(queue, j, k);
k = j;
}
}
}
}
//ImprovedMergeSort
package sort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ImprovedMergeSort implements SortUtil.Sort {
private static final int THRESHOLD = 10;
/*
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] temp=new int[data.length];
mergeSort(data,temp,0,data.length-1);
}
private void mergeSort(int[] data, int[] temp, int l, int r) {
int i, j, k;
int mid = (l + r) / 2;
if (l == r)
return;
if ((mid - l) >= THRESHOLD)
mergeSort(data, temp, l, mid);
else
insertSort(data, l, mid - l + 1);
if ((r - mid) > THRESHOLD)
mergeSort(data, temp, mid + 1, r);
else
insertSort(data, mid + 1, r - mid);
for (i = l; i <= mid; i++) {
temp[i] = data[i];
}
for (j = 1; j <= r - mid; j++) {
temp[r - j + 1] = data[j + mid];
}
int a = temp[l];
int b = temp[r];
for (i = l, j = r, k = l; k <= r; k++) {
if (a < b) {
data[k] = temp[i++];
a = temp[i];
} else {
data[k] = temp[j--];
b = temp[j];
}
}
}
/**
* @param data
* @param l
* @param i
*/
private void insertSort(int[] data, int start, int len) {
for(int i=start+1;i<start+len;i++){
for(int j=i;(j>start) && data[j]<data[j-1];j--){
SortUtil.swap(data,j,j-1);
}
}
}
}
//ImprovedQuickSort
package sort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ImprovedQuickSort implements SortUtil.Sort {
private static int MAX_STACK_SIZE=4096;
private static int THRESHOLD=10;
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] stack=new int[MAX_STACK_SIZE];
int top=-1;
int pivot;
int pivotIndex,l,r;
stack[++top]=0;
stack[++top]=data.length-1;
while(top>0){
int j=stack[top--];
int i=stack[top--];
pivotIndex=(i+j)/2;
pivot=data[pivotIndex];
SortUtil.swap(data,pivotIndex,j);
//partition
l=i-1;
r=j;
do{
while(data[++l]<pivot);
while((r!=0)&&(data[--r]>pivot));
SortUtil.swap(data,l,r);
}
while(l<r);
SortUtil.swap(data,l,r);
SortUtil.swap(data,l,j);
if((l-i)>THRESHOLD){
stack[++top]=i;
stack[++top]=l-1;
}
if((j-l)>THRESHOLD){
stack[++top]=l+1;
stack[++top]=j;
}
}
//new InsertSort().sort(data);
insertSort(data);
}
/**
* @param data
*/
private void insertSort(int[] data) {
for(int i=1;i<data.length;i++){
for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
SortUtil.swap(data,j,j-1);
}
}
}
}
//InsertSort
package sort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class InsertSort implements SortUtil.Sort
{
/*
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data)
{
for (int i = 1; i < data.length; i++)
{
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--)
{
SortUtil.swap(data, j, j - 1);
}
}
}
}
//MergeSort
package sort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class MergeSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] temp=new int[data.length];
mergeSort(data,temp,0,data.length-1);
}
private void mergeSort(int[] data,int[] temp,int l,int r){
int mid=(l+r)/2;
if(l==r) return ;
mergeSort(data,temp,l,mid);
mergeSort(data,temp,mid+1,r);
for(int i=l;i<=r;i++){
temp[i]=data[i];
}
int i1=l;
int i2=mid+1;
for(int cur=l;cur<=r;cur++){
if(i1==mid+1)
data[cur]=temp[i2++];
else if(i2>r)
data[cur]=temp[i1++];
else if(temp[i1]<temp[i2])
data[cur]=temp[i1++];
else
data[cur]=temp[i2++];
}
}
}
//QuickSort
package sort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class QuickSort implements SortUtil.Sort
{
/**
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data)
{
quickSort(data, 0, data.length - 1);
}
private void quickSort(int[] data, int i, int j)
{
int pivotIndex = (i + j) / 2;
/** swap */
SortUtil.swap(data, pivotIndex, j);
int k = partition(data, i - 1, j, data[j]);
SortUtil.swap(data, k, j);
if ((k - i) > 1)
quickSort(data, i, k - 1);
if ((j - k) > 1)
quickSort(data, k + 1, j);
}
/**
*
* @param data
* @param l
* @param r
* @param pivot
* @return
*/
private int partition(int[] data, int l, int r, int pivot)
{
do
{
while (data[++l] < pivot)
;
while ((r != 0) && data[--r] > pivot)
;
SortUtil.swap(data, l, r);
} while (l < r);
SortUtil.swap(data, l, r);
return l;
}
}
//SelectionSort
package sort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class SelectionSort implements SortUtil.Sort
{
/**
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data)
{
for (int i = 0; i < data.length; i++)
{
int lowIndex = i;
for (int j = data.length - 1; j > i; j--)
{
if (data[j] < data[lowIndex])
{
lowIndex = j;
}
}
SortUtil.swap(data, i, lowIndex);
}
}
/*public static void main(String[] args)
{
int[] a = {12, 43, 54, 32, 13, 26, 37, 28, 19, 27};
long forest = System.currentTimeMillis();
new SelectionSort().sort(a);
long lastest = System.currentTimeMillis();
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
for(int i:a)
{
System.out.print(i+" ");
}
System.out.println();
System.out.print(lastest - forest);
}*/
}
//ShellSort
package sort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ShellSort implements SortUtil.Sort
{
/*
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data)
{
for (int i = data.length / 2; i > 2; i /= 2)
{
for (int j = 0; j < i; j++)
{
insertSort(data, j, i);
}
}
insertSort(data, 0, 1);
}
/**
* @param data
* @param j
* @param i
*/
private void insertSort(int[] data, int start, int inc)
{
for (int i = start + inc; i < data.length; i += inc)
{
for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc)
{
SortUtil.swap(data, j, j - inc);
}
}
}
}
分享到：
发表评论
相关推荐
关于数据的几种排序算法的程序对比分析，结合具体案例
本文将深入探讨由C语言实现的几种常见排序算法，包括它们的基本原理、实现细节和性能特点。 首先，让我们从最经典的排序算法——冒泡排序（Bubble Sort）开始。冒泡排序通过不断地交换相邻的不正确顺序的元素来逐步...
根据给定文件中的标题、描述、标签以及部分内容，我们可以总结出以下关于几种排序算法的知识点，特别是关于希尔排序的相关细节。 ### 几种排序算法的代码实现 #### 1. **希尔排序** - **定义与原理**：希尔排序是...
下面我们将详细解析链表实现的几种排序算法，以及它们的优缺点。 1. **冒泡排序** (LinkList1.cpp 和 LinkList2.cpp): 冒泡排序是一种简单的交换排序，通过不断比较相邻元素并交换位置，使较大的元素逐渐"浮"到...
这里我们将深入探讨几种最常见的排序算法，包括冒泡排序、选择排序、插入排序、快速排序以及归并排序。 1. 冒泡排序（Bubble Sort） 冒泡排序是最基础的排序算法之一，它通过不断地比较相邻元素并交换位置来实现...
C++中的几种排序算法 C++中的几种排序算法是计算机科学中的一种基本算法，用于对数据进行排序。排序算法的选择取决于具体的应用场景和数据特点。本文将介绍C++中的几种常见的排序算法，包括插入排序、选择排序、...
以下是对标题和描述中提及的几种排序算法的详细解释： 1. **Shell排序**：由Donald Shell于1959年提出，是一种改进的插入排序。它通过将待排序的元素按一定的间隔分组，然后对每组进行插入排序，逐渐减小间隔，直到...
本文将详细介绍Java中常见的几种排序算法，包括冒泡排序、快速排序以及选择排序。 1. **冒泡排序**： 冒泡排序是最基础的排序算法之一，它的主要思想是通过不断比较相邻元素并交换位置，使得较大的元素逐渐“浮”到...
该程序包含了几种算法，读者可对此进行试验
本资源"**C语言几种排序算法实现.zip**"可能包含了一系列用C语言编写的经典排序算法，如冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等。下面将对这些常见的排序算法进行详细介绍。 1. **冒泡排序...
根据给定文件的内容，以下是对学习的几种排序算法的详细知识点总结。 1. 冒泡排序（BubbleSort）： 冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换...
在这篇《基于C语言的几种排序算法的分析》的研究论文中，作者陈思敏对计算机程序设计中常见的几种排序算法进行了深入的分析。文中讨论了排序算法的概念、特点、C语言实现方法以及算法的时间复杂度，还对这些排序算法...
### 数据结构中几种排序算法分析比较 #### 插入排序 **插入排序**是一类简单直观的基于比较的排序算法。其基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 #####...
这个文件"JAVA关于几种排序算法的性能比较.pdf"显然探讨了不同排序算法在Java环境下的效率对比，包括直接插入排序、直接选择排序、冒泡排序、希尔排序、快速排序和堆排序。这些排序算法各有优劣，适用于不同的场景，...
本程序主要演示了归并，插入，快排等几种排序算法在各种不同数据量的情况下的算法效率，适合编程新手对排序算法的认识和学习
7种排序算法程序汇总 冒泡排序 选择排序 插入排序 希排序尔 快速排序 二叉排序树 堆排序
PHP中的几种排序算法 一、 开发环境 1、环境搭建：Windows 7+Apache 2.4.18+MySQL 5.7.11+PHP 7.1.0。 2、文本编辑器：Sublime 3。 二、主要技术 本案例主要使用PHP 7中的几种排序算法：快速排序、选择排序、插入...