java中的几种排序方法

Java中实现排序的那些方法作者：娜 来源：程序员之家 发布者：admin 时间：2009-12-21 11:10:30 点击：820 下面，要和大家分享的是用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。希望对大家有所帮助。插入排序：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;ifor(int j=i;(j>0)&&(data[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;ifor(int j=data.length-1;j>i;j--){if(data[j]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 int lowIndex = i;for (int j = data.length - 1; j > i; j--) {if (data[j] 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;jinsertSort(data,j,i);}}insertSort(data,0,1);}private void insertSort(int[] data, int start, int inc) {int temp;for(int i=start+inc;ifor(int j=i;(j>=inc)&&(data[j]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;//swapSortUtil.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]while((r!=0)&&data[--r]>pivot);SortUtil.swap(data,l,r);}while(lSortUtil.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);//partitionl=i-1;r=j;do{while(data[++l]while((r!=0)&&(data[--r]>pivot));SortUtil.swap(data,l,r);}while(lSortUtil.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;ifor(int j=i;(j>0)&&(data[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;itemp[i]=data[i];}int i1=l;int i2=mid+1;for(int cur=l;curif(i1==mid+1)data[cur]=temp[i2++];else if(i2>r)data[cur]=temp[i1++];else if(temp[i1]data[cur]=temp[i1++];elsedata[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);elseinsertSort(data, l, mid - l + 1);if ((r - mid) > THRESHOLD)mergeSort(data, temp, mid + 1, r);elseinsertSort(data, mid + 1, r - mid);for (i = l; i temp[i] = data[i];}for (j = 1; j temp[r - j + 1] = data[j + mid];}int a = temp[l];int b = temp[r];for (i = l, j = r, k = l; k if (a data[k] = temp[i++];a = temp[i];} else {data[k] = temp[j--];b = temp[j];}}}private void insertSort(int[] data, int start, int len) {for(int i=start+1;ifor(int j=i;(j>start) && data[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;ih.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;iqueue[++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);}//fixdownprivate void fixDown(int k) {int j;while ((j = k if (j 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={

Java中实现排序的那些方法作者：娜 来源：程序员之家 发布者：admin 时间：2009-12-21 11:10:30 点击：820 下面，要和大家分享的是用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。希望对大家有所帮助。插入排序：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;ifor(int j=i;(j>0)&&(data[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;ifor(int j=data.length-1;j>i;j--){if(data[j]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 int lowIndex = i;for (int j = data.length - 1; j > i; j--) {if (data[j] 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;jinsertSort(data,j,i);}}insertSort(data,0,1);}private void insertSort(int[] data, int start, int inc) {int temp;for(int i=start+inc;ifor(int j=i;(j>=inc)&&(data[j]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;//swapSortUtil.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]while((r!=0)&&data[--r]>pivot);SortUtil.swap(data,l,r);}while(lSortUtil.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);//partitionl=i-1;r=j;do{while(data[++l]while((r!=0)&&(data[--r]>pivot));SortUtil.swap(data,l,r);}while(lSortUtil.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;ifor(int j=i;(j>0)&&(data[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;itemp[i]=data[i];}int i1=l;int i2=mid+1;for(int cur=l;curif(i1==mid+1)data[cur]=temp[i2++];else if(i2>r)data[cur]=temp[i1++];else if(temp[i1]data[cur]=temp[i1++];elsedata[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);elseinsertSort(data, l, mid - l + 1);if ((r - mid) > THRESHOLD)mergeSort(data, temp, mid + 1, r);elseinsertSort(data, mid + 1, r - mid);for (i = l; i temp[i] = data[i];}for (j = 1; j temp[r - j + 1] = data[j + mid];}int a = temp[l];int b = temp[r];for (i = l, j = r, k = l; k if (a data[k] = temp[i++];a = temp[i];} else {data[k] = temp[j--];b = temp[j];}}}private void insertSort(int[] data, int start, int len) {for(int i=start+1;ifor(int j=i;(j>start) && data[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;ih.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;iqueue[++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);}//fixdownprivate void fixDown(int k) {int j;while ((j = k if (j 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={


相关文章

  • infosys面试总结

    • 1． 作用域public,private,protected,以及不写时的区别 区别如下: 作用域 当前类 同一package 子孙类 其他package public √ √ √ √ protected √ √ √ × friendly ...查看


  • 用Java集合中的Collections.sort方法对list排序的两种方法

    • 用Collections.sort方法对list排序有两种方法 第一种是list中的对象实现Comparable接口,如下: 01/** 02* 根据order对User排序 03*/ 04public class User impleme ...查看


  • 面向对象程序实验报告撰写模板

    • 面向对象设计实验指导书 2015年9月 信息工程学院 侯向华 目录 实验一 熟悉java 的编程环境 . ................................................................... ...查看


  • JAVA复试问题答案

    • (一) JAVA复试的问题整理 1 Hibernate 的优化流程是如何实现的,流程是怎么样? 1. 尽量使用many-to-one ,避免使用单向one-to-many 象 2 Struts1与Struts2的区别? 在Action 实现 ...查看


  • 信息论与编码论文之香农与java

    • 信息论与编码 学科论文 指导: XXXXX 主题:Java 下模拟香农编码 专业: 信息与计算科学 年级: XXX 姓名: XXX 学号: XXXXXXXX 目录 contents 1.绪论------------------------- ...查看


  • Android中获取正在运行的服务

    • 转载请注明出处:http://blog.csdn.net/qinjuning 关于PackageManager和ActivityManager的使用 ,自己也写了一些DEMO 了,基本上写的线路参考了Settings模块下的 应用程序,大家 ...查看


  • Java员工管理系统实训报告

    • 实 习 报 告 年 级 大三 专 业 计算机科学与技术 学 号姓 名 实习时间 2016.8.8-2016.8.28 实习地点 三峡大学 一.实习目的 进一步了解java 开发的相关知识,掌握java 开发的基本技术,丰富java 开发的实 ...查看


  • 历年软考程序员试题分析

    • 历年软考程序员试题分析及2011年备考建议 程序员考试上午科目和下午科目的考试形式与考核内容已经趋于稳定,考生应紧扣考试大纲和指南,有针对性地进行学习. 1.程序员上午试题分析和备考建议 分析近几年程序员上午试题的考试内容,其知识点和分值分 ...查看


  • 软件体系结构期末试卷

    • 北京工业大学2008 – 2009学年 第二学期考试样题 考试课程: 软件体系结构 II 考试日期:2009 年 12 月 日 学 院: 软件学院 专 业: 软件工程 学 号: 姓名: 成绩: 一 填空题 (共 30 空, 每空 1 分) ...查看


热门内容