Java实现各种排序算法
?
曾經學數據結構的時候，各種排序練的很熟，但是想過用Java怎么實現嗎，以下給出來給你看看，當然閑著就當學習數據結構了，因為jdk提供的工具足夠你應付所有事情。
插入排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class InsertSort implements SortUtil.Sort{
?? 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;
public class BubbleSort implements SortUtil.Sort{
?? 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;
public class SelectionSort implements SortUtil.Sort {
?? public void sort(int[] data) {
? ? int temp;
? ? 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);
? ? }
? }
}
Shell排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class ShellSort implements SortUtil.Sort{
?? 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);
? }
? private void insertSort(int[] data, int start, int inc) {
? ? int temp;
? ? 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);
? ? ? ? }
? ? }
? }
}
快速排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class QuickSort implements SortUtil.Sort{
? 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);
? }
? 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;
public class ImprovedQuickSort implements SortUtil.Sort {
? private static int MAX_STACK_SIZE=4096;
? private static int THRESHOLD=10;
? 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);
? }
?? 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;
public class MergeSort implements SortUtil.Sort{
? 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=data;
? ? }
? ? 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;
public class ImprovedMergeSort implements SortUtil.Sort {
? private static final int THRESHOLD = 10;
? 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 = data;
? ? }
? ? 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;
? ? ? ? } else {
? ? ? ? ? data[k] = temp[j--];
? ? ? ? ? b = temp[j];
? ? ? ? }
? ? }
? }
? 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;
public class HeapSort implements SortUtil.Sort{
? 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;
? ? ? ? ? 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;
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;
? ? data = data[j];
? ? data[j] = temp;
? }
}
轉載于:https://www.cnblogs.com/alaricblog/p/3278287.html
總結
以上是生活随笔為你收集整理的Java实现各种排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 4.Servlet（动态web资源）
- 下一篇： 星型模式、雪花模式和事实星座模式