插入排序：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @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) {
int temp;
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);
}
}
}
}
冒泡排序：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @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) {
int temp;
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);
}
}
}
}
}
快速排序：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @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 i
* @param j
* @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;
}
}
改进后的快速排序：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @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) {
int temp;
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);
}
}
}
}
归并排序：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @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++];
}
}
}
改进后的归并排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @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);
}
}
}
}
堆排序：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @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;
}
}
}
}
SortUtil：
package org.rut.util.algorithm;
import org.rut.util.algorithm.support.BubbleSort;
import org.rut.util.algorithm.support.HeapSort;
import org.rut.util.algorithm.support.ImprovedMergeSort;
import org.rut.util.algorithm.support.ImprovedQuickSort;
import org.rut.util.algorithm.support.InsertSort;
import org.rut.util.algorithm.support.MergeSort;
import org.rut.util.algorithm.support.QuickSort;
import org.rut.util.algorithm.support.SelectionSort;
import org.rut.util.algorithm.support.ShellSort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class SortUtil {
public final static int INSERT = 1;
public final static int BUBBLE = 2;
public final static int SELECTION = 3;
public final static int SHELL = 4;
public final static int QUICK = 5;
public final static int IMPROVED_QUICK = 6;
public final static int MERGE = 7;
public final static int IMPROVED_MERGE = 8;
public final static int HEAP = 9;
public static void sort(int[] data) {
sort(data, IMPROVED_QUICK);
}
private static String[] name={
"insert", "bubble", "selection", "shell", "quick", "improved_quick", "merge", "improved_merge", "heap"
};
private static Sort[] impl=new Sort[]{
new InsertSort(),
new BubbleSort(),
new SelectionSort(),
new ShellSort(),
new QuickSort(),
new ImprovedQuickSort(),
new MergeSort(),
new ImprovedMergeSort(),
new HeapSort()
};
public static String toString(int algorithm){
return name[algorithm-1];
}
public static void sort(int[] data, int algorithm) {
impl[algorithm-1].sort(data);
}
public static interface Sort {
public void sort(int[] data);
}
public static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
相关推荐
在Java编程语言中，排序是数据处理和算法分析的一个核心概念。本文将深入探讨几种常见的排序算法，并提供相应的源码实现。这些算法包括插入排序、选择排序、希尔排序、冒泡排序以及最佳排序（通常指的是快速排序或...
本文将详细介绍如何在 Java 中对包含中文姓氏的对象列表或字符串列表进行排序。 #### 二、基本概念 1. **Collator 类**：这是 Java 中用于文本排序和检索的标准类。`Collator` 类提供了与语言环境相关的字符串排序...
在Java编程语言中，对包含中文、数字和字母的数据进行排序是一项常见的任务。这个场景下，我们关注的是如何实现一个自定义的排序规则，按照数字、字母和汉字的顺序进行排列。以下是对这一主题的详细解释。 首先，...
本文将深入探讨Java中各种排序算法，包括内置库函数和自定义实现，以帮助开发者更好地理解和运用这些技术。 一、内置排序方法 1. `Arrays.sort()`: 这是Java标准库提供的一个强大工具，适用于基本类型的数组（如...
本文将全面解析Java中的各种排序算法，帮助你理解并掌握它们的核心概念、实现方式以及适用场景。 1. 冒泡排序（Bubble Sort） 冒泡排序是最简单的排序算法之一，通过不断交换相邻的逆序元素来逐步排序。其时间...
本文将深入探讨Java中实现的各种排序算法，包括它们的工作原理、优缺点以及如何在实际应用中选择合适的排序方法。 1. 冒泡排序（Bubble Sort） 冒泡排序是最基础的排序算法之一，通过不断交换相邻的错误顺序元素来...
Java ip 地址排序Java ip 地址排序Java ip 地址排序Java ip 地址排序
在编程领域，排序算法是数据结构与算法学习中的基础部分，尤其在Java中，了解和掌握各种排序算法对于提升程序性能至关重要。以下是对标题和描述中提到的Java各种排序算法的详细解释，以及它们的实现代码概述。 1）*...
这个名为"Java各种排序算法代码.zip"的压缩包包含了一系列实现不同排序算法的Java源代码。排序算法是计算机科学中的基本概念，用于对一组数据进行排列。下面将详细讨论这些算法及其在Java中的实现。 1. 冒泡排序...
在Java编程语言中，处理中文和英文混合的排序问题是一个常见的需求，特别是在处理用户输入、数据库数据或文件名等场景。这个"关于中文英文混合排序javaDemo"的示例主要展示了如何实现这样的功能。让我们深入探讨一下...
在上面的代码实现中，我们可以看到，归并排序的时间复杂度为 O(nlog2^n)，这是因为我们需要将原始数组分割成小组，并对每个小组进行排序，然后将排序好的小组合并成一个有序数组。空间复杂度为 O(N)，这是因为我们...
在Java中，可以使用`java.util.Comparator`接口自定义比较规则，根据笔画数对`List<String>`类型的汉字列表进行排序。此外，`java.text.Normalizer`类可以帮助处理Unicode编码，确保笔画计算的准确性。 总的来说，...
Java 中 List 排序 Java 中 List 排序是指在数据库中查出来的列表中对不同的字段重新排序。一般的做法都是使用排序的字段，重新到数据库中查询。如果不到数据库查询，直接在第一次查出来的 List 中排序，无疑会提高...
本文将介绍两种常见的排序算法：直接插入排序和希尔排序，并通过Java代码实现来帮助理解。 1. 直接插入排序（直接插入排序） 直接插入排序是一种简单的排序方法，它的工作原理类似于我们平时手动整理扑克牌。在排序...
Java 八大排序是 Java 语言中八种常用的排序算法，分别是直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序、归并排序、堆排序和 Radix 排序。下面是对每种排序算法的详细介绍： 1. 直接插入排序 基本...
java中数组的自定义排序，种类繁多，简单实现，可自由操控。
本文将深入探讨Java中的各种排序算法，帮助你巩固理解并提升编程技能。 首先，我们从最基本的内部排序算法开始，如冒泡排序（Bubble Sort）。冒泡排序通过不断交换相邻的错误顺序元素来实现排序，它的复杂度在最坏...
在Java中，这些排序算法的实现通常涉及数组操作和递归。`Algorithm.java`文件可能包含了这些排序算法的Java实现代码，而`常见排序算法的实现与性能比较.doc`文档则可能详细比较了这些算法的性能和适用场景。`readme....
Java经典算法 ，各种排序算法 老掉牙 河內塔 費式數列 巴斯卡三角形 三色棋 老鼠走迷官（一） 老鼠走迷官（二） 騎士走棋盤 八個皇后 八枚銀幣 生命遊戲 字串核對 雙色、三色河內塔 背包問題（Knapsack...