java排序算法

admin 2022年1月6日01:35:36评论57 views字数 5685阅读18分57秒阅读模式

冒泡排序法

详情可看此文章https://www.cnblogs.com/guoyaohua/p/8600214.html

算法总结:

算法分类:

0x1冒泡排序法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class BubbleSort {
public static void sort(int[] array) {
if(array.length==0) {
return ;
}
for(int i=0;i<array.length;i++) {
for(int j=0;j<array.length-i-1;j++) {
if(array[j+1]<array[j]) {
int temp=array[j+1];
array[j+1]=array[j];
array[j]=temp;
}
}
}
}
}

0x2选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Selection {
public static void sort(int[] nums) {
int N=nums.length;
for(int i=0;i<N;i++) {
int min=i;
for(int j=i+1;j<N;j++) {
if(nums[i]>nums[j]) {
min=j;

}
}
int temp=nums[i];
nums[i]=nums[min];
nums[min]=temp;

}

}
}

0x3插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Insertion {
public static void sort(int[] array) {
if(array.length==0) {
return ;
}
for(int i=0;i<array.length-1;i++) {
int current=array[i+1];
int preindex=i;
while(preindex>=0&amp;&current>array[preindex]) {
array[preindex+1]=array[preindex];
preindex--;

}
array[preindex]=current;
}

}

}

0x4希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Shell {
public static void sort(int[] array) {
int len=array.length;
int gap=len/2;
while(gap>0) {
for(int i=gap;i<len;i++) {
int temp=array[i];
int preindex=i-gap;
while(preindex>=0&&temp<array[preindex]) {
array[preindex+gap]=array[preindex];
preindex-=gap;
}
array[preindex+gap]=temp;

}
gap=gap/2;
}
}

}

0x5归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Merge {
public static int[] sort(int[] array) {
if(array.length<2) {
return array;
}
int mid=array.length/2;
int[] left=Arrays.copyOfRange(array, 0, mid);
int[] right=Arrays.copyOfRange(array, mid, array.length);
return merge(sort(left),sort(right));

}


public static int[] merge(int[] left,int[] right) {
int[] result=new int[left.length+right.length];
for(int index=0,i=0,j=0;index<result.length;index++) {
if(i>=left.length) {
result[index]=right[j++];
}else if(j>=right.length){
result[index]=left[i++];
}else if(left[i]>right[j]) {
result[index]=right[j++];

}else {
result[index]=left[i++];
}
}
return result;

}
}

0x6快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Quick {
public static int[] sort(int[] array,int start,int end) {
if(array.length<1||start<0||end>=array.length||start>end) return null;
int smallIndex=partition(array,start,end);
if(smallIndex>start)
sort(array,start,smallIndex-1);
if(smallIndex<end)
sort(array,smallIndex+1,end);
return array;

}
public static int partition(int[] array,int start ,int end) {
int pivot=(int)(start+Math.random()*(end-start+1));
int smallIndex=start-1;
swap(array,pivot,end);
for(int i=start;i<=end;i++) {
if(array[i]<=array[end]) {
smallIndex++;
if(i>smallIndex)
swap(array,i,smallIndex);
}
}
return smallIndex;

}
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

}

0x7堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Heap {
static int len;
public static int[] sort(int[] array) {
len=array.length;
if(len<1) return array;
//2.循环将堆首位(最大值)与末位交换,然后在重新调整最大堆
buildMaxHeap(array);
while(len>0) {
swap(array,0,len-1);
len--;
adjustHeap(array,0);
}

return array;

}
public static void buildMaxHeap(int[] array) {
//从最后一个非叶子节点开始向上构造最大堆
for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒,此处应该为 i = (len/2 - 1)
adjustHeap(array, i);
}
}
public static void adjustHeap(int[] array, int i) {
int maxIndex = i;
//如果有左子树,且左子树大于父节点,则将最大指针指向左子树
if (i * 2 < len && array[i * 2] > array[maxIndex])
maxIndex = i * 2;
//如果有右子树,且右子树大于父节点,则将最大指针指向右子树
if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
maxIndex = i * 2 + 1;
//如果父节点不是最大值,则将父节点与最大值交换,并且递归调整与父节点交换的位置。
if (maxIndex != i) {
swap(array, maxIndex, i);
adjustHeap(array, maxIndex);
}
}

public static void swap(int[] array, int i,int j) {
int temp=array[i];
array[i]=array[j];
array[j]=temp;

}
}

0x8计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Arrays;

public class Counting {
public static void sort(int[] array) {
if(array.length<1) {
return;
}

int min = array[0],max = array[0],bias;
for(int i=0;i<array.length;i++) {
if(min>array[i])
min=array[i];
if(max<array[i])
max=array[i];
}
bias=min;
int[] bucket=new int[max-min+1];
Arrays.fill(bucket, 0);
for(int i=0;i<array.length;i++) {
bucket[array[i]-bias]++;
}
int index=0,i=0;
while(index<array.length) {
if(bucket[i]!=0) {
array[index]=i+bias;
bucket[i]--;
index++;
}else {
i++;
}
}

}

}

0x9桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
if (array == null || array.size() < 2)
return array;
int max = array.get(0), min = array.get(0);
// 找到最大值最小值
for (int i = 0; i < array.size(); i++) {
if (array.get(i) > max)
max = array.get(i);
if (array.get(i) < min)
min = array.get(i);
}
int bucketCount = (max - min) / bucketSize + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
ArrayList<Integer> resultArr = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
bucketArr.add(new ArrayList<Integer>());
}
for (int i = 0; i < array.size(); i++) {
bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
}
for (int i = 0; i < bucketCount; i++) {
if (bucketSize == 1) { // 如果带排序数组中有重复数字时 感谢 @见风任然是风 朋友指出错误
for (int j = 0; j < bucketArr.get(i).size(); j++)
resultArr.add(bucketArr.get(i).get(j));
} else {
if (bucketCount == 1)
bucketSize--;
ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
for (int j = 0; j < temp.size(); j++)
resultArr.add(temp.get(j));
}
}
return resultArr;
}

0x10基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.ArrayList;

public class Radix {
public static void RadixSort(int[] array) {
if(array==null||array.length<2) return;
int max=array[0];
for(int i=0;i<array.length;i++) {
max=Math.max(max, array[i]);
}
int maxDigit=0;
while(max!=0) {
max/=10;
maxDigit++;
}
int mod=10,div=1;
ArrayList<ArrayList<Integer>> bucketList=new ArrayList<ArrayList<Integer>>();
for(int i=0;i<maxDigit;i++,mod*=10,div*=10) {
for(int j=0;j<array.length;j++) {
int num=(array[j]%mod)/div;
bucketList.get(num).add(array[j]);
}
}
int index=0;
for(int j=0;j<bucketList.size();j++) {
for(int k=0;k<bucketList.get(j).size();k++) {
array[index++]=bucketList.get(j).get(k);
}
bucketList.get(j).clear();
}
}

}

参考文章:
十大经典排序算法最强总结

FROM :blog.cfyqy.com | Author:cfyqy

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:35:36
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   java排序算法http://cn-sec.com/archives/721947.html

发表评论

匿名网友 填写信息