排序算法

以下排序算法均按升序处理。

1.冒泡排序

算法原理:依次比较两个数的大小,如果左边的数大于右边的数,就交换两者的位置,当第一轮交换结束后,最后一个数肯定是整个数组中最大的那个数,因此下一轮比较的时候这个数就不需要比较了。

优化:按照上面的写有一个弊端,当数组初始状态就是部分或者完全升序,还是需要全部比较,这耗费很多时间,因此可以标记哪个位置以后是完全有序,就比较这个位置之前的位置就可以了。

冒泡排序是一个稳定的算法,是因为如果遇到相同的数,排序后不会改变相同的数它们彼此的相对位置。

时间复杂度:O(n²)

空间复杂度:O(n)

代码:

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
public class BubbleSort {
public static void sort(int[] nums){
//end表示将要排序的数的最后一个数的位置,end后面的不用排序
for (int end = nums.length - 1; end > 0; end--) {
int index = 0;
for (int i = 1; i <= end; i++) {
if(nums[i] < nums[i - 1]){
int temp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = temp;
//如果一直进不了这里面,说明i后面都是升序了,所以index后面都是升序
index = i;
}
}
end = index;
}
}

public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
BubbleSort.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}

2.选择排序

算法原理:先将所有数进行比较,找出最大的那个数,然后让这个数与最后一个元素交换位置,这时最大的数就在最后面了,接着缩小范围再进行选择比较。

选择排序也是一个稳定的算法。

时间复杂度:O(n²)

空间复杂度:O(1)

代码实现:

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
public class SelectionSort {
public static void sort(int[] nums){
for (int end = nums.length - 1; end > 0; end--) {
int max = 0;//假设最大值是索引为0的数
for (int i = 1; i <= end; i++) {
//这里的等号就是为了维护算法的稳定性
if(nums[max] <= nums[i]){
max = i;
}
}
int temp = nums[max];
nums[max] = nums[end];
nums[end] = temp;
}

}

public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
SelectionSort.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}

3.堆排序

堆排序可以认为是对选择排序的一种优化。

时间复杂度:O(nlogn)

空间复杂度:O(1)

堆排序

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
52
53
public class HeapSort {
//默认是大顶堆
private int heapSize;
private int[] nums;
public void sort(int[] nums){
this.nums = nums;
heapSize = nums.length;
//从第一个非叶子节点开始,到索引为0的节点
for(int i = (heapSize >> 1) - 1; i >= 0; i--){
siftDown(i);
}

while(heapSize > 1){
int top = nums[0];
nums[0] = nums[heapSize - 1];
nums[heapSize - 1] = top;//现在最大的数在末尾
heapSize--;
siftDown(0);
}
}

private void siftDown(int index){
int element = nums[index];
int half = heapSize >> 1;

while(index < half){
int leftIndex = (index << 1) + 1;
int leftChild = nums[leftIndex];
int rightIndex = leftIndex + 1;
if(rightIndex < heapSize && nums[rightIndex] > leftChild){
leftIndex = rightIndex;
leftChild = nums[rightIndex];
}
if(element >= leftChild){
break;
}
//因为index的左孩子和右孩子已经是一个最大堆了,所以leftChild就是堆的最大值,直接让最大值作为index的堆顶
nums[index] = leftChild;
//由于不知道左孩子的子树的堆中有没有比nums[index]更大的,所以每次找到一个下沉的位置,如果它不是叶子结点,再进入循环看是否还有比它大的
index = leftIndex;
}
nums[index] = element;
}

public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
HeapSort heap = new HeapSort();
heap.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}

4.插入排序

算法思想:数组的前一部分是有序的,后一部分是无序的,将后面的无序的元素依次插入到前面有序的部分,并保证插入后前一部分仍然是有序的。

假设这个数组是[44,51,61,82,94,96,52,54,71,17,32,60,5]

第一种做法:将52与有序数组依次进行比较,52<96,交换,52<94,交换,…..这样的话假如数组的有序部分都大于52,需要将52交换很多次,最后换到第一个位置,这样效率很低。

第二种做法:我们将【交换】改为【挪动】,首先倒着来,依次比较52和她们的大小关系,然后找出那个小于52的索引前面的索引,就是52要插入的位置,然后将这个位置到52位置的所有元素向右挪动一个位置,然后直接将52赋值到这个索引处。如果有序数组是倒序,也需要比较很多次才能找到这个索引。

