- 浏览: 161964 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (193)
- Axis2 (10)
- Andriod (2)
- Java (22)
- Eclipse (2)
- 程序人生 (3)
- Windows (1)
- Sql Server 2005/2008 (7)
- 健身 (2)
- Log4j (1)
- Ant (1)
- Fatjar (2)
- 国际化 (1)
- Linux (3)
- JDBC (1)
- Oracle (2)
- 各种报错 (4)
- SWT (5)
- Tomcat (2)
- 车辆管理 (1)
- SVN (2)
- Spring (5)
- 域名服务器 (0)
- HaoWaYa (1)
- FTP (1)
- 集散中心 (1)
- 专业知识 (1)
- 面试准备 (19)
- 设计模式 (22)
- Junit (1)
- 软件下载 (3)
- 深入理解Java虚拟机 (3)
- 数据结构 (4)
- 雅思 托福 (0)
- UML (1)
- Maven (1)
- CV (1)
- ServiceMix (1)
- 电子书 (5)
- Struts1/2 (4)
- DOM W3C DHTML (3)
- Jawr (1)
- LoadRunner (1)
- Java反编译 (0)
- 英语学习 (0)
- 技术书籍 (1)
- Cygwin (0)
- ibatis (1)
- 数据库 (1)
- jQuery (0)
- s (2)
- 源代码项目 (5)
- JSRs (0)
- JCP (0)
- XML (2)
- Dojo (3)
- Effective Java (1)
- 一站到底 (3)
- JavaScript (6)
- DB2 (1)
- 刷机 (1)
- 字符 (1)
- Dynamic Web Project (1)
- 股市日记 (1)
- 代码片段 (0)
- CSS (1)
- PDF (0)
- 英语口语 (1)
- 乒乓球 (1)
- 体检 (0)
- 送花 (0)
- 面试准备-再战江湖 (5)
- ddq (0)
- sss (0)
- ssssss (0)
- 2020面试 (0)
最新评论
-
samsongbest:
Copperfield 写道你的目标很远大,佩服~惭愧,都忘了 ...
人生目标 -
Copperfield:
你的目标很远大,佩服~
人生目标
http://justsee.iteye.com/blog/1098724
常见的内部排序:
下面介绍这十种常见内部排序(都是从小到大的排序)
直接选择排序
- import java.util.*;
- //定义一个数据包装类
- class DataWrap implements Comparable<DataWrap>
- {
- int data;
- String flag;
- public DataWrap( int data, String flag)
- {
- this .data = data;
- this .flag = flag;
- }
- public String toString()
- {
- return data + flag;
- }
- //根据data实例变量来决定两个DataWrap的大小
- public int compareTo(DataWrap dw)
- {
- return this .data > dw.data ? 1
- : (this .data == dw.data ? 0 : - 1 );
- }
- }
- public class SelectSort
- {
- public static void selectSort(DataWrap[] data)
- {
- System.out.println("开始排序" );
- int arrayLength = data.length;
- //依次进行n-1趟比较, 第i趟比较将第i大的值选出放在i位置上。
- for ( int i = 0 ; i < arrayLength - 1 ; i++ )
- {
- int minIndex = i ;
- //第i个数据只需和它后面的数据比较
- for ( int j = i + 1 ; j < arrayLength ; j++ )
- {
- //如果第i位置的数据 > j位置的数据, 交换它们
- if (data[i].compareTo(data[j]) > 0 )
- {
- DataWrap tmp = data[i];
- data[i] = data[j];
- data[j] = tmp;
- }
- }
- System.out.println(java.util.Arrays.toString(data));
- }
- }
- public static void main(String[] args)
- {
- DataWrap[] data = {
- new DataWrap( 21 , "" ),
- new DataWrap( 30 , "" ),
- new DataWrap( 49 , "" ),
- new DataWrap( 30 , "*" ),
- new DataWrap( 16 , "" ),
- new DataWrap( 9 , "" )
- };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- selectSort(data);
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
优化后:
- import java.util.*;
- class DataWrap implements Comparable<DataWrap>
- {
- int data;
- String flag;
- public DataWrap( int data, String flag)
- {
- this .data = data;
- this .flag = flag;
- }
- public String toString()
- {
- return data + flag;
- }
- public int compareTo(DataWrap dw)
- {
- return this .data > dw.data ? 1
- : (this .data == dw.data ? 0 : - 1 );
- }
- }
- public class SelectSort2
- {
- public static void selectSort(DataWrap[] data)
- {
- System.out.println("开始排序" );
- int arrayLength = data.length;
- //依次进行n-1趟比较, 第i趟比较将第i大的值选出放在i位置上。
- for ( int i = 0 ; i < arrayLength - 1 ; i++ )
- {
- //minIndex永远保留本趟比较中最小值的索引
- int minIndex = i ;
- //第i个数据只需和它后面的数据比较
- for ( int j = i + 1 ; j < arrayLength ; j++ )
- {
- //如果第minIndex位置的数据 > j位置的数据
- if (data[minIndex].compareTo(data[j]) > 0 )
- {
- //将j的值赋给minIndex
- minIndex = j;
- }
- }
- //每趟比较最多交换一次
- if (minIndex != i)
- {
- DataWrap tmp = data[i];
- data[i] = data[minIndex];
- data[minIndex] = tmp;
- }
- System.out.println(java.util.Arrays.toString(data));
- }
- }
- public static void main(String[] args)
- {
- DataWrap[] data = {
- new DataWrap( 21 , "" ),
- new DataWrap( 30 , "" ),
- new DataWrap( 49 , "" ),
- new DataWrap( 30 , "*" ),
- new DataWrap( 16 , "" ),
- new DataWrap( 9 , "" )
- };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- selectSort(data);
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
- //时间复杂度:n的平方
- //空间复杂度:1
- //稳定性:不稳定
堆排序
建大堆求得从小到大的排序。每次建立大堆把大堆顶与数组最后一个元素交换。
- import java.util.*;
- //定义一个数据包装类
- class DataWrap implements Comparable<DataWrap>
- {
- int data;
- String flag;
- public DataWrap( int data, String flag)
- {
- this .data = data;
- this .flag = flag;
- }
- public String toString()
- {
- return data + flag;
- }
- //根据data实例变量来决定两个DataWrap的大小
- public int compareTo(DataWrap dw)
- {
- return this .data > dw.data ? 1
- : (this .data == dw.data ? 0 : - 1 );
- }
- }
- public class HeapSort
- {
- public static void heapSort(DataWrap[] data)
- {
- System.out.println("开始排序" );
- int arrayLength = data.length;
- //循环建堆
- for ( int i = 0 ; i < arrayLength - 1 ; i++ ) //n-1次循环
- {
- //建堆
- builMaxdHeap(data , arrayLength - 1 - i);
- //交换堆顶和最后一个元素
- swap(data , 0 , arrayLength - 1 - i);
- System.out.println(java.util.Arrays.toString(data));
- }
- }
- //对data数组从0到lastIndex建大顶堆
- private static void builMaxdHeap(DataWrap[] data , int lastIndex)
- {
- //从lastIndex处节点(最后一个节点)的父节点开始
- for ( int i = (lastIndex - 1 ) / 2 ; i >= 0 ; i--)
- {
- //k保存当前正在判断的节点
- int k = i;
- //如果当前k节点的子节点存在
- while (k * 2 + 1 <= lastIndex)
- {
- //k节点的左子节点的索引
- int biggerIndex = 2 * k + 1 ;
- //如果biggerIndex小于lastIndex,即biggerIndex + 1
- //代表的k节点的右子节点存在
- if (biggerIndex < lastIndex)
- {
- //如果右子节点的值较大
- if (data[biggerIndex].compareTo(data[biggerIndex + 1 ]) < 0 )
- {
- //biggerIndex总是记录较大子节点的索引
- biggerIndex++;
- }
- }
- //如果k节点的值小于其较大子节点的值
- if (data[k].compareTo(data[biggerIndex]) < 0 )
- {
- //交换它们
- swap(data , k , biggerIndex);
- //将biggerIndex赋给k,开始while循环的下一次循环,
- //重新保证k节点的值大于其左、右子节点的值。
- k = biggerIndex;
- }
- else
- {
- break ;
- }
- }
- }
- }
- //交换data数组中i、j两个索引处的元素
- private static void swap(DataWrap[] data , int i , int j)
- {
- DataWrap tmp = data[i];
- data[i] = data[j];
- data[j] = tmp;
- }
- public static void main(String[] args)
- {
- DataWrap[] data = {
- new DataWrap( 21 , "" ),
- new DataWrap( 30 , "" ),
- new DataWrap( 49 , "" ),
- new DataWrap( 30 , "*" ),
- new DataWrap( 21 , "*" ),
- new DataWrap( 16 , "" ),
- new DataWrap( 9 , "" )
- };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- heapSort(data);
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
- //时间复杂度:nlog2n
- //空间复杂度:1
- //稳定性:不稳定
冒泡排序
- import java.util.*;
- //定义一个数据包装类
- class DataWrap implements Comparable<DataWrap>
- {
- int data;
- String flag;
- public DataWrap( int data, String flag)
- {
- this .data = data;
- this .flag = flag;
- }
- public String toString()
- {
- return data + flag;
- }
- //根据data实例变量来决定两个DataWrap的大小
- public int compareTo(DataWrap dw)
- {
- return this .data > dw.data ? 1
- : (this .data == dw.data ? 0 : - 1 );
- }
- }
- public class BubbleSort
- {
- public static void bubbleSort(DataWrap[] data)
- {
- System.out.println("开始排序" );
- int arrayLength = data.length;
- //依次进行n-1趟比较, 第i趟把第i大的值选出放在arrayLength-1-i位置上。
- for ( int i = 0 ; i < arrayLength - 1 ; i++ )
- {
- boolean flag = false ;
- for ( int j = 0 ; j < arrayLength - 1 - i ; j++ )
- {
- //如果j索引处的元素大于j+1索引处的元素
- if (data[j].compareTo(data[j + 1 ]) > 0 )
- {
- //交换它们
- DataWrap tmp = data[j + 1 ];
- data[j + 1 ] = data[j];
- data[j] = tmp;
- flag = true ;
- }
- }
- System.out.println(java.util.Arrays.toString(data));
- //如果某趟没有发生交换,则表明已处于有序状态
- if (!flag)
- {
- break ;
- }
- }
- }
- public static void main(String[] args)
- {
- DataWrap[] data = {
- new DataWrap( 9 , "" ),
- new DataWrap( 16 , "" ),
- new DataWrap( 21 , "*" ),
- new DataWrap( 23 , "" ),
- new DataWrap( 30 , "" ),
- new DataWrap( 49 , "" ),
- new DataWrap( 21 , "" ),
- new DataWrap( 30 , "*" )
- };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- bubbleSort(data);
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
- //时间复杂度:
- //空间复杂度:1
- //稳定性:稳定
快速排序
用到了递归。注意分界值是和 j交换来建立从小到大的排序。
- import java.util.*;
- //定义一个数据包装类
- class DataWrap implements Comparable<DataWrap>
- {
- int data;
- String flag;
- public DataWrap( int data, String flag)
- {
- this .data = data;
- this .flag = flag;
- }
- public String toString()
- {
- return data + flag;
- }
- //根据data实例变量来决定两个DataWrap的大小
- public int compareTo(DataWrap dw)
- {
- return this .data > dw.data ? 1
- : (this .data == dw.data ? 0 : - 1 );
- }
- }
- public class QuickSort
- {
- //将指定数组的i和j索引处的元素交换
- private static void swap(DataWrap[] data, int i, int j)
- {
- DataWrap tmp;
- tmp = data[i];
- data[i] = data[j];
- data[j] = tmp;
- }
- //对data数组中从start~end索引范围的子序列进行处理
- //使之满足所有小于分界值的放在左边,所有大于分界值的放在右边
- private static void subSort(DataWrap[] data
- , int start , int end)
- {
- //需要排序
- if (start < end)
- {
- //以第一个元素作为分界值
- DataWrap base = data[start];
- //i从左边搜索,搜索大于分界值的元素的索引
- int i = start;
- //j从右边开始搜索,搜索小于分界值的元素的索引
- int j = end + 1 ;
- while ( true )
- {
- //找到大于分界值的元素的索引,或i已经到了end处
- while (i < end && data[++i].compareTo(base) <= 0 );
- //找到小于分界值的元素的索引,或j已经到了start处
- while (j > start && data[--j].compareTo(base) >= 0 );
- if (i < j)
- {
- swap(data , i , j);
- }
- else
- {
- break ;
- }
- }
- swap(data , start , j);
- //递归左子序列
- subSort(data , start , j - 1 );
- //递归右边子序列
- subSort(data , j + 1 , end);
- }
- }
- public static void quickSort(DataWrap[] data)
- {
- subSort(data , 0 , data.length - 1 );
- }
- public static void main(String[] args)
- {
- DataWrap[] data = {
- new DataWrap( 9 , "" ),
- new DataWrap(- 16 , "" ),
- new DataWrap( 21 , "*" ),
- new DataWrap( 23 , "" ),
- new DataWrap(- 30 , "" ),
- new DataWrap(- 49 , "" ),
- new DataWrap( 21 , "" ),
- new DataWrap( 30 , "*" ),
- new DataWrap( 13 , "*" )
- };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- quickSort(data);
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
- //时间复杂度:n的平方
- //空间复杂度:1
- //稳定性:稳定
直接插入排序
- import java.util.*;
- //定义一个数据包装类
- class DataWrap implements Comparable<DataWrap>
- {
- int data;
- String flag;
- public DataWrap( int data, String flag)
- {
- this .data = data;
- this .flag = flag;
- }
- public String toString()
- {
- return data + flag;
- }
- //根据data实例变量来决定两个DataWrap的大小
- public int compareTo(DataWrap dw)
- {
- return this .data > dw.data ? 1
- : (this .data == dw.data ? 0 : - 1 );
- }
- }
- public class InsertSort
- {
- public static void insertSort(DataWrap[] data)
- {
- System.out.println("直接插入排序\n开始排序:\n" );
- int arrayLength = data.length;
- for ( int i = 1 ; i < arrayLength ; i++ )
- {
- //当整体后移时,保证data[i]的值不会丢失
- DataWrap tmp = data[i];
- //i索引处的值已经比前面所有值都大,表明已经有序,无需插入
- //(i-1索引之前的数据已经有序的,i-1索引处元素的值就是最大值)
- if (data[i].compareTo(data[i - 1 ]) < 0 )
- {
- int j = i - 1 ;
- //整体后移一格
- for ( ; j >= 0 && data[j].compareTo(tmp) > 0 ; j--)
- {
- data[j + 1 ] = data[j];
- }
- //最后将tmp的值插入合适位置
- data[j + 1 ] = tmp;
- }
- System.out.println(java.util.Arrays.toString(data));
- }
- }
- public static void main(String[] args)
- {
- DataWrap[] data = {
- new DataWrap( 9 , "" ),
- new DataWrap(- 16 , "" ),
- new DataWrap( 21 , "*" ),
- new DataWrap( 23 , "" ),
- new DataWrap(- 30 , "" ),
- new DataWrap(- 49 , "" ),
- new DataWrap( 21 , "" ),
- new DataWrap( 30 , "*" ),
- new DataWrap( 30 , "" )
- };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- insertSort(data);
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
折半插入排序
- import java.util.*;
- //定义一个数据包装类
- class DataWrap implements Comparable<DataWrap>
- {
- int data;
- String flag;
- public DataWrap( int data, String flag)
- {
- this .data = data;
- this .flag = flag;
- }
- public String toString()
- {
- return data + flag;
- }
- //根据data实例变量来决定两个DataWrap的大小
- public int compareTo(DataWrap dw)
- {
- return this .data > dw.data ? 1
- : (this .data == dw.data ? 0 : - 1 );
- }
- }
- public class BinaryInsertSort
- {
- public static void binaryInsertSort(DataWrap[] data)
- {
- System.out.println("开始排序:\n" );
- int arrayLength = data.length;
- for ( int i = 1 ; i < arrayLength ; i++)
- {
- //当整体后移时,保证data[i]的值不会丢失
- DataWrap tmp = data[i];
- int low = 0 ;
- int high = i - 1 ;
- while (low <= high)
- {
- //找出low、high中间的索引
- int mid = (low + high) / 2 ;
- //如果tmp值大于low、high中间元素的值
- if (tmp.compareTo(data[mid]) > 0 )
- {
- //限制在索引大于mid的那一半中搜索
- low = mid + 1 ;
- }
- else
- {
- //限制在索引小于mid的那一半中搜索
- high = mid - 1 ;
- }
- }
- //将low到i处的所有元素向后整体移一位
- for ( int j = i ; j > low ; j--)
- {
- data[j] = data[j - 1 ];
- }
- //最后将tmp的值插入合适位置
- data[low] = tmp;
- System.out.println(java.util.Arrays.toString(data));
- }
- }
- public static void main(String[] args)
- {
- DataWrap[] data = {
- new DataWrap( 9 , "" ),
- new DataWrap(- 16 , "" ),
- new DataWrap( 21 , "*" ),
- new DataWrap( 23 , "" ),
- new DataWrap(- 30 , "" ),
- new DataWrap(- 49 , "" ),
- new DataWrap( 21 , "" ),
- new DataWrap( 30 , "*" ),
- new DataWrap( 30 , "" )
- };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- binaryInsertSort(data);
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
Shell排序
在进行排序时的数据项之间的间隔被称为增量,习惯上用h 表示。 h 序列从 1 开始,通过 h=3*h+1 计算产生(其实直接插入排序是 Shell 排序的一种特例:直接使用增量为 1 的 Shell
排序。)
- import java.util.*;
- //定义一个数据包装类
- class DataWrap implements Comparable<DataWrap>
- {
- int data;
- String flag;
- public DataWrap( int data, String flag)
- {
- this .data = data;
- this .flag = flag;
- }
- public String toString()
- {
- return data + flag;
- }
- //根据data实例变量来决定两个DataWrap的大小
- public int compareTo(DataWrap dw)
- {
- return this .data > dw.data ? 1
- : (this .data == dw.data ? 0 : - 1 );
- }
- }
- public class ShellSort
- {
- public static void shellSort(DataWrap[] data)
- {
- System.out.println("Shell\n开始排序:" );
- int arrayLength = data.length;
- //h变量保存可变增量
- int h = 1 ;
- //按h * 3 + 1得到增量序列的最大值
- while (h <= arrayLength / 3 )
- {
- h = h * 3 + 1 ;
- }
- while (h > 0 )
- {
- System.out.println("===h的值:" + h + "===" );
- for ( int i = h ; i < arrayLength ; i++ )
- {
- //当整体后移时,保证data[i]的值不会丢失
- DataWrap tmp = data[i];
- //i索引处的值已经比前面所有值都大,表明已经有序,无需插入
- //(i-1索引之前的数据已经有序的,i-1索引处元素的值就是最大值)
- if (data[i].compareTo(data[i - h]) < 0 )
- {
- int j = i - h;
- //整体后移h格
- for ( ; j >= 0 && data[j].compareTo(tmp) > 0 ; j-=h)
- {
- data[j + h] = data[j];
- }
- //最后将tmp的值插入合适位置
- data[j + h] = tmp;
- }
- System.out.println(java.util.Arrays.toString(data));
- }
- h = (h - 1 ) / 3 ;
- }
- }
- public static void main(String[] args)
- {
- DataWrap[] data = {
- new DataWrap( 9 , "" ),
- new DataWrap(- 16 , "" ),
- new DataWrap( 21 , "*" ),
- new DataWrap( 23 , "" ),
- new DataWrap(- 30 , "" ),
- new DataWrap(- 49 , "" ),
- new DataWrap( 21 , "" ),
- new DataWrap( 30 , "*" ),
- new DataWrap( 30 , "" ),
- };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- shellSort(data);
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
- //时间复杂度:
- //空间复杂度:1
- //稳定性:稳定
归并排序
他是将两个有序的数据序列合并成一个新的有序序列。
- class DataWrap implements Comparable<DataWrap>
- {
- int data;
- String flag;
- public DataWrap( int data, String flag)
- {
- this .data = data;
- this .flag = flag;
- }
- public String toString()
- {
- return data + flag;
- }
- //根据data实例变量来决定两个DataWrap的大小
- public int compareTo(DataWrap dw)
- {
- return this .data > dw.data ? 1
- : (this .data == dw.data ? 0 : - 1 );
- }
- }
- public class MergeSort
- {
- //利用归并排序算法对数组data进行排序
- public static void mergeSort(DataWrap[] data)
- {
- //归并排序
- sort(data , 0 , data.length - 1 );
- }
- /**
- * 将索引从left到right范围的数组元素进行归并排序
- * @param data 待排序的数组
- * @param left 待排序的数组的第一个元素索引
- * @param right 待排序的数组的最后一个元素的索引
- */
- private static void sort(DataWrap[] data
- , int left, int right)
- {
- if (left < right)
- {
- //找出中间索引
- int center = (left + right) / 2 ;
- //对左边数组进行递归
- sort(data, left, center);
- //对右边数组进行递归
- sort(data, center + 1 , right);
- //合并
- merge(data, left, center, right);
- }
- }
- /**
- * 将两个数组进行归并,归并前两个数组已经有序,归并后依然有序。
- * @param data 数组对象
- * @param left 左数组的第一个元素的索引
- * @param center 左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
- * @param right 右数组的最后一个元素的索引
- */
- private static void merge(DataWrap[] data
- , int left, int center, int right)
- {
- //定义一个与待排序序列长度相同的临时数组
- DataWrap[] tmpArr = new DataWrap[data.length];
- int mid = center + 1 ;
- //third记录中间数组的索引
- int third = left;
- int tmp = left;
- while (left <= center && mid <= right)
- {
- //从两个数组中取出小的放入中间数组
- if (data[left].compareTo(data[mid]) <= 0 )
- {
- tmpArr[third++] = data[left++];
- }
- else
- {
- tmpArr[third++] = data[mid++];
- }
- }
- //剩余部分依次放入中间数组
- while (mid <= right)
- {
- tmpArr[third++] = data[mid++];
- }
- while (left <= center)
- {
- tmpArr[third++] = data[left++];
- }
- //将中间数组中的内容复制拷回原数组
- //(原left~right范围的内容复制回原数组)
- while (tmp <= right)
- {
- data[tmp] = tmpArr[tmp++];
- }
- }
- public static void main(String[] args)
- {
- DataWrap[] data = {
- new DataWrap( 9 , "" ),
- new DataWrap(- 16 , "" ),
- new DataWrap( 21 , "*" ),
- new DataWrap( 23 , "" ),
- new DataWrap(- 30 , "" ),
- new DataWrap(- 49 , "" ),
- new DataWrap( 21 , "" ),
- new DataWrap( 30 , "*" ),
- new DataWrap( 30 , "" )
- };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- mergeSort(data);
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
- //时间复杂度:
- //空间复杂度:
- //稳定性:稳定
桶式排序的特征:
待排序列的所有值处于一个可枚举范围内;
待排序列所在的这个可枚举范围不应该太大,否则排序开销太大。
- import java.util.Arrays;
- class DataWrap implements Comparable<DataWrap>
- {
- int data;
- String flag;
- public DataWrap( int data, String flag)
- {
- this .data = data;
- this .flag = flag;
- }
- public String toString()
- {
- return data + flag;
- }
- //根据data实例变量来决定两个DataWrap的大小
- public int compareTo(DataWrap dw)
- {
- return this .data > dw.data ? 1
- : (this .data == dw.data ? 0 : - 1 );
- }
- }
- public class BucketSort
- {
- public static void bucketSort(DataWrap[] data
- , int min , int max)
- {
- System.out.println("开始排序:" );
- //arrayLength记录待排序数组的长度
- int arrayLength = data.length;
- DataWrap[] tmp = new DataWrap[arrayLength];
- //buckets数组相当于定义了max - min个桶,
- //buckets数组用于记录待排序元素的信息
- int [] buckets = new int [max - min];
- //计算每个元素在序列出现的次数
- for ( int i = 0 ; i < arrayLength ; i++)
- {
- //buckets数组记录了DataWrap出现的次数
- buckets[data[i].data - min]++;
- }
- System.out.println( Arrays.toString(buckets));
- //计算“落入”各桶内的元素在有序序列中的位置
- for ( int i = 1 ; i < max - min; i++)
- {
- //前一个bucket的值 + 当前bucket的值 -> 当前bucket新的值
- buckets[i] = buckets[i] + buckets[i - 1 ];
- }
- //循环结束后,buckets数组元素记录了“落入”前面所有桶和
- //“落入”当前bucket中元素的总数,
- //也就说:buckets数组元素的值代表了“落入”当前桶的元素在有序序列中的位置
- System.out.println( Arrays.toString(buckets));
- //将data数组中数据完全复制到tmp数组中缓存起来。
- System.arraycopy(data, 0 , tmp, 0 , arrayLength);
- //根据buckets数组中的信息将待排序列的各元素放入相应的位置。
- for ( int k = arrayLength - 1 ; k >= 0 ; k--) //从高位开始可以保证排序的稳定性
- {
- data[--buckets[tmp[k].data - min]] = tmp[k];
- }
- }
- public static void main(String[] args)
- {
- DataWrap[] data = {
- new DataWrap( 9 , "" ),
- new DataWrap( 5 , "" ),
- new DataWrap(- 1 , "" ),
- new DataWrap( 8 , "" ),
- new DataWrap( 5 , "*" ),
- new DataWrap( 7 , "" ),
- new DataWrap( 3 , "" ),
- new DataWrap(- 3 , "" ),
- new DataWrap( 1 , "" ),
- new DataWrap( 3 , "*" )
- };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- bucketSort(data , -3 , 10 );
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
- //时间复杂度:小
- //空间复杂度:大
- //稳定性:稳定
基数排序必须依赖于另外的排序方法。基数排序的总体思想就是将待排序数据拆分成多个关键字进行排序,也就是说,基数排序的实质是多关键字排序。
多关键字排序解决方案:
最高位优先法MSD ;
最低位优先法LSD 。
基数排序对任一子关键字排序时必须借助于另外一个排序方法,而且这种排序方法必须是稳定的,一般用通式排序。
- import java.util.Arrays;
- public class MultiKeyRadixSort
- {
- /**
- * @param data 待排序的数组
- * @param radix 指定关键字拆分的进制。如radix=10,表明按10进制拆分
- * @param d 指定将关键字拆分成几个子关键字
- */
- public static void radixSort( int [] data, int radix, int d)
- {
- System.out.println("开始排序:" );
- int arrayLength = data.length;
- //需要一个临时数组
- int [] tmp = new int [arrayLength];
- //buckets数组是桶式排序必须buckets数组
- int [] buckets = new int [radix];
- //依次从最高位的子关键字对待排数据进行排序
- //下面循环中rate用于保存当前计算的位(比如十位时rate=10)
- for ( int i = 0 , rate = 1 ; i < d ; i++)
- {
- //重置count数组,开始统计第二个关键字
- Arrays.fill(buckets, 0 );
- //将data数组的元素复制到temporary数组中进行缓存
- System.arraycopy(data, 0 , tmp, 0 , arrayLength);
- //计算每个待排序数据的子关键字
- for ( int j = 0 ; j < arrayLength ; j++)
- {
- //计算数据指定位上的子关键字
- int subKey = (tmp[j] / rate) % radix;
- buckets[subKey]++;
- }
- for ( int j = 1 ; j < radix ; j++)
- {
- buckets[j] = buckets[j] + buckets[j-1 ];
- }
- //按子关键字对指定数据进行排序
- for ( int m = arrayLength - 1 ; m >= 0 ; m--)
- {
- int subKey = (tmp[m] / rate) % radix;
- data[--buckets[subKey]] = tmp[m];
- }
- System.out.println("对" + rate + "位上子关键字排序:"
- + java.util.Arrays.toString(data));
- rate *= radix;
- }
- }
- public static void main(String[] args)
- {
- int [] data = { 1100 , 192 , 221 , 12 , 13 };
- System.out.println("排序之前:\n"
- + java.util.Arrays.toString(data));
- radixSort(data , 10 , 4 );
- System.out.println("排序之后:\n"
- + java.util.Arrays.toString(data));
- }
- }
相关推荐
LeetCode 问题 33 是一个关于在旋转排序数组中搜索一个给定目标值的问题。如果目标值存在返回它的索引,否则返回 -1。数组可能在某个未知的轴心上进行了旋转(例如 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2])。你...
5.射向法判断点是否在多边形内部 6.判断点是否在线段上 7.判断两线段是否相交 8.判断线段与直线是否相交 9.点到线段最短距离 10.求两直线的交点 11.判断一个封闭图形是凹集还是凸集 12.Graham扫描法寻找凸包 13.求两...
计算机专业所需,C语言编写,富含例题一、线性表 (一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储结构 2.... 3....二、栈、队列和数组 (一)栈和队列的基本概念 ...(十一)内部排序算法的应用
元组可以按字典顺序排序并默认连接。 安装 将文件tuple.lua复制到 LUA_PATH。 用 Lua-Tuple 允许在 Lua 中声明 in-mutable 和 interned tuples。 由于内部化,元组的创建是一项耗时的操作,但是,由于这一点,它们...
基于排序选择模型,分别建立了基于排序Probit和排序Logil的公共交通内部方式转移价格阈值模型,并对模型进行局部效应分析.结果表明:性别、职业、收入、公交出行时间、公交出行费用及地铁与公交出行时间比对公共交通...
Date类 自动拆箱和自动装箱 Arrays 类和接口的关系 内部类 成员内部类 局部内部类 匿名内部类 抽象类 接口 多态 封装 类和对象 方法 StringBuilder类 String类 static for循环 final 权限修饰符 跳转控制语句 while...
数组 一维数组、数组参数、数组返回值、数组增删、扩容、排序、二维数组 chp6.面向对象 类和对象、实例变量、构造方法、方法重载、引用的概念、this关键字 chp7.面向对象三大特性 封装、继承、多态、对象创建过程、...
10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换一选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 顺序文件 ...
10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换一选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 ...
允许在项目周围和内部选择文本 处理不同大小的元素 支持在页面上任何位置放置元素,找到最接近的可用放置区域 处理拖放区的可见性变化 可选的拖动手柄 支持多个和嵌套的可排序容器 每个容器可配置的放置区。 调度...
软件说明: 编写语言:JAVA 运行环境:XP 或 WIN7, JRE1.6 含以及以上版本 作为一个初级程序猿来说:最苦恼的莫过于“兴冲冲得搞到了一批感兴趣的代码”,结果...“各种内部排序代码实现.rar”文件样本,供转换参考;
文中详细介绍并分析了归并排序算法的优缺点,针对归并算法的强制把数据划分两份进行了改进,提出按照数据本身具有的规律进行智能归并排序划分的方法。该方法将局部有序的记录块作为一组,避免对已经有序的数据划分再...
10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换一选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 顺序文件 ...
10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换一选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 顺序文件 ...
9. 内部排序 直接插入排序(A) 折半插入排序(A,P) 希尔排序(A) 起泡排序(A) 快速排序(A,P,O) 简单选择排序(P,A,O) 堆的概念,调整成堆(A),堆排序(A,O) 归并排序(A,O) 链式基数排序(A,O)...
10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 顺序文件...
10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换一选择排序 11.5 最佳归并树 第12章 文件 12.1 有关文件的基本概念 12.2 顺序文件 ...
Les02 : 过滤和排序数据[where / order by] Les03 : 单行函数[字符/数值/日期/转换/通用] Les04 : 多表查询 Les05 : 分组函数 Les06 : 子查询 Les07 : iSQL*Plus Les08 : 处理数据[DML:UPDATE/INSERT INTO/DELETE ...
Java 视频教程目录: day01、Java 语言发展史_JDK的安装_HelloWorld程序的编写_关键字_标识符_基本数据类型。 day02、Java 数据类型转换_...day11:Java final 关键字_内部类_成员内部类_局部内部类_匿名内部类。