首页 / JAVA / Java中的七大排序(上)
Java中的七大排序(上)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java中的七大排序(上),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2466字,纯文字阅读大概需要4分钟。
内容图文
![Java中的七大排序(上)](/upload/InfoBanner/zyjiaocheng/695/daaf6c96c3c24a74ae2349c5ee8b9c68.jpg)
一般排序通常认为是升序。
稳定性:两个相等的数据若在排序前后的相对位置不发生改变,则称该算法是具备稳定性的算法。
一:插入排序
原理: 将数组分为有序区间和无序区间,每次用无需区间的
第一个数与有序区间进行比较。
时间复杂度:O(n*n),空间复杂度:O(1)
稳定性:稳定
代码如下:
public static void insertSort0(int[] array) {
for (int i = 1; i < array.length; i++) {
// 有序区间 [0, i)
// 无序区间 [i, array.length)
int key = array[i];
int j;
for (j = i - 1; j >= 0 && array[j] > key; j--) {
array[j + 1] = array[j];
}
array[j + 1] = key;
}
}
二:希尔排序
原理:分组插排,每分隔gap个大小从数组中取一个数,进而将数组分成了若干 个组,重复此操作,直到gap=1;
时间复杂度:O(n)~O(n*n),空间复杂度:O(1)
稳定性:不稳定
代码如下:
public static void shellSort(int[] array){
int gap=array.length;
while(true){
gap=(gap/3)+1;//or gap=gap/2
insertSortWithGap(array,gap);
if(gap==1){
break;
}
}
}
private static void inserSortWithGap(int[] array,int gap){
for(int i=gap;i<array.length;i++){
int key=array[i];
int j;
for(j=i-gap;j>=0&&array[j]>key;j-=gap){
array[j+gap]=array[j];
}
array[j+gap]=key;
}
}
三:选择排序
1.单向选择排序
原理:每次从无序区间选出最大(或者最小)的数存放在无序区间的最后(最 前),直到所有的待排序数据排序完。
时间复杂度:O(n^2),空间复杂度:O(1)
稳定性:不稳定
public static void selsctSort1(int[] array){
//每次选最小的放在无序区间的前面
for(int i=0;i<array.length-1;i++){//需要排序的次数
//有序:[0,i)
//无序:[i,array.length)
int minIndex=i;
for(int j=i+1;j<array.length;j++){
if(array[j]<array[minIndex]){
minIndex=j;
}
}
swap(array,mindex,i);
}
}
public static void selsctSort2(int[] array){
//每次选最大的放在无序区间的后面
for(int i=0;i<=array.length-1;i++){
//无序:[0,array.length-i)
//有序:[array.length-i,array.length)
int maxIndex=0;
for(int j=1;j<array.length-i;j++){
if(array[j]>array[max]){
max=j;
}
}
int t=array[max];
array[max]=array[array.length-i-1];
array[array.length-i-1]=t;
}
2.双向排序比较
原理:每一次从无序区间选出最小 + 最大的元素,存放在无序区间的最前和最后,直到全部待排序的数据元素排完 。
时间复杂度:O(n^2),空间复杂度:O(1)
稳定性:不稳定
代码如下:
public static void selectSort3(int[] array){
int low=0;
int high=array.length-1;
//[low,high]表示整个无序区间
while(low<=high){
int min=low;
int high=low;
for(int i=low+1;i<=max;i++){
if (array[i] < array[min]) {
min = i;
}
if (array[i] > array[max]) {
max = i;
}
swap(array, min, low);
if (max == low) {
max = min;
}
swap(array, max, high);
}
private void swap(int[] array, int i, int j) {
int t = array[i]; array[i] = array[j]; array[j] = t;
}
}
内容总结
以上是互联网集市为您收集整理的Java中的七大排序(上)全部内容,希望文章能够帮你解决Java中的七大排序(上)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。