第三种做法:利用二分查找的原理,二分地找出第一个大于52的数的索引,然后将它们挪动,再将52赋值到这个索引处。

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
public class InsertSort {
private int[] nums;
public void sort(int[] nums){
this.nums = nums;
for (int i = 1; i < nums.length; i++) {
int index = search(i);
int element = nums[i];
for (int j = i; j > index; j--) {
nums[j] = nums[j - 1];
}
nums[index] = element;
}
}
//查找v在有序数组中待插入的位置,找到第一个比v大的元素
private int search(int index){
int begin = 0;
int end = index;
//[begin,end)
while(begin < end){
int mid = (begin + end) >> 1;
if(nums[index] < nums[mid]){
end = mid;
}else{
begin = mid + 1;
}
}
return begin;
}
public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
InsertSort insertSort = new InsertSort();
insertSort.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}

5.归并排序

算法思想:将一个大数组分为两个小数组,在递归地将这两个小数组分为4个小数组,一直递归,终止条件是每个数组都只有一个元素,每个数组一定是一个有序数组,因为只有一个元素肯定是有序的啦,然后两两合并,合并完的仍然是有序数组才可以,最终合并成一个有序数组。

时间复杂度:O(nlogn)

空间复杂度:O(n)

代码实现

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
public class MergeSort {
private int[] leftArray;
private int[] nums;
public void sort(int[] nums){
this.nums = nums;
leftArray = new int[nums.length >> 1];
sort(0,nums.length);
}

//[begin,end)
private void sort(int begin,int end){
if(end - begin < 2) return;
int mid = (begin + end) >> 1;
sort(begin,mid);
sort(mid,end);
merge(begin,mid,end);
}

private void merge(int begin, int mid, int end) {
int point = begin;
int right = mid;
for (int i = 0; i < mid - begin; i++) {
leftArray[i] = nums[begin + i];
}
int left = 0;
//如果左边先结束,就不用再挪动元素了
//如果右边先结束,需要将左边的全部挪动到右边
while (left < mid - begin){//左边不越界
if(right >= end || leftArray[left] <= nums[right]){
nums[point++] = leftArray[left++];
}else{
nums[point++] = nums[right++];
}
}
}

public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
MergeSort mergeSort = new MergeSort();
mergeSort.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}

6.快速排序

算法思想:先选择一个轴点元素,比轴点元素大的元素放在轴点元素的右边,比轴点元素小的元素放在它的左边,然后再将轴点元素两遍的序列递归进行这个步骤,逐渐将每个元素都变成轴点元素。所以递归终止条件就是每个元素都变成了轴点元素。这样所有元素都是有序了。

时间复杂度:最好 O(nlogn),最坏O(n²)

空间复杂度:O(n)

当轴点元素将数组均分或者差不多均分的时候时间复杂度最低,最差的情况是轴点元素一边没有元素,一边是所有元素。

代码实现:

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
52
53
54
55
56
public class FastSort {
private int[] nums;
public void sort(int[] nums){
this.nums = nums;
sort(0,nums.length);
}
private void sort(int begin,int end){
if(end - begin < 2) return;

int pointIndex = point(begin,end);
sort(begin,pointIndex);
sort(pointIndex,end);
}

//确定轴点元素
private int point(int begin, int end) {
//随机选择轴点元素,并将它放到begin位置
int index = begin + (int) (Math.random() * (end - begin));
int first = nums[begin];
nums[begin] = nums[index];
nums[index] = first;

int element = nums[begin];
end--;

while (begin < end){
while(begin < end){
if(nums[end] > element){
end--;
}else {//覆盖轴点元素,这个循环结束,开始从左往右遍历
nums[begin++] = nums[end];
break;
}
}
while(begin < end){
if(nums[begin] < element){
begin++;
}else{//覆盖轴点元素,这个循环结束,开始从右往左遍历
nums[end--] = nums[begin];
break;
}
}
}
nums[begin] = element;
return begin;
}

public static void main(String[] args) {
int[] nums = {5,8,7,4,6,5,3,9,8,10,0};
FastSort s = new FastSort();
s.sort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+"_");
}
}
}

这里有一个很巧妙的设计,因为当每次覆盖操作之后,都需要进行反方向的遍历,轮流进行,当遍历的元素不满足与轴点元素的大小关系时,就还是这个方向进行遍历。这里使用了两个while循环,只要一覆盖,就break,换方向,否则不换。

一些转换公式


排序算法
https://vickkkyz.fun/2022/03/24/计算机/LeetCoode/排序算法/
作者
Vickkkyz
发布于
2022年3月24日
许可协议