Java 部分排序算法
、
import java.io.*;
import java.math.*;
import java.util.*;
public class Algr{
public static int array[] = new int[]{3, 9, 1, 2, 8, 11, 34, 21, 0, 23, 22, 10, 14, 2};
public enum Type{Bubble, Selection, Insert, Shell, Counter, Quick};
public static void main(String[] args){
sort(array, Type.Bubble);
random(array);
sort(array, Type.Selection);
random(array);
sort(array, Type.Insert);
random(array);
sort(array, Type.Shell);
random(array);
sort(array, Type.Counter);
random(array);
sort(array, Type.Quick);
}
public static void random(int[] array){
Random random = new Random();
int n = array.length;
for(int i=0; i< n; i++){
swap(array, i, Math.abs(random.nextInt() % n));
}
}
public static void sort(int[] array, Type type){
if(array == null || array.length ==0){
return;
}
output(type.name(), array);
switch(type){
case Bubble:
bubble(array);
break;
case Selection:
selection(array);
break;
case Insert:
insert(array);
break;
case Shell:
shell(array);
break;
case Counter:
counterSort(array);
break;
case Quick:
quickSort(array);
break;
}
output(type.name(), array);
}
public static void quickSort(int[] array){
int n = array.length;
quickSort(array, 0, n-1);
}
public static void quickSort(int[] array, int left, int right){
if(left >= right){
return;
}
final int start = left;
final int end = right;
int mid = array[left];
while(left < right){
while(array[right] >= mid && left < right){
right--;
}
if(left < right){
array[left] = array[right];
}
while(array[left] < mid && left < right){
left++;
}
if(left < right){
array[right] = array[left];
}
}
array[left] = mid;
quickSort(array, start, left -1);
quickSort(array, left +1, end);
}
// stable N 计数排序,需要额外的空间,并且对待排序的数范围有要求
public static void counterSort(int[] array){
int n = array.length;
int max = getMax(array);
int[] counterArray = new int[max+1];
for(int i=0; i< n ; i++){
counterArray[array[i]]++;
}
int index = 0;
for(int i=0; i<= max; i++){
while(counterArray[i]>0){
array[index] = i;
index++;
counterArray[i]--;
}
}
}
public static int getMax(int[] array){
int max = array[0];
int n = array.length;
for(int i=1; i<n; i++ ){
if(array[i] > max){
max = array[i];
}
}
return max;
}
// instable N^1.5 直接插入排序的变种,利用有序化程度越高,排序越快的特性,逐步缩小增量,将数组有序化
public static void shell(int[] array){
int n = array.length;
int d = n/2;
while(d >= 1){
shellInsertion(array, d);
d = d/2;
}
}
public static void shellInsertion(int[] array, int d){
int n = array.length;
for(int i=d; i< n; i = i+ d ){
int k = i;
int target = array[k];
while(k >= d && target < array[k-d]){
array[k] = array[k-d];
k = k -d;
}
array[k] = target;
}
}
// stable N^2 插入算法和冒泡算法的不同之处在于,它是选定值和前面所有值逐个比较。而不是前后两个比较
public static void insert(int[] array){
int n = array.length;
for(int i=1; i< n; i++){
int k = i;
int target = array[k];
while(k >= 1 && target < array[k-1]){
array[k] = array[k-1];
k--;
}
array[k] = target;
}
}
// instable N^2 选择算法是从无序区中选择一个最小的替换到有序区的指定位置;
public static void selection(int[] array){
int n = array.length;
for(int i=0; i< n; i++){
int k = i;
for(int j= i+1; j< n; j++){
if(array[j] < array[k]){
k = j;
}
}
swap(array, i, k);
}
}
public static void output(String name, int[] array){
System.out.print(name +" ");
for(int i=0; i< array.length; i++){
System.out.print(array[i] +" ");
}
System.out.println();
}
// stable N^2
public static void bubble(int[] array){
int size = array.length;
for(int i=0; i< size; i++){
boolean bSwap = false;
for(int j=size-1; j>0; j--){
if(array[j]< array[j-1]){
swap(array, j, j-1);
bSwap = true;
}
}
if(bSwap == false){
break;
}
}
}
public static void swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
最新文章
- 2015.4.19 为什么footer下a的索引值那么大
- 5-26课堂作业——组员投票Alpha版存在的问题
- 关于Android真机调测Profiler
- cvReleaseImage 释放内存出错
- KochSnow曲线
- HDOJ(HDU) 2115 I Love This Game(排序排序、、、)
- nyist 58 最小步数 BFS
- CodeForces 678A Johny Likes Numbers
- bigdecimal更精确的浮点处理方式
- Python序列化和反序列化
- 关于Makefile,Makefile.in,Makefile.am,Configure功能及相互关系的问题
- HTML5 video 播放视频黑屏
- MyBatis笔记----多表关联查询两种方式实现
- wav文件格式分析与详解
- 【 Gym - 101138F 】GukiZ Height (数学)
- Qt532界面.ZC测试
- bzoj2152 (点分治)
- MVC5使用EF6 Code First--创建EF数据模型(一)
- 百度离线下载Tampermonkey脚本
- 能添加图标的label
热门文章
- Python-同时匹配邮箱和电话号码的正则表达式
- 求教——使用node做表单,刷新浏览器页面,浏览器为什么会重复提交上次所填的信息
- 数据库知识整理<;一>;
- 用sass画蜗牛
- Mac上搭建直播服务器Nginx+rtmp
- 使用jquery实现简单的拖动效果,分享源码
- paip.哈米架构CAO.txt
- Atitit..组件化事件化的编程模型--(2)---------Web datagridview 服务器端控件的实现原理and总结
- atitit.GMT UTC Catitit.GMT UTC CST DST CET 星期 月份 节日 时间的不同本质and起源
- JAVA实现多线程入门