- 浏览: 566279 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (267)
- 随笔 (4)
- Spring (13)
- Java (61)
- HTTP (3)
- Windows (1)
- CI(Continuous Integration) (3)
- Dozer (1)
- Apache (11)
- DB (7)
- Architecture (41)
- Design Patterns (11)
- Test (5)
- Agile (1)
- ORM (3)
- PMP (2)
- ESB (2)
- Maven (5)
- IDE (1)
- Camel (1)
- Webservice (3)
- MySQL (6)
- CentOS (14)
- Linux (19)
- BI (3)
- RPC (2)
- Cluster (9)
- NoSQL (7)
- Oracle (25)
- Loadbalance (7)
- Web (5)
- tomcat (1)
- freemarker (1)
- 制造 (0)
最新评论
-
panamera:
如果设置了连接需要密码,Dynamic Broker-Clus ...
ActiveMQ 集群配置 -
panamera:
请问你的最后一种模式Broker-C节点是不是应该也要修改持久 ...
ActiveMQ 集群配置 -
maosheng:
longshao_feng 写道楼主使用 文件共享 模式的ma ...
ActiveMQ 集群配置 -
longshao_feng:
楼主使用 文件共享 模式的master-slave,produ ...
ActiveMQ 集群配置 -
tanglanwen:
感触很深,必定谨记!
少走弯路的十条忠告
1. 选择排序
选择排序的基本思想是遍历数组的过程中,以 i 代表当前需要排序的序号,则需要在剩余的 [i…n-1] 中找出其中的最小值,然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程,所以人们形象地称之为选择排序。
举个实例来看看:
初始: [10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
i = 0: [0 32 1 9 5 7 12 10 4 3]
i = 1: [0 1 32 9 5 7 12 10 4 3]
i = 2: [0 1 3 9 5 7 12 10 4 32]
i = 3: [0 1 3 4 5 7 12 10 9 32]
i = 4: [0 1 3 4 5 7 12 10 9 32]
i = 5: [0 1 3 4 5 7 12 10 9 32]
i = 6: [0 1 3 4 5 7 9 10 12 32]
i = 7: [0 1 3 4 5 7 9 10 12 32]
i = 8: [0 1 3 4 5 7 9 10 12 32]
i = 9: [0 1 3 4 5 7 9 10 12 32]
由例子可以看出,选择排序随着排序的进行( i 逐渐增大),比较的次数会越来越少,但是不论数组初始是否有序,选择排序都会从 i 至数组末尾进行一次选择比较,所以给定长度的数组,选择排序的比较次数是固定的: 1 + 2 + 3 + …. + n = n * (n + 1) / 2 ,而交换的次数则跟初始数组的顺序有关,如果初始数组顺序为随机,则在最坏情况下,数组元素将会交换 n 次,最好的情况下则可能 0 次(数组本身即为有序)。
由此可以推出,选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) (选择排序只需要一个额外空间用于数组元素交换)。
实现代码:
/* 选择排序 ;lz每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。
*/
public static void doChooseSort(int[] src) {
int len = src.length;
int temp;
for (int i = 0; i < len; i++) {
temp = src[i];
int j;
int samllestLocation = i;// 最小数的下标
for (j = i + 1; j < len; j++) {
if (src[j] < temp) {
temp = src[j];// 取出最小值
samllestLocation = j;// 取出最小值所在下标
}
}
// 下面两行代码是将最小数换到最前面
src[samllestLocation] = src[i];
src[i] = temp;
printResult(i, src);
}
}
2. 插入排序
插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好序,本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,为元素 x “腾位置”,最后将 k 对应的元素值赋为 x ,插入排序也是根据排序的特性来命名的。
以下是一个实例,红色 标记的数字为插入的数字,被划掉的数字是未参与此次排序的元素,红色 标记的数字与被划掉数字之间的元素为逐个向后移动的元素,比如第二趟参与排序的元素为 [11, 31, 12] ,需要插入的元素为 12 ,但是 12 当前并没有处于正确的位置,于是我们需要依次与前面的元素 31 、 11 做比较,一边比较一边移动比较过的元素,直到找到第一个比 12 小的元素 11 时停止比较,此时 31 对应的索引 1 则是 12 需要插入的位置。
初始: [10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
第一趟: [10 32 1 9 5 7 12 0 4 3]
第二趟: [1 10 32 9 5 7 12 0 4 3]
第三趟: [1 9 10 32 5 7 12 0 4 3]
第四趟: [1 5 9 10 32 7 12 0 4 3]
第五趟: [1 5 7 9 10 32 12 0 4 3]
第六趟: [1 5 7 9 10 12 32 0 4 3]
第七趟: [0 1 5 7 9 10 12 32 4 3]
第八趟: [0 1 4 5 7 9 10 12 32 3]
第九趟: [0 1 3 4 5 7 9 10 12 32]
插入排序会优于选择排序,理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势,有效地减少一些比较的次数,当然这种优势得看数组的初始顺序如何,最坏的情况下(给定的数组恰好为倒序)插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ,这种极端情况下,插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法,插入效率与数组初始顺序息息相关。一般情况下,插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。
实现代码:
// 插入排序(WHILE循环实现)
public static void doInsertSort1(int[] src) {
int len = src.length;
for (int i = 1; i < len; i++) {
int temp = src[i];
int j = i;
while (src[j - 1] > temp) {
src[j] = src[j - 1];
j--;
if (j <= 0)
break;
}
src[j] = temp;
printResult(i, src);
}
}
// 插入排序(FOR循环实现)
// 插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕
public static void doInsertSort2(int[] src) {
int len = src.length;
for (int i = 1; i < len; i++) {
int j;
int temp = src[i];
for (j = i; j > 0; j--) {
if (src[j - 1] > temp) {
src[j] = src[j - 1];
} else
{
// 如果当前的数,不小前面的数,那就说明不小于前面所有的数,
// 因为前面已经是排好了序的,所以直接通出当前一轮的比较
break;
}
}
src[j] = temp;
printResult(i, src);
}
}
3. 冒泡排序
冒泡排序可以算是最经典的排序算法了,记得小弟上学时最先接触的也就是这个算法了,因为实现方法最简单,两层 for 循环,里层循环中判断相邻两个元素是否逆序,是的话将两个元素交换,外层循环一次,就能将数组中剩下的元素中最小的元素“浮”到最前面,所以称之为冒泡排序。
照例举个简单的实例吧:
初始状态: [10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
内层第一趟: [10 32 1 9 5 7 12 0 4 3]
内层第二趟: [10 1 32 9 5 7 12 0 4 3]
内层第三趟: [10 1 9 32 5 7 12 0 4 3]
内层第四趟: [10 1 9 5 32 7 12 0 4 3]
内层第五趟: [10 1 9 5 7 32 12 0 4 3]
内层第六趟: [10 1 9 5 7 12 32 0 4 3]
内层第七趟: [10 1 9 5 7 12 0 32 4 3]
内层第八趟: [10 1 9 5 7 12 0 4 32 3]
内层第九趟: [10 1 9 5 7 12 0 4 3 32]
…...
其实冒泡排序跟选择排序比较相像,比较次数一样,都为 n * (n + 1) / 2 ,但是冒泡排序在挑选最小值的过程中会进行额外的交换(冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换,与之对应的是选择排序,只会在内层循环比较结束之后根据情况决定是否进行交换),所以在我看来,选择排序属于冒泡排序的改进版。
实现代码:
/*
冒泡排序 依次比较相邻的两个数,将小数放在前面,大数放在后面。 即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。
然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后
*/
public static void doBubbleSort(int[] a) {
int temp;
boolean hasChange=true; //用来标记每轮遍历中是否发生了交换
//每轮遍历开始,将hasChange设置为false
for (int i = 0; i < a.length - 1 && hasChange; i++) { // -1是因为最后一个没必要再跟它本身比较;hasChange为false的时候可以避免无效循环
hasChange=false;
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
hasChange=true;
}
printResult(i, a);
}
}
}
// 打印方法
private static void printResult(int i, int[] a) {
System.out.print("排序中"+(i)+": ");
for (int j : a)
{// 和for (int i = 0; i < len; i++) 效果是一样的
System.out.print(j + " ");
}
System.out.println(" ");
}
4. 希尔排序
希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”,划分为若干个小的数组,以 gap 来划分,比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ,如果以 gap = 2 来划分,可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组(对应的,如 gap = 3 ,则划分的数组为: [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] )然后分别对划分出来的数组进行插入排序,待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤,直至 gap = 1 ,即对整个数组进行插入排序,此时的数组已经基本上快排好序了,所以需要移动的元素会很小很小,解决了插入排序在处理大规模数组时较多移动次数的问题。
具体实例请参照插入排序。
希尔排序是插入排序的改进版,在数据量大的时候对效率的提升帮助很大,数据量小的时候建议直接使用插入排序就好了。
排序前
[10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
排序后
排序中: 5 32 1 9 10 7 12 0 4
排序中: 5 7 1 9 10 32 12 0 4
排序中: 5 7 1 0 10 32 12 9 4
排序中: 4 7 1 0 5 32 12 9 10
排序中: 1 7 4 0 5 32 12 9 10
排序中: 1 0 4 7 5 32 12 9 10
排序中: 1 0 4 7 5 9 12 32 10
排序中: 1 0 4 7 5 9 10 32 12
排序中: 0 1 4 7 5 9 10 32 12
排序中: 0 1 4 5 7 9 10 32 12
排序中: 0 1 4 5 7 9 10 12 32
实现代码:
// shell排序
public static void ShellSort(int Index) {
int i, j, k; // 循环计数变量
int Temp; // 暂存变量
boolean Change; // 数据是否改变
int DataLength; // 分割集合的间隔长度
int Pointer; // 进行处理的位置
DataLength = (int) Index / 2; // 初始集合间隔长度
while (DataLength != 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = arr[j]; // 暂存Data[j]的值,待交换值时用
Pointer = j - DataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
while (Temp < arr[Pointer] && Pointer >= 0 && Pointer <= Index) {
arr[Pointer + DataLength] = arr[Pointer];
// 计算下一个欲进行处理的位置
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
// 与最后的数值交换
arr[Pointer + DataLength] = Temp;
if (Change) {
// 打印目前排序结果
System.out.print("排序中: ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", arr[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; // 计算下次分割的间隔长度
}
}
5. 归并排序
归并排序采用的是递归来实现,属于“分而治之”,将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序完毕之后再将排好序的两个数组“归并”到一起,归并排序最重要的也就是这个“归并”的过程,归并的过程中需要额外的跟需要归并的两个数组长度一致的空间,比如需要规定的数组分别为: [3, 6, 8, 11] 和 [1, 3, 12, 15] (虽然逻辑上被划为为两个数组,但实际上这些元素还是位于原来数组中的,只是通过一些 index 将其划分成两个数组,原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ,我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分)那么需要的额外数组的长度为 4 + 4 = 8 。归并的过程可以简要地概括为如下:
1) 将两个子数组中的元素复制到新数组 copiedArray 中,以前面提到的例子为例,则 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ;
2) 设置两个指针分别指向原子数组中对应的第一个元素,假定这两个指针取名为 leftIdx 和 rightIdx ,则 leftIdx = 0 (对应 copiedArray 中的第一个元素 [3] ), rightIdx = 4 (对应 copiedArray 中的第五个元素 [1] );
3) 比较 leftIdx 和 rightIdx 指向的数组元素值,选取其中较小的一个并将其值赋给原数组中对应的位置 i ,赋值完毕后分别对参与赋值的这两个索引做自增 1 操作,如果 leftIdx 或 rigthIdx 值已经达到对应数组的末尾,则余下只需要将剩下数组的元素按顺序 copy 到余下的位置即可。
下面给个归并的具体实例:
第一趟:
辅助数组 [21 , 28, 39 | 35, 38] (数组被拆分为左右两个子数组,以 | 分隔开)
[21 , , , , ] (第一次 21 与 35 比较 , 左边子数组胜出, leftIdx = 0 , i = 0 )
第二趟:
辅助数组 [21, 28 , 39 | 35, 38]
[21 , 28, , , ] (第二次 28 与 35 比较,左边子数组胜出, leftIdx = 1 , i = 1 )
第三趟: [21, 28, 39 | 35 , 38]
[21 , 28 , 35, , ] (第三次 39 与 35 比较,右边子数组胜出, rightIdx = 0 , i = 2 )
第四趟: [21, 28, 39 | 35, 38 ]
[21 , 28 , 35 , 38, ] (第四次 39 与 38 比较,右边子数组胜出, rightIdx = 1 , i = 3 )
第五趟: [21, 28, 39 | 35, 38]
[21 , 28 , 35 , 38 , 39] (第五次时右边子数组已复制完,无需比较 leftIdx = 2 , i = 4 )
以上便是一次归并的过程,我们可以将整个需要排序的数组做有限次拆分(每次一分为二)直到分为长度为 1 的小数组为止,长度为 1 时数组已经不用排序了。在这之后再逆序(由于采用递归)依次对这些数组进行归并操作,直到最后一次归并长度为 n / 2 的子数组,归并完成之后数组排序也完成。
归并排序需要的额外空间是所有排序中最多的,每次归并需要与参与归并的两个数组长度之和相同个元素(为了提供辅助数组)。则可以推断归并排序的空间复杂度为 1 + 2 + 4 + … + n = n * ( n + 2) / 4 (忽略了 n 的奇偶性的判断),时间复杂度比较难估,这里小弟也忘记是多少了(囧)。
实现代码:
public void mergeSort(int [] a,int start,int end){
if(start<end){//当子序列中只有一个元素时结束递归
int mid=(start+end)/2;//划分子序列
mergeSort(a, start, mid);//对左侧子序列进行递归排序
mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
merge(a, start, mid, end);//合并
}
}
public class MergeSort {
//两路归并算法,两个排好序的子序列合并为一个子序列
public void merge(int []a,int left,int mid,int right){
int []tmp=new int[a.length];//辅助数组
int p1=left,p2=mid+1,k=left;//p1、p2是检测指针,k是存放指针
while(p1<=mid && p2<=right){
if(a[p1]<=a[p2])
tmp[k++]=a[p1++];
else
tmp[k++]=a[p2++];
}
while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
while(p2<=right) tmp[k++]=a[p2++];//同上
//复制回原素组
for (int i = left; i <=right; i++)
a[i]=tmp[i];
}
@Test
public void test(){
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
mergeSort(a, 0, a.length-1);
System.out.println("排好序的数组:");
for (int e : a)
System.out.print(e+" ");
}
}
6. 快速排序
快速排序也是用归并方法实现的一个“分而治之”的排序算法,它的魅力之处在于它能在每次partition(排序算法的核心所在)都能为一个数组元素确定其排序最终正确位置(一次就定位准,下次循环就不考虑这个元素了)。
快速排序的partition操作按以下逻辑进行,假定本次排序的数组为arr:
1) 选择一个元素(为了简单起见,就选择本次partition的第一个元素,即arr[0])作为基准元素,接下来的步骤会为其确定排序完成后最终的位置;
2) 1) 接下来需要遍历[1…n-1]对应的数组元素以帮助找到arr[0]值(以v替代)对应的位置,定义i为当前访问数组的索引,lt为值小于v的最大索引,gt为值大于v的最小索引,那么在遍历过程中,如果发现i指向的值与v相等,则将i值加1,继续下一次比较;如果i指向的值比v小,则将i和lt对应的元素进行交换,然后分别将两个索引加1;如果i指向的值比v大,则将i与gt对应的元素进行交换,然后i自增,gt自减。循环遍历完成(i > gt时结束)之后可以保证[0…lt-1]对应的值都是比v小的,[lt..gt]之间的值都是与v相等的,[gt+1…n-1]对应的值都是比v大的。
3) 分别对[0…lt-1]和[gt+1…n-1]两个子数组进行排序,如此递归,直至子子子数组的长度为0。
下面举个partition的具体实例:
初始(i = 1, lt = 0, gt = 8):
[41, 59, 43, 26, 63, 30, 29, 26, 42](需要确定位置的为0th[41])
第一趟(i = 1, lt = 0, gt = 8):
[41, 42, 43, 26, 63, 30, 29, 26, 59](1st[59] > 41,1st[59]<->8th[42],gt--)
第二趟(i = 1, lt = 0, gt = 7):
[41, 26, 43, 26, 63, 30, 29, 42, 59](1st[42] > 41,1st[42]<->7th[26],gt--)
第三趟(i = 1, lt = 0, gt = 6):
[26, 41, 43, 26, 63, 30, 29, 42, 59](1st[26] < 41, 1st[26]<->0st[41],i++, lt++)
第四趟(i = 2, lt = 1, gt = 6):
[26, 41, 29, 26, 63, 30, 43, 42, 59](2nd[43] > 41,2nd[43]<->6th[29],gt--)
第五趟(i = 2, lt = 1, gt = 5):
[26, 29, 41, 26, 63, 30, 43, 42, 59](2nd[29] < 41, 2nd[29]<->1st[41],i++,lt++)
第六趟(i = 3, lt = 2, gt = 5):
[26, 29, 26, 41, 63, 30, 43, 42, 59](3rd[26] < 41,3rd[26]<->2nd[41],i++,lt++)
第七趟(i = 4, lt = 3, gt = 5):
[26, 29, 26, 41, 30, 63, 43, 42, 59] (4th[63] > 41,4th[63]<->5th[30],gt--)
第八趟(i = 4, lt = 3, gt = 4):
[26, 29, 26, 30, 41, 63, 43, 42, 59](4th[30] < 41,4th[30]<->3rd[41],i++,lt++)
可以看出,在一次partition之后,以41为分割线,41左侧皆为比它小的元素,41右侧皆为比它大或相等的元素(当然这个实例比较特殊,没有出现和41相等的元素)。快速排序顾名思义就是排序速度非常快,后面我会放在我机器上跑各个排序方法的时间对比图。值得一提的是JDK中在Arrays工具内中内置的sort方法就是接合插入排序和三路快速排序实现的,有兴趣的同学可以看看JDK的源码。
排序前
[10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
排序后
[3, 4, 1, 9, 5, 7, 0, 10, 12, 32]
[0, 1, 3, 9, 5, 7, 4, 10, 12, 32]
[0, 1, 3, 9, 5, 7, 4, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
实现代码:
/**
* 一次排序单元,完成此方法,key左边都比key小,key右边都比key大。
*
* @param array
* 排序数组
* @param low
* 排序起始位置
* @param high
* 排序结束位置
* @return 单元排序后的数组游标
*/
private static int sortUnit(int[] array, int low, int high) {
int key = array[low];
while (low < high) {
// 从后向前搜索比key小的值
while (array[high] >= key && high > low) {
--high;
}
// 比key小的放左边
array[low] = array[high];
// 从前向后搜索比key大的值,比key大的放右边
while (array[low] <= key && high > low) {
++low;
}
// 比key大的放右边
array[high] = array[low];
}
// 左边都比key小,右边都比key大。将key放在游标当前位置。此时low等于high
array[high] = key;
System.out.println(Arrays.toString(array));
return high;
}
//快速排序1
/**
*
* @param
* array 排序数组
* @param
* low 排序起始位置
* @param
* high 排序结束位置
*/
public static void sort(int[] array, int low, int high) {
if (low < high) {
// 完成一次单元排序
int index = sortUnit(array, low, high);
// 对左边单元进行排序
sort(array, low, index - 1);
// 对右边单元进行排序
sort(array, index + 1, high);
}
}
排序前
[10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
排序后
[0, 3, 1, 9, 5, 7, 4, 10, 12, 32]
[0, 3, 1, 9, 5, 7, 4, 10, 12, 32]
[0, 1, 3, 9, 5, 7, 4, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
实现代码:
// 快速排序2
/**
* @param a
* 排序数组
* @param low
* 排序起始位置
* @param high
* 排序结束位置
*/
public static void qSort(int[] a, int p, int r) {
if (p < r) {
int q = partition(a, p, r);
qSort(a, p, q - 1);
qSort(a, q + 1, r);
}
}
/**
*
* @param a
* 排序数组
* @param low
* 排序起始位置
* @param high
* 排序结束位置
* @return
*/
private static int partition(int[] a, int low, int high) {
int i = low, j = high + 1;
int x = a[low];
while (true) {
while (a[++i] < x && i < high); // 找到第一个比 x 大的
while (a[--j] > x); // 找到第一个比 x 小的
if (i >= j)
break;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
a[low] = a[j];
a[j] = x;
System.out.println(Arrays.toString(a));
return j;
}
选择排序的基本思想是遍历数组的过程中,以 i 代表当前需要排序的序号,则需要在剩余的 [i…n-1] 中找出其中的最小值,然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程,所以人们形象地称之为选择排序。
举个实例来看看:
初始: [10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
i = 0: [0 32 1 9 5 7 12 10 4 3]
i = 1: [0 1 32 9 5 7 12 10 4 3]
i = 2: [0 1 3 9 5 7 12 10 4 32]
i = 3: [0 1 3 4 5 7 12 10 9 32]
i = 4: [0 1 3 4 5 7 12 10 9 32]
i = 5: [0 1 3 4 5 7 12 10 9 32]
i = 6: [0 1 3 4 5 7 9 10 12 32]
i = 7: [0 1 3 4 5 7 9 10 12 32]
i = 8: [0 1 3 4 5 7 9 10 12 32]
i = 9: [0 1 3 4 5 7 9 10 12 32]
由例子可以看出,选择排序随着排序的进行( i 逐渐增大),比较的次数会越来越少,但是不论数组初始是否有序,选择排序都会从 i 至数组末尾进行一次选择比较,所以给定长度的数组,选择排序的比较次数是固定的: 1 + 2 + 3 + …. + n = n * (n + 1) / 2 ,而交换的次数则跟初始数组的顺序有关,如果初始数组顺序为随机,则在最坏情况下,数组元素将会交换 n 次,最好的情况下则可能 0 次(数组本身即为有序)。
由此可以推出,选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) (选择排序只需要一个额外空间用于数组元素交换)。
实现代码:
/* 选择排序 ;lz每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。
*/
public static void doChooseSort(int[] src) {
int len = src.length;
int temp;
for (int i = 0; i < len; i++) {
temp = src[i];
int j;
int samllestLocation = i;// 最小数的下标
for (j = i + 1; j < len; j++) {
if (src[j] < temp) {
temp = src[j];// 取出最小值
samllestLocation = j;// 取出最小值所在下标
}
}
// 下面两行代码是将最小数换到最前面
src[samllestLocation] = src[i];
src[i] = temp;
printResult(i, src);
}
}
2. 插入排序
插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好序,本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,为元素 x “腾位置”,最后将 k 对应的元素值赋为 x ,插入排序也是根据排序的特性来命名的。
以下是一个实例,红色 标记的数字为插入的数字,被划掉的数字是未参与此次排序的元素,红色 标记的数字与被划掉数字之间的元素为逐个向后移动的元素,比如第二趟参与排序的元素为 [11, 31, 12] ,需要插入的元素为 12 ,但是 12 当前并没有处于正确的位置,于是我们需要依次与前面的元素 31 、 11 做比较,一边比较一边移动比较过的元素,直到找到第一个比 12 小的元素 11 时停止比较,此时 31 对应的索引 1 则是 12 需要插入的位置。
初始: [10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
第一趟: [10 32 1 9 5 7 12 0 4 3]
第二趟: [1 10 32 9 5 7 12 0 4 3]
第三趟: [1 9 10 32 5 7 12 0 4 3]
第四趟: [1 5 9 10 32 7 12 0 4 3]
第五趟: [1 5 7 9 10 32 12 0 4 3]
第六趟: [1 5 7 9 10 12 32 0 4 3]
第七趟: [0 1 5 7 9 10 12 32 4 3]
第八趟: [0 1 4 5 7 9 10 12 32 3]
第九趟: [0 1 3 4 5 7 9 10 12 32]
插入排序会优于选择排序,理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势,有效地减少一些比较的次数,当然这种优势得看数组的初始顺序如何,最坏的情况下(给定的数组恰好为倒序)插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ,这种极端情况下,插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法,插入效率与数组初始顺序息息相关。一般情况下,插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。
实现代码:
// 插入排序(WHILE循环实现)
public static void doInsertSort1(int[] src) {
int len = src.length;
for (int i = 1; i < len; i++) {
int temp = src[i];
int j = i;
while (src[j - 1] > temp) {
src[j] = src[j - 1];
j--;
if (j <= 0)
break;
}
src[j] = temp;
printResult(i, src);
}
}
// 插入排序(FOR循环实现)
// 插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕
public static void doInsertSort2(int[] src) {
int len = src.length;
for (int i = 1; i < len; i++) {
int j;
int temp = src[i];
for (j = i; j > 0; j--) {
if (src[j - 1] > temp) {
src[j] = src[j - 1];
} else
{
// 如果当前的数,不小前面的数,那就说明不小于前面所有的数,
// 因为前面已经是排好了序的,所以直接通出当前一轮的比较
break;
}
}
src[j] = temp;
printResult(i, src);
}
}
3. 冒泡排序
冒泡排序可以算是最经典的排序算法了,记得小弟上学时最先接触的也就是这个算法了,因为实现方法最简单,两层 for 循环,里层循环中判断相邻两个元素是否逆序,是的话将两个元素交换,外层循环一次,就能将数组中剩下的元素中最小的元素“浮”到最前面,所以称之为冒泡排序。
照例举个简单的实例吧:
初始状态: [10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
内层第一趟: [10 32 1 9 5 7 12 0 4 3]
内层第二趟: [10 1 32 9 5 7 12 0 4 3]
内层第三趟: [10 1 9 32 5 7 12 0 4 3]
内层第四趟: [10 1 9 5 32 7 12 0 4 3]
内层第五趟: [10 1 9 5 7 32 12 0 4 3]
内层第六趟: [10 1 9 5 7 12 32 0 4 3]
内层第七趟: [10 1 9 5 7 12 0 32 4 3]
内层第八趟: [10 1 9 5 7 12 0 4 32 3]
内层第九趟: [10 1 9 5 7 12 0 4 3 32]
…...
其实冒泡排序跟选择排序比较相像,比较次数一样,都为 n * (n + 1) / 2 ,但是冒泡排序在挑选最小值的过程中会进行额外的交换(冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换,与之对应的是选择排序,只会在内层循环比较结束之后根据情况决定是否进行交换),所以在我看来,选择排序属于冒泡排序的改进版。
实现代码:
/*
冒泡排序 依次比较相邻的两个数,将小数放在前面,大数放在后面。 即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。
然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后
*/
public static void doBubbleSort(int[] a) {
int temp;
boolean hasChange=true; //用来标记每轮遍历中是否发生了交换
//每轮遍历开始,将hasChange设置为false
for (int i = 0; i < a.length - 1 && hasChange; i++) { // -1是因为最后一个没必要再跟它本身比较;hasChange为false的时候可以避免无效循环
hasChange=false;
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
hasChange=true;
}
printResult(i, a);
}
}
}
// 打印方法
private static void printResult(int i, int[] a) {
System.out.print("排序中"+(i)+": ");
for (int j : a)
{// 和for (int i = 0; i < len; i++) 效果是一样的
System.out.print(j + " ");
}
System.out.println(" ");
}
4. 希尔排序
希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”,划分为若干个小的数组,以 gap 来划分,比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ,如果以 gap = 2 来划分,可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组(对应的,如 gap = 3 ,则划分的数组为: [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] )然后分别对划分出来的数组进行插入排序,待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤,直至 gap = 1 ,即对整个数组进行插入排序,此时的数组已经基本上快排好序了,所以需要移动的元素会很小很小,解决了插入排序在处理大规模数组时较多移动次数的问题。
具体实例请参照插入排序。
希尔排序是插入排序的改进版,在数据量大的时候对效率的提升帮助很大,数据量小的时候建议直接使用插入排序就好了。
排序前
[10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
排序后
排序中: 5 32 1 9 10 7 12 0 4
排序中: 5 7 1 9 10 32 12 0 4
排序中: 5 7 1 0 10 32 12 9 4
排序中: 4 7 1 0 5 32 12 9 10
排序中: 1 7 4 0 5 32 12 9 10
排序中: 1 0 4 7 5 32 12 9 10
排序中: 1 0 4 7 5 9 12 32 10
排序中: 1 0 4 7 5 9 10 32 12
排序中: 0 1 4 7 5 9 10 32 12
排序中: 0 1 4 5 7 9 10 32 12
排序中: 0 1 4 5 7 9 10 12 32
实现代码:
// shell排序
public static void ShellSort(int Index) {
int i, j, k; // 循环计数变量
int Temp; // 暂存变量
boolean Change; // 数据是否改变
int DataLength; // 分割集合的间隔长度
int Pointer; // 进行处理的位置
DataLength = (int) Index / 2; // 初始集合间隔长度
while (DataLength != 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = arr[j]; // 暂存Data[j]的值,待交换值时用
Pointer = j - DataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
while (Temp < arr[Pointer] && Pointer >= 0 && Pointer <= Index) {
arr[Pointer + DataLength] = arr[Pointer];
// 计算下一个欲进行处理的位置
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
// 与最后的数值交换
arr[Pointer + DataLength] = Temp;
if (Change) {
// 打印目前排序结果
System.out.print("排序中: ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", arr[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; // 计算下次分割的间隔长度
}
}
5. 归并排序
归并排序采用的是递归来实现,属于“分而治之”,将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序完毕之后再将排好序的两个数组“归并”到一起,归并排序最重要的也就是这个“归并”的过程,归并的过程中需要额外的跟需要归并的两个数组长度一致的空间,比如需要规定的数组分别为: [3, 6, 8, 11] 和 [1, 3, 12, 15] (虽然逻辑上被划为为两个数组,但实际上这些元素还是位于原来数组中的,只是通过一些 index 将其划分成两个数组,原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ,我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分)那么需要的额外数组的长度为 4 + 4 = 8 。归并的过程可以简要地概括为如下:
1) 将两个子数组中的元素复制到新数组 copiedArray 中,以前面提到的例子为例,则 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ;
2) 设置两个指针分别指向原子数组中对应的第一个元素,假定这两个指针取名为 leftIdx 和 rightIdx ,则 leftIdx = 0 (对应 copiedArray 中的第一个元素 [3] ), rightIdx = 4 (对应 copiedArray 中的第五个元素 [1] );
3) 比较 leftIdx 和 rightIdx 指向的数组元素值,选取其中较小的一个并将其值赋给原数组中对应的位置 i ,赋值完毕后分别对参与赋值的这两个索引做自增 1 操作,如果 leftIdx 或 rigthIdx 值已经达到对应数组的末尾,则余下只需要将剩下数组的元素按顺序 copy 到余下的位置即可。
下面给个归并的具体实例:
第一趟:
辅助数组 [21 , 28, 39 | 35, 38] (数组被拆分为左右两个子数组,以 | 分隔开)
[21 , , , , ] (第一次 21 与 35 比较 , 左边子数组胜出, leftIdx = 0 , i = 0 )
第二趟:
辅助数组 [21, 28 , 39 | 35, 38]
[21 , 28, , , ] (第二次 28 与 35 比较,左边子数组胜出, leftIdx = 1 , i = 1 )
第三趟: [21, 28, 39 | 35 , 38]
[21 , 28 , 35, , ] (第三次 39 与 35 比较,右边子数组胜出, rightIdx = 0 , i = 2 )
第四趟: [21, 28, 39 | 35, 38 ]
[21 , 28 , 35 , 38, ] (第四次 39 与 38 比较,右边子数组胜出, rightIdx = 1 , i = 3 )
第五趟: [21, 28, 39 | 35, 38]
[21 , 28 , 35 , 38 , 39] (第五次时右边子数组已复制完,无需比较 leftIdx = 2 , i = 4 )
以上便是一次归并的过程,我们可以将整个需要排序的数组做有限次拆分(每次一分为二)直到分为长度为 1 的小数组为止,长度为 1 时数组已经不用排序了。在这之后再逆序(由于采用递归)依次对这些数组进行归并操作,直到最后一次归并长度为 n / 2 的子数组,归并完成之后数组排序也完成。
归并排序需要的额外空间是所有排序中最多的,每次归并需要与参与归并的两个数组长度之和相同个元素(为了提供辅助数组)。则可以推断归并排序的空间复杂度为 1 + 2 + 4 + … + n = n * ( n + 2) / 4 (忽略了 n 的奇偶性的判断),时间复杂度比较难估,这里小弟也忘记是多少了(囧)。
实现代码:
public void mergeSort(int [] a,int start,int end){
if(start<end){//当子序列中只有一个元素时结束递归
int mid=(start+end)/2;//划分子序列
mergeSort(a, start, mid);//对左侧子序列进行递归排序
mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
merge(a, start, mid, end);//合并
}
}
public class MergeSort {
//两路归并算法,两个排好序的子序列合并为一个子序列
public void merge(int []a,int left,int mid,int right){
int []tmp=new int[a.length];//辅助数组
int p1=left,p2=mid+1,k=left;//p1、p2是检测指针,k是存放指针
while(p1<=mid && p2<=right){
if(a[p1]<=a[p2])
tmp[k++]=a[p1++];
else
tmp[k++]=a[p2++];
}
while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
while(p2<=right) tmp[k++]=a[p2++];//同上
//复制回原素组
for (int i = left; i <=right; i++)
a[i]=tmp[i];
}
@Test
public void test(){
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
mergeSort(a, 0, a.length-1);
System.out.println("排好序的数组:");
for (int e : a)
System.out.print(e+" ");
}
}
6. 快速排序
快速排序也是用归并方法实现的一个“分而治之”的排序算法,它的魅力之处在于它能在每次partition(排序算法的核心所在)都能为一个数组元素确定其排序最终正确位置(一次就定位准,下次循环就不考虑这个元素了)。
快速排序的partition操作按以下逻辑进行,假定本次排序的数组为arr:
1) 选择一个元素(为了简单起见,就选择本次partition的第一个元素,即arr[0])作为基准元素,接下来的步骤会为其确定排序完成后最终的位置;
2) 1) 接下来需要遍历[1…n-1]对应的数组元素以帮助找到arr[0]值(以v替代)对应的位置,定义i为当前访问数组的索引,lt为值小于v的最大索引,gt为值大于v的最小索引,那么在遍历过程中,如果发现i指向的值与v相等,则将i值加1,继续下一次比较;如果i指向的值比v小,则将i和lt对应的元素进行交换,然后分别将两个索引加1;如果i指向的值比v大,则将i与gt对应的元素进行交换,然后i自增,gt自减。循环遍历完成(i > gt时结束)之后可以保证[0…lt-1]对应的值都是比v小的,[lt..gt]之间的值都是与v相等的,[gt+1…n-1]对应的值都是比v大的。
3) 分别对[0…lt-1]和[gt+1…n-1]两个子数组进行排序,如此递归,直至子子子数组的长度为0。
下面举个partition的具体实例:
初始(i = 1, lt = 0, gt = 8):
[41, 59, 43, 26, 63, 30, 29, 26, 42](需要确定位置的为0th[41])
第一趟(i = 1, lt = 0, gt = 8):
[41, 42, 43, 26, 63, 30, 29, 26, 59](1st[59] > 41,1st[59]<->8th[42],gt--)
第二趟(i = 1, lt = 0, gt = 7):
[41, 26, 43, 26, 63, 30, 29, 42, 59](1st[42] > 41,1st[42]<->7th[26],gt--)
第三趟(i = 1, lt = 0, gt = 6):
[26, 41, 43, 26, 63, 30, 29, 42, 59](1st[26] < 41, 1st[26]<->0st[41],i++, lt++)
第四趟(i = 2, lt = 1, gt = 6):
[26, 41, 29, 26, 63, 30, 43, 42, 59](2nd[43] > 41,2nd[43]<->6th[29],gt--)
第五趟(i = 2, lt = 1, gt = 5):
[26, 29, 41, 26, 63, 30, 43, 42, 59](2nd[29] < 41, 2nd[29]<->1st[41],i++,lt++)
第六趟(i = 3, lt = 2, gt = 5):
[26, 29, 26, 41, 63, 30, 43, 42, 59](3rd[26] < 41,3rd[26]<->2nd[41],i++,lt++)
第七趟(i = 4, lt = 3, gt = 5):
[26, 29, 26, 41, 30, 63, 43, 42, 59] (4th[63] > 41,4th[63]<->5th[30],gt--)
第八趟(i = 4, lt = 3, gt = 4):
[26, 29, 26, 30, 41, 63, 43, 42, 59](4th[30] < 41,4th[30]<->3rd[41],i++,lt++)
可以看出,在一次partition之后,以41为分割线,41左侧皆为比它小的元素,41右侧皆为比它大或相等的元素(当然这个实例比较特殊,没有出现和41相等的元素)。快速排序顾名思义就是排序速度非常快,后面我会放在我机器上跑各个排序方法的时间对比图。值得一提的是JDK中在Arrays工具内中内置的sort方法就是接合插入排序和三路快速排序实现的,有兴趣的同学可以看看JDK的源码。
排序前
[10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
排序后
[3, 4, 1, 9, 5, 7, 0, 10, 12, 32]
[0, 1, 3, 9, 5, 7, 4, 10, 12, 32]
[0, 1, 3, 9, 5, 7, 4, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
实现代码:
/**
* 一次排序单元,完成此方法,key左边都比key小,key右边都比key大。
*
* @param array
* 排序数组
* @param low
* 排序起始位置
* @param high
* 排序结束位置
* @return 单元排序后的数组游标
*/
private static int sortUnit(int[] array, int low, int high) {
int key = array[low];
while (low < high) {
// 从后向前搜索比key小的值
while (array[high] >= key && high > low) {
--high;
}
// 比key小的放左边
array[low] = array[high];
// 从前向后搜索比key大的值,比key大的放右边
while (array[low] <= key && high > low) {
++low;
}
// 比key大的放右边
array[high] = array[low];
}
// 左边都比key小,右边都比key大。将key放在游标当前位置。此时low等于high
array[high] = key;
System.out.println(Arrays.toString(array));
return high;
}
//快速排序1
/**
*
* @param
* array 排序数组
* @param
* low 排序起始位置
* @param
* high 排序结束位置
*/
public static void sort(int[] array, int low, int high) {
if (low < high) {
// 完成一次单元排序
int index = sortUnit(array, low, high);
// 对左边单元进行排序
sort(array, low, index - 1);
// 对右边单元进行排序
sort(array, index + 1, high);
}
}
排序前
[10, 32, 1, 9, 5, 7, 12, 0, 4, 3]
排序后
[0, 3, 1, 9, 5, 7, 4, 10, 12, 32]
[0, 3, 1, 9, 5, 7, 4, 10, 12, 32]
[0, 1, 3, 9, 5, 7, 4, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
[0, 1, 3, 4, 5, 7, 9, 10, 12, 32]
实现代码:
// 快速排序2
/**
* @param a
* 排序数组
* @param low
* 排序起始位置
* @param high
* 排序结束位置
*/
public static void qSort(int[] a, int p, int r) {
if (p < r) {
int q = partition(a, p, r);
qSort(a, p, q - 1);
qSort(a, q + 1, r);
}
}
/**
*
* @param a
* 排序数组
* @param low
* 排序起始位置
* @param high
* 排序结束位置
* @return
*/
private static int partition(int[] a, int low, int high) {
int i = low, j = high + 1;
int x = a[low];
while (true) {
while (a[++i] < x && i < high); // 找到第一个比 x 大的
while (a[--j] > x); // 找到第一个比 x 小的
if (i >= j)
break;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
a[low] = a[j];
a[j] = x;
System.out.println(Arrays.toString(a));
return j;
}
发表评论
-
java 类的加载 以及 ClassLoader
2020-04-16 09:43 454Class Loader 类加载器: 类加载器负责加载 ... -
高性能 IO 设计 Reactor 模式
2020-04-11 08:40 387传统的服务器设计是:一连接一处理线程,也就是我们常说的 BIO ... -
事务和一致性:从ACID到CAP再到BASE
2020-04-09 21:24 713先了解一下互联网 ... -
Stack 的实现原理深入剖析
2020-04-06 13:26 492Stack 介绍: Stack是栈。 ... -
Vector 的实现原理深入剖析
2020-04-06 13:17 366Vector介绍: Vector 是矢量队列,它是JDK1. ... -
JDK 分析工具
2020-04-05 17:30 369常用分析工具: jps:显示指定系统中所有的HotSpot虚 ... -
DDD 设计
2020-04-11 08:49 365概述: DDD将一个软件 ... -
二叉树的深度优先遍历和广度优先遍历
2020-03-10 09:33 599概述: 1、深度优先遍历(Depth-First-Sear ... -
Hashtable 的实现原理深入剖析
2020-02-18 20:59 538一、Hashtable的基本方法: 1、定义: HashT ... -
jdk 1.8 新特性
2020-02-17 13:43 3661、default关键字 ... -
Java IO 架构
2019-11-11 16:39 351主要两类: 磁盘I/O 网络I/O 基于字节 ... -
Java 数据结构与算法
2019-04-03 10:25 519程序=数据结构+算法 ... -
MVC架构、RPC架构、SOA架构、微服务架构区别
2018-12-11 08:47 2617一、MVC架构 ... -
Java语言异常(Exception)
2018-10-09 11:40 549异常,是Java中非常常用 ... -
Java并发问题--乐观锁与悲观锁以及乐观锁的一种实现方式-CAS
2018-08-17 09:47 1473首先介绍一些乐观锁与 ... -
Java I/O Reactor 模式
2017-05-12 17:29 690Java NIO 相关类图: ... -
Java 高性能编程注意事项
2016-11-17 09:55 6481. 尽量在合适的场合使用单例 使用单例可以减轻加载的负担, ... -
Netty 解析
2017-03-07 13:47 1221Linux网络IO模型: Linux ... -
分布式事务探讨
2016-09-07 16:20 544分布式事务: 分布式 ... -
2016年Java 面试题总结
2016-01-18 13:34 54794多线程、并发及线程的基础问题: 1)Java 中能创建 vo ...
相关推荐
### JAVA排序算法总结 在计算机科学领域,排序算法是数据处理和分析中极其重要的组成部分,尤其是在使用Java语言进行开发时。本文将针对常用的几种排序算法进行详细的总结与解析,包括它们的基本原理、时间复杂度、...
本文将对Java中的九种基本排序算法进行深入的总结和探讨,包括它们的工作原理、优缺点以及适用场景。 首先,我们来看堆排序(HeapSort)。堆排序是一种基于比较的排序算法,它利用了完全二叉树的特性,通过构建最大...
Java排序算法实现 Java排序算法实现 Java排序算法实现
【Java排序算法总结】 在计算机科学中,排序算法是用于对数据进行排列的算法,而Java作为一种广泛应用的编程语言,提供了多种实现排序的方案。以下是对几种常见的Java排序算法的详细解析: 一、冒泡排序 冒泡排序...
Java排序算法大全是一份专为Java开发者准备的学习资源,涵盖了各种经典的排序算法,旨在帮助初学者和有经验的程序员深入理解排序的原理和实现。排序是计算机科学中的基础且重要的概念,它在数据处理、数据库操作、...
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
冒泡排序和快速排序是两种基础但广泛使用的数据排序算法。冒泡排序由于其简单直观的特性,易于理解和实现,而快速排序则以其较高的效率在数据量较大时展现出优势。 首先,让我们来看冒泡排序算法。冒泡排序通过重复...
本文将详细探讨标题所提及的几种排序算法:合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合Java语言的实现进行解析。 1. **合并排序(Merge Sort)**: 合并排序是一种基于分治策略的排序算法...
Java作为广泛应用的编程语言,其对排序算法的支持使得开发者能够高效地处理大量数据。本篇文章将详细探讨Java中冒泡排序、选择排序、快速排序以及插入排序这四大基本排序算法,并结合代码和动画演示来帮助理解它们的...
排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际...
在Java编程语言中,排序算法是数据结构与算法学习中的重要组成部分。本实验通过生成大量随机数并写入文件,然后使用四种不同的排序算法进行排序,以比较它们的效率。以下是对这四种排序算法的详细解释: 1. **冒泡...
在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。排序算法是用来组织和优化数据结构的关键工具,它可以帮助我们快速查找、分析和处理大量数据。本篇将深入探讨Java中实现的几种...
【JAVA排序汇总】Java编程语言中,排序是数据处理中非常基础且重要的操作。本文将对几种经典的排序算法进行简要介绍和分析。 1. **插入排序**: 插入排序分为直接插入排序和折半插入排序。直接插入排序是将每个...
这个名为"Java各种排序算法代码.zip"的压缩包包含了一系列实现不同排序算法的Java源代码。排序算法是计算机科学中的基本概念,用于对一组数据进行排列。下面将详细讨论这些算法及其在Java中的实现。 1. 冒泡排序...
总结,堆排序是一种高效的排序算法,尤其在没有额外内存限制的情况下。尽管它不是稳定的排序算法,但其优秀的平均性能和较低的空间复杂度使其在实际应用中有着广泛的应用。理解堆排序的原理和实现,对于提升编程能力...
【Java排序算法详细整理】 在计算机科学中,排序算法是用于对一组数据进行排列的算法。在Java中,实现各种排序算法有助于理解数据结构和算法的原理,同时也能提高编程能力。以下是对Java中常见的几种排序算法的详细...
在编程领域,排序算法是计算机科学中的核心概念,尤其是在Java这样的高级编程语言中。Java提供了丰富的内置库函数,如Arrays.sort(),可以方便地对数组进行排序。然而,理解并掌握各种排序算法对于优化程序性能、...
在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。排序算法是用来组织和优化数据结构的关键工具,它可以帮助我们快速查找、分析和处理数据。本资源包含的是Java实现的各种常见排序...