选择排序
从0-（n-1）找出一个最小值放在0位置 1-（n-1）找出一个最小值放在1位置，以此类推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static void SelectionSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for(int minIndex, i = 0;i < arr.length - 1 ;i++){
minIndex = i;
for(int j = i+1;j < arr.length;j++){
if(arr[i]>arr[j]){
minIndex = j;
swap(arr,i,minIndex);
}
}
}
}
|
冒泡排序
两两比较，大的向后移，直至在数组末尾，每比较一轮下一轮比较次数减一
1
2
3
4
5
6
7
8
9
10
11
12
| public static void BubbleSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for(int end= arr.length - 1;end >0 ;end--){
for(int i=0;i<end;i++){
if(arr[i]>arr[i+1]){
swap(arr,i,i+1);
}
}
}
}
|
插入排序
认为第一个值为一个有序序列，从剩下的未排序序列中取出第一个元素，从有序序列末尾开始，依次与此元素比较，小则交换
1
2
3
4
5
6
7
8
9
10
| public static void InsertionSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for(int i = 1;i <arr.length;i++){
for(int j = i -1;j >=0 &&arr[j]>arr[j+1];j--){
swap(arr,j,j+1);
}
}
}
|
归并排序
算法步骤
- 将一个大数组持续对半拆分，直至剩下一个元素，此时天然有序
- 将左右两部分数组进行排序并放入一个辅助数组中
- 将辅助数组的元素拷贝回原数组
- 重复执行2和3
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public static void mergeSort(int l ,int r) {
if (l == r) {
return;
}
int mid = l + (r - l)/2;
mergeSort(l, mid);
mergeSort(mid + 1, r);
merge(l, mid, r);
}
public static void merge(int l,int mid,int r){
int a = l,b = mid+1 ,i = l;
while(a <= mid && b <= r){
help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
}
while (a <= mid){
help[i++] = arr[a++];
}
while (b <= r){
help[i++] = arr[b++];
}
for(int k = l;k <= r;k++){
arr[k] = help[k];
}
}
|
随机快速排序
算法步骤
- 随机出一个数组中的值，假定它为中间值，对其左右两侧进行分区，<x的放左边 ，=x的放中间，>x的放右边
- 左右两侧的做法与步骤一相同
代码实现
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 static void quickSort(int l ,int r){
if( l >= r){
return;
}
int mid = arr[l + (int)(Math.random() * (r - l + 1))];
partition(l,r,mid);
int left =first;
int right=last;
quickSort(l,left - 1);
quickSort(right + 1,r);
}
public static int first ,last;
public static void partition(int l ,int r ,int mid){
first = l;
last = r;
int i = l;
while(i <= last){
if(arr[i] < mid){
swap(first++,i++);
}else if(arr[i] > mid){
swap(last--,i);
}else {
i++;
}
}
}
public static void swap(int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
|
堆排序
- 首先建立一个大根堆（最大值在最顶部）
- 将最大值与数组最后一个元素交换，再将剩下的元素再构成一个大根堆
- 重复步骤2
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
45
46
47
48
49
50
51
|
public static void heapInsert(int i){
while (arr[i] > arr[(i - 1) / 2]) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
public static void heapify(int i ,int size){
int l = 2*i+1;
while(l < size) {
int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
best = arr[best] > arr[i] ? best : i;
if (best == i) {
break; int best = (l+1) < size && arr[l] > arr[l + 1] ? l : (l + 1);
best = arr[i] > arr[best] ? i : best;
}
swap(i, best);
i = best;
l = 2 * i + 1;
}
}
public static void heapSort1(){
for(int i = 0;i < n;i++){
heapInsert(i);
}
int size = n;
while(size > 1){
swap(0,--size);
heapify(0,size);
}
}
public static void heapSort2(){
for(int i = (n - 1)/2;i >= 0;i--){
heapify(i,n);
}
int size = n;
while(size > 1){
swap(0,--size);
heapify(0,size);
}
}
public static void swap(int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
|
让我不能理解的地方是以下两行代码
1
2
| int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
best = arr[best] > arr[i] ? best : i;
|
替换成接下来的代码无法通过测试
1
2
| break; int best = (l+1) < size && arr[l] > arr[l + 1] ? l : (l + 1);
best = arr[i] > arr[best] ? i : best;
|
基数排序
不基于比较的排序
- 找出数组中的最大值，得出其位数
- 从最低位开始，计算每一位数字小于等于其值的个数
- 按照当前位的数字大小进行排序
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
|
public static void sort(){
int min = arr[0];
for(int i = 0;i < n;i++){
min = Math.min(min,arr[i]);
}
int max = 0;
for(int i = 0;i < n;i++){
arr[i] -= min;
max = Math.max(max,arr[i]);
}
radisSort(bit(max));
for(int i = 0;i < n;i++){
arr[i] += min;
}
}
public static void radisSort(int bits){
for(int offset = 1 ;bits > 0 ;offset *= BASE ,bits--){
Arrays.fill(cnt, 0);
for(int i = 0;i < n ;i++){
cnt[(arr[i]/offset)%BASE]++;
}
for(int i = 1;i < BASE ;i++){
cnt[i] = cnt[i] + cnt[i-1];
}
for(int i = n -1 ;i >= 0;i--){
help[--cnt[(arr[i]/offset)%BASE]] = arr[i];
}
for(int i = 0;i < n ;i++){
arr[i] = help[i];
}
}
}
public static int bit (int number){
int ans = 0;
while(number > 0){
ans++;
number /= BASE;
}
return ans;
}
|
