算法：数组排序

发表于 | 分类于

概述

算法几乎在所有的面试中都会遇到，尤其是在笔试的时候，除了理论知识外，就是要求手写算法。今天尝试手写几个经典算法。

算法

已知数组arr[]，数组长度为len。

冒泡算法

1.示意图：

2.具体实现：

1
2
3
4
5
6
7
8
9
for(int i = 0;i < len-1; ++i){
	for(int j = 0;j < len-1-i; ++j){
		if(arr[j] > arr[j+1]){//交换双方位置
			int temp = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = temp;
		}
	}
}

可以看出是由两个for循环实现，逐个比较相邻两个元素的大小，所以时间复杂度为O(n^2);

插入排序

1.百科示意图：

2.具体实现：

1
2
3
4
5
6
7
8
int j;
for(int i = 1;i < len;++i){
	int temp = arr[i];
	for(j = i;j > 0 && temp < arr[j-1],--j){
		arr[j] = arr[j-1];
	}
	arr[j] = temp;
}

根据数组的特性，如果数组接近有序数组的话，插入排序的效率会很高。接近O(n)

选择排序

百科示意图：

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < len - 1; ++i) {
        int min = i;
        for (int j = i + 1; j < len; ++j) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
		int temp = arr[i];
		arr[i] = arr[min];
		arr[min] = temp;
    }

效率对比

在随机生成的50000个元素的数组后，分别用上述三个方式为其排序。用时结果如图：

图中可以明显看出，长度较大的数组中，三种排序方式最耗时的是冒泡排序法，效率最高的是插入排序法

总结

这里需要注意的是我这里使用的++i,而不是i++的形式。一开始我以为两者在for循环中的效果是一样的。但是后来发现，当数组长度较大的时候，在不影响逻辑的情况下，建议使用++i的形式。一开始我以为两者在for循环中的效果是一样的。但是后来发现，当数组长度较大的时候，在不影响逻辑的情况下，建议使用++i的形式
因为在Java中i++语句是需要一个临时变量取存储返回自增前的值，而++i不需要。这样就导致使用i++时系统需要先申请一段内存空间，然后将值赛如进去，最后不用了才去释放。