- 浏览: 16988 次
- 性别:
- 来自: 郑州
文章分类
最新评论
package com.shine.sort;
/**
* 排序算法 <br>
* @说明:<br>
* 排序算法分为三种:插入排序、交换排序、选择排序 <br>
* 1.插入排序:直接插入排序、折半插入排序、希尔排序 <br>
* 2.交换排序:冒泡排序、快速排序 <br>
* 3.选择排序: 直接选择排序、堆排序 <br>
*/
public class MySort {
/**
* 直接插入排序<br>
* @描述:<br>
* 1. 直接插入排序是第i趟把第i个元素放的前面已经排好序的序列中去<br>
* 2. 重复上述操作。n个元素共需n-1趟扫描,每趟将一个元素插入到它前面的子序列中 <br>
* @复杂度分析:<br>
* 1.时间复杂度:<br>
* 最好情况:当数据序列已排序,时间复杂度为o(n) <br>
* 最坏情况:数据序列反序,时间复杂度为o(n*n) <br>
* 随机:o(n*n) <br>
* 2.空间复杂度:o(1) <br>
* @稳定性:稳定
*/
public static void insertSort(int[] table){
for(int i=1;i<table.length;i++){//n-1趟扫描
int temp=table[i],j;//每趟将table[i]插入到前面排序序列中
for(j=i-1;j>=0&&temp<table[j];j--)
table[j+1]=table[j];//将较大元素向后移动
table[j+1]=temp;//temp到达插入位置
}
}
/**
* 希尔排序 <br>
* @描述: <br>
* 1.将一个数据序列分成若干组,每组由若干相隔一段距离的元素组成,这段距离称为增量,
* 在一组内采用直接插入排序算法进行排序 <br>
* 2.当增量为1时,只有一组,元素是整个序列,再进行一次直接插入排序即可 <br>
* @复杂度分析:
* 1.时间复杂度:时间复杂度比较复杂,具体时间取决于具体增量的序列 <br>
* 2.空间复杂度:o(1)
* @稳定性:不稳定
*/
public static void shellSort(int[] table){
for(int delta=table.length/2;delta>0;delta/=2)//进行若干趟扫描,控制增量,增量减半
for(int i=delta;i<table.length;i++){//一趟分若干组,每组进行直接插入排序
int temp=table[i],j;
for(j=i-delta;j>=0&&temp<table[j];j-=delta)
table[j+delta] = table[j];
table[j+delta] = temp;
}
}
/**
* 冒泡排序 <br>
* @说明: <br>
* 比较两个相邻元素的关键值,如果反序,则交换。若按升序排序,每一趟将被扫描的数据序列中的最大元素交换到
* 最后位置,就像气泡从水里冒出一样。 <br>
* @复杂度分析:<br>
* 1.时间复杂度分析:o(n)-o(n*n)
* 2.空间复杂度分析:o(1)
* @稳定性:稳定
*/
public static void bubleSort(int[] table){
boolean exchange = true;
for(int i=1;i<table.length&&exchange;i++){//有交换时才进行下一趟排序
exchange = false;//假定元素没有交换
for(int j=0;j<table.length-i;j++)
if(table[j]>table[j+1]){
int temp = table[j];
table[j] = table[j+1];
table[j+1] = temp;
exchange = true;
}
}
}
/**
* 快速排序算法 <br>
* @说明: <br>
* 在数据序列中选择一个值作为比较的基准值,每趟从数据序列的两端开始交替进行,将小于基准值的元素交换到序列
* 前段,大于基准值的元素交换到序列后端,介于两者之间的位置则称为基准值的最终位置。同时序列被划分成两个子
* 序列,在用同样的方法对两个子序列进行排序,直到子序列长度为1,则完成排序。
* @复杂度分析: <br>
* 时间复杂度:<br>
* 最好情况:每趟排序将序列分成长度相近的两个子序列。 o(nlog2n) <br>
* 最坏情况:每趟排序将序列分成长度差异很大的两个子序列 o(n*n) <br>
* 空间复杂度:<br>
* 最好情况: o(log2n)
* 最坏情况: o(n)
* @稳定性:不稳定<br>
*/
public static void quickSort(int[] table){
quickSort(table,0,table.length-1);
}
private static void quickSort(int[] table,int begin,int end){
if(begin<end){
int i=begin,j=end;
int vot=table[i];//基准值
while(i!=j){//一趟排序
while(i<j&&vot<=table[j])
j--;
if(i<j)//如果有小元素(当有table[j]<vot的时候,该条件恒成立)
table[i++]=table[j];//把后面的小元素向前移动
while(i<j&&table[i]<=vot)
i++;
if(i<j)
table[j--]=table[i];//把大元素向后移动
}
table[i]=vot;//基准值到达最终位置
quickSort(table,begin,j-1);//前段子序列进行排序
quickSort(table,i+1,end);//后端子序列进行排序
}
}
/**
* 直接选择排序 <br>
* @说明:<br>
* 第一趟从n个元素的数据中选出关键字最小或最大的元素放到最前或最后位置,下一趟再从n-1个元素……。直接选择排序
* 算法可用顺序表和单链表实现。 <br>
* @复杂度: <br>
* 时间复杂度:o(n*n) <br>
* 空间复杂度:o(1) <br>
* @稳定性:不稳定 <br>
*/
public static void selectSort(int[] table){
for(int i=0;i<table.length-1;i++){
int min=i;
for(int j=i+1;j<table.length;j++)
if(table[j]<table[min])
min=j;
if(min!=i){
int temp=table[i];
table[i]=table[min];
table[min]=temp;
}
}
}
/**
* 堆排序
* @说明: <br>
* 1.堆:这里的堆不是数据结构里面的堆栈,而是一种数据结构。堆可以视为一颗完全二叉树,完全二叉树的一个优秀的性质是
* 除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个节点对应数组中的一个元素。二叉堆一般分
* 为两种,最小堆和最大堆。<br>
* 2.最大堆:堆中每个父节点的值都大于等于其孩子节点,这样的堆就是一个最大堆。<br>
* 最小堆:对中的每个父节点都小于等于其孩子节点,这样的堆就是一个最小堆。 <br>
* 3.堆排序:堆排序分两个阶段。首先将一个数据序列建成堆序列,根节点值是最小(大)值;然后采用选择排序思路,每趟将
* 根结点值交换到最后,再将其余值调整成堆,依次重复,直到排序完成。<br>
* @复杂度:<br>
* 时间复杂度:o(n*log2n) <br>
* 空间复杂度:o(1) <br>
* @稳定性:不稳定
*/
public static void heapSort(int[] table){//堆排序
int n=table.length;
for(int j=n/2-1;j>=0;j--) //创建最小堆
sift(table,j,n-1);
for(int j=n-1;j>0;j--){ //每趟将最小值交换到后面,再调整成堆
int temp=table[0];
table[0]=table[j];
table[j]=temp;
sift(table,0,j-1);
}
}
//将以begin为根的子树调整成最小堆,begin、end是序列下届和上届
private static void sift(int[] table,int begin,int end){
int i=begin,j=2*i+1;//i为子树的根,j为i节点的左孩子
int temp=table[i];//获得第i个元素的值
while(j<=end){ //沿较小值孩子节点向下筛选
if(j<end&&table[j]>table[j+1]) //数组元素比较
j++; //j为左右孩子的较小者
if(temp>table[j]){ //若父母结点值较大
table[i]=table[j]; //孩子节点中的较小者上移
i=j; //i,j向下一层
j=2*i+1;
}
else break;
}
table[i]=temp;//当前子树的原根值调整后的位置
}
/**
* 归并排序
* @param args
*/
//一次归并方法: m和r分别是两个相邻的两个已排序的子序列的起始下标
private static void merge(int[] X,int[] Y,int m,int r,int n){ //一次归并
int i=m,j=r,k=m;
while(i<r&&j<r+n&&j<X.length){ //将X中两个相邻子序列归并到Y中
if(X[i]<X[j]) //较小值复制到Y中
Y[k++]=X[i++];
else Y[k++]=X[j++];
while(i<r) //将前一个子序列剩余元素复制到Y中
Y[k++]=X[i++];
while(j<r+n&&j<X.length) //将后一个子序列剩余元素复制到Y中
Y[k++]=X[j++];
}
}
//一趟归并
private static void mergepass(int[] X,int[] Y,int n){//一趟归并
int i=0;
while(i<X.length-2*n+1){
merge(X,Y,i,i+n,n);
i+=2*n;
}
if(i+n<X.length)
merge(X,Y,i,i+n,n); //再一次归并
else
for(int j=i;j<X.length;j++) //将X剩余元素复制到Y中
Y[j]=X[j];
}
public static void mergeSort(int[] X){ //归并排序
int[] Y = new int[X.length];
int n=1;
while(n<X.length){
mergepass(X,Y,n);
n*=2;
if(n<X.length){
mergepass(Y,X,n);
n*=2;
}
}
}
public static void main(String[] args) {
int[] table = {22,11,65,33,21,23,10};
System.out.println("直接插入排序:");
insertSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n希尔排序:");
shellSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n冒泡排序:");
bubleSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n快速排序:");
quickSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n直接选择排序:");
selectSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n堆排序:");
heapSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n归并排序:");
mergeSort(table);
for(int x: table)
System.out.print(x+"\t");
}
}
/**
* 排序算法 <br>
* @说明:<br>
* 排序算法分为三种:插入排序、交换排序、选择排序 <br>
* 1.插入排序:直接插入排序、折半插入排序、希尔排序 <br>
* 2.交换排序:冒泡排序、快速排序 <br>
* 3.选择排序: 直接选择排序、堆排序 <br>
*/
public class MySort {
/**
* 直接插入排序<br>
* @描述:<br>
* 1. 直接插入排序是第i趟把第i个元素放的前面已经排好序的序列中去<br>
* 2. 重复上述操作。n个元素共需n-1趟扫描,每趟将一个元素插入到它前面的子序列中 <br>
* @复杂度分析:<br>
* 1.时间复杂度:<br>
* 最好情况:当数据序列已排序,时间复杂度为o(n) <br>
* 最坏情况:数据序列反序,时间复杂度为o(n*n) <br>
* 随机:o(n*n) <br>
* 2.空间复杂度:o(1) <br>
* @稳定性:稳定
*/
public static void insertSort(int[] table){
for(int i=1;i<table.length;i++){//n-1趟扫描
int temp=table[i],j;//每趟将table[i]插入到前面排序序列中
for(j=i-1;j>=0&&temp<table[j];j--)
table[j+1]=table[j];//将较大元素向后移动
table[j+1]=temp;//temp到达插入位置
}
}
/**
* 希尔排序 <br>
* @描述: <br>
* 1.将一个数据序列分成若干组,每组由若干相隔一段距离的元素组成,这段距离称为增量,
* 在一组内采用直接插入排序算法进行排序 <br>
* 2.当增量为1时,只有一组,元素是整个序列,再进行一次直接插入排序即可 <br>
* @复杂度分析:
* 1.时间复杂度:时间复杂度比较复杂,具体时间取决于具体增量的序列 <br>
* 2.空间复杂度:o(1)
* @稳定性:不稳定
*/
public static void shellSort(int[] table){
for(int delta=table.length/2;delta>0;delta/=2)//进行若干趟扫描,控制增量,增量减半
for(int i=delta;i<table.length;i++){//一趟分若干组,每组进行直接插入排序
int temp=table[i],j;
for(j=i-delta;j>=0&&temp<table[j];j-=delta)
table[j+delta] = table[j];
table[j+delta] = temp;
}
}
/**
* 冒泡排序 <br>
* @说明: <br>
* 比较两个相邻元素的关键值,如果反序,则交换。若按升序排序,每一趟将被扫描的数据序列中的最大元素交换到
* 最后位置,就像气泡从水里冒出一样。 <br>
* @复杂度分析:<br>
* 1.时间复杂度分析:o(n)-o(n*n)
* 2.空间复杂度分析:o(1)
* @稳定性:稳定
*/
public static void bubleSort(int[] table){
boolean exchange = true;
for(int i=1;i<table.length&&exchange;i++){//有交换时才进行下一趟排序
exchange = false;//假定元素没有交换
for(int j=0;j<table.length-i;j++)
if(table[j]>table[j+1]){
int temp = table[j];
table[j] = table[j+1];
table[j+1] = temp;
exchange = true;
}
}
}
/**
* 快速排序算法 <br>
* @说明: <br>
* 在数据序列中选择一个值作为比较的基准值,每趟从数据序列的两端开始交替进行,将小于基准值的元素交换到序列
* 前段,大于基准值的元素交换到序列后端,介于两者之间的位置则称为基准值的最终位置。同时序列被划分成两个子
* 序列,在用同样的方法对两个子序列进行排序,直到子序列长度为1,则完成排序。
* @复杂度分析: <br>
* 时间复杂度:<br>
* 最好情况:每趟排序将序列分成长度相近的两个子序列。 o(nlog2n) <br>
* 最坏情况:每趟排序将序列分成长度差异很大的两个子序列 o(n*n) <br>
* 空间复杂度:<br>
* 最好情况: o(log2n)
* 最坏情况: o(n)
* @稳定性:不稳定<br>
*/
public static void quickSort(int[] table){
quickSort(table,0,table.length-1);
}
private static void quickSort(int[] table,int begin,int end){
if(begin<end){
int i=begin,j=end;
int vot=table[i];//基准值
while(i!=j){//一趟排序
while(i<j&&vot<=table[j])
j--;
if(i<j)//如果有小元素(当有table[j]<vot的时候,该条件恒成立)
table[i++]=table[j];//把后面的小元素向前移动
while(i<j&&table[i]<=vot)
i++;
if(i<j)
table[j--]=table[i];//把大元素向后移动
}
table[i]=vot;//基准值到达最终位置
quickSort(table,begin,j-1);//前段子序列进行排序
quickSort(table,i+1,end);//后端子序列进行排序
}
}
/**
* 直接选择排序 <br>
* @说明:<br>
* 第一趟从n个元素的数据中选出关键字最小或最大的元素放到最前或最后位置,下一趟再从n-1个元素……。直接选择排序
* 算法可用顺序表和单链表实现。 <br>
* @复杂度: <br>
* 时间复杂度:o(n*n) <br>
* 空间复杂度:o(1) <br>
* @稳定性:不稳定 <br>
*/
public static void selectSort(int[] table){
for(int i=0;i<table.length-1;i++){
int min=i;
for(int j=i+1;j<table.length;j++)
if(table[j]<table[min])
min=j;
if(min!=i){
int temp=table[i];
table[i]=table[min];
table[min]=temp;
}
}
}
/**
* 堆排序
* @说明: <br>
* 1.堆:这里的堆不是数据结构里面的堆栈,而是一种数据结构。堆可以视为一颗完全二叉树,完全二叉树的一个优秀的性质是
* 除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个节点对应数组中的一个元素。二叉堆一般分
* 为两种,最小堆和最大堆。<br>
* 2.最大堆:堆中每个父节点的值都大于等于其孩子节点,这样的堆就是一个最大堆。<br>
* 最小堆:对中的每个父节点都小于等于其孩子节点,这样的堆就是一个最小堆。 <br>
* 3.堆排序:堆排序分两个阶段。首先将一个数据序列建成堆序列,根节点值是最小(大)值;然后采用选择排序思路,每趟将
* 根结点值交换到最后,再将其余值调整成堆,依次重复,直到排序完成。<br>
* @复杂度:<br>
* 时间复杂度:o(n*log2n) <br>
* 空间复杂度:o(1) <br>
* @稳定性:不稳定
*/
public static void heapSort(int[] table){//堆排序
int n=table.length;
for(int j=n/2-1;j>=0;j--) //创建最小堆
sift(table,j,n-1);
for(int j=n-1;j>0;j--){ //每趟将最小值交换到后面,再调整成堆
int temp=table[0];
table[0]=table[j];
table[j]=temp;
sift(table,0,j-1);
}
}
//将以begin为根的子树调整成最小堆,begin、end是序列下届和上届
private static void sift(int[] table,int begin,int end){
int i=begin,j=2*i+1;//i为子树的根,j为i节点的左孩子
int temp=table[i];//获得第i个元素的值
while(j<=end){ //沿较小值孩子节点向下筛选
if(j<end&&table[j]>table[j+1]) //数组元素比较
j++; //j为左右孩子的较小者
if(temp>table[j]){ //若父母结点值较大
table[i]=table[j]; //孩子节点中的较小者上移
i=j; //i,j向下一层
j=2*i+1;
}
else break;
}
table[i]=temp;//当前子树的原根值调整后的位置
}
/**
* 归并排序
* @param args
*/
//一次归并方法: m和r分别是两个相邻的两个已排序的子序列的起始下标
private static void merge(int[] X,int[] Y,int m,int r,int n){ //一次归并
int i=m,j=r,k=m;
while(i<r&&j<r+n&&j<X.length){ //将X中两个相邻子序列归并到Y中
if(X[i]<X[j]) //较小值复制到Y中
Y[k++]=X[i++];
else Y[k++]=X[j++];
while(i<r) //将前一个子序列剩余元素复制到Y中
Y[k++]=X[i++];
while(j<r+n&&j<X.length) //将后一个子序列剩余元素复制到Y中
Y[k++]=X[j++];
}
}
//一趟归并
private static void mergepass(int[] X,int[] Y,int n){//一趟归并
int i=0;
while(i<X.length-2*n+1){
merge(X,Y,i,i+n,n);
i+=2*n;
}
if(i+n<X.length)
merge(X,Y,i,i+n,n); //再一次归并
else
for(int j=i;j<X.length;j++) //将X剩余元素复制到Y中
Y[j]=X[j];
}
public static void mergeSort(int[] X){ //归并排序
int[] Y = new int[X.length];
int n=1;
while(n<X.length){
mergepass(X,Y,n);
n*=2;
if(n<X.length){
mergepass(Y,X,n);
n*=2;
}
}
}
public static void main(String[] args) {
int[] table = {22,11,65,33,21,23,10};
System.out.println("直接插入排序:");
insertSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n希尔排序:");
shellSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n冒泡排序:");
bubleSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n快速排序:");
quickSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n直接选择排序:");
selectSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n堆排序:");
heapSort(table);
for(int x: table)
System.out.print(x+"\t");
System.out.println("\n归并排序:");
mergeSort(table);
for(int x: table)
System.out.print(x+"\t");
}
}
发表评论
-
String,StringBuffer,StringBuilder的区别
2015-02-03 22:45 466String 字符串常量StringBuffer 字符 ... -
设计模式——工厂模式
2015-02-02 17:21 370说明: 工厂模式主要是为创建对象提供方便。 ... -
java类集之Queue
2015-01-30 16:38 293Queue接口: ... -
java类集之List
2015-01-30 14:25 464程序想删除一个A对象 ... -
java中的类集之Set
2015-01-29 17:11 478java容器中有三个接口:Iterato ... -
栈 java实现
2015-01-29 17:12 579package com.shine.stack; /* * ... -
队列 java实现
2015-01-28 16:27 508package com.shine.queue; /* * ... -
矩阵 java实现
2015-01-28 16:24 696package com.shine.matrix; /* * ... -
链表 java实现
2015-01-28 16:22 445package com.shine.linearList; / ... -
java中的同步机制
2015-01-28 14:37 731在java中,控制线程的同步是使用synchronized关键 ...
相关推荐
选择排序 二分排序 及时终止的选择排序 冒泡排序 及时终止的冒泡排序 快速排序 插入排序 希尔排序 堆排序 利用附加数组重排数组元素 原地重排数组元素
(1)直接插入排序算法验证。 (2)快速排序算法验证。 (3)直接选择排序算法验证。 几种简单的排序算法代码
常见的几种排序方式,包括选择排序,冒泡排序,快速排序,希尔排序,堆排序,插入排序。vs2008实现,对话框方式,主要实现字符串的由小到大排序。点击“几种排序方法.vcproj“运行。字符集使用多字节集,不能用...
几种简单、高效的插入排序法,直接插入排序、冒泡排序法、选择排序,代码简单明了,可直接使用。
C++中的几种排序方法介绍,并给出相关代码。包括冒泡排序法,简单排序法,希尔排序法和快速排序法
数据结构报告c++,简单选择排序,冒牌排序,插入排序,快速排序,两路合并排序,堆排序,几种排序方法的比较,有详细的源代码和实验报告
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
包括有十种排序方法,有堆排序,归并排序,基排序,简单选择排序,快速排序,冒泡排序等等
几种内部排序算法的Java实现 各种内部排序方法的比较 直接插入排序 折半插入排序 希尔排序 起泡排序 快速排序 简单选择排序 树形选择排序 堆排序 归并排序 基数排序
起泡排序 直接插入排序 简单选择排序 快速排序 希尔排序 堆排序
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...
几种简单算法的源代码和动画演示,动画演示是用HTML来实现的。
java中几种简单的排序.doc
用C#实现的几种典型排序算法,包括二叉树排序、快速排序、希尔排序、插入排序、冒泡排序、选择排序等,代码简单易懂,适合初学者,供学习教育用
1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较; (2)待排序表的表长不小于100,表中数据随机产生,至少用5组不同数据作比较,比较指标有:关键字参加比较次数和关键字的移动次数...
对直接插入排序、希尔排序、冒泡排序、快排、简单选择排序、堆排序的性能进行分析:比较各种排序算法在不同测试数据情况下的比较次数、移动次数。
冒泡排序、快速排序、直接插入排序、简单选择排序 等经典算法的思想介绍,大白话简单易懂。并用java实现。代码拿去即可用,不需做任何修改! 部分内容: /** * 快排:O(n*logn);如果是从小到大排序; * 思想:选...
c++的几种常见的大小排序的算法的模板,包括冒泡排序、选择排序、木桶排序、快速排序等,这些不同的算法的复杂度和效率也不同,里面有说明
排序算法不少于5种; 待排序的元素的关键字为整数; 比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表,以便比较各种...
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试