排序算法总结

归并排序+快速排序

1. 归并排序

时间复杂度O(nlogn)和序列初始顺序无关

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
class MergeSort {
public int[] sort(int[] num) {
int[] arr = Arrays.copyOf(num, num.length);
if (arr.length <= 1) return arr;
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
int[] ansLeft= sort(left);
int[] ansRight= sort(right);
int [] ans=merge(ansLeft,ansRight);
return ans;
}
public int[] merge(int[] left, int[] right){
int[] result = new int[left.length+right.length];
int i=0,l=0,r=0;
while(l<left.length&&r<right.length){
if(left[l]<right[r]){
result[i++]=left[l];
l++;
}
else{
result[i++]=right[r];
r++;
}
}
for(int j=l;j<left.length;j++) result[i++]=left[j];
for(int j=r;j<right.length;j++) result[j++]=right[j];
return result;
}
}

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
class QuickSort  {
public int[] sort(int[] sourceArray) {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

return quickSort(arr, 0, arr.length - 1);
}

private int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}

private int partition(int[] arr, int left, int right) {
// 设定基准值(pivot)
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

}
Author

Pemp

Posted on

2022-02-25

Updated on

2022-03-10

Licensed under

Comments