排序算法之插入排序和选择排序

发表于 | 分类于 ，

插入排序

排序思想

将排序序列分为两部分，前一部分是已排序的序列，后一部分为待排序序列。

每次从待排序序列中选择一个元素，依次比较其和已排序序列中的元素的大小，直到找到一个比它大的元素，并将其插入到这个元素前边。重复上步，直到待排序序列中没有元素了。

排序示例

对序列[3, 4, 63, 4, 0, 1, 32, -2]进行排序。
首先将序列分为两部分：待排序序列[4, 63, 4, 0, 1, 32, -2]、已排序序列[3]。

第一轮排序，从待排序序列中选取元素4，依次和已排序序列中元素比较，未找到比4大的元素，结束。
此时已排序序列为[3, 4]、待排序序列为[63, 4, 0, 1, 32, -2]。

第二轮排序，从待排序序列中选取元素63，依次和已排序序列中元素比较，未找到比63大的元素，结束。
此时已排序序列为[3, 4, 63]、待排序序列为[4, 0, 1, 32, -2]。

第三轮排序，从待排序序列中选取元素4，依次和已排序序列中元素比较，找到比4大的元素63，将4插入63之前，结束。
此时已排序序列为[3, 4, 4, 63]、待排序序列为[0, 1, 32, -2]。

第四轮排序，从待排序序列中选取元素0，依次和已排序序列中元素比较，找到比0大的元素3，将0插入3之前，结束。
此时已排序序列为[0, 3, 4, 4, 63]、待排序序列为[1, 32, -2]。

第五轮排序，从待排序序列中选取元素1，依次和已排序序列中元素比较，找到比1大的元素3，将1插入3之前，结束。
此时已排序序列为[0, 1, 3, 4, 4, 63]、待排序序列为[32, -2]。

第六轮排序，从待排序序列中选取元素32，依次和已排序序列中元素比较，找到比32大的元素63，将32插入63之前，结束。
此时已排序序列为[0, 1, 3, 4, 4, 32, 63]、待排序序列为[-2]。

第七轮排序，从待排序序列中选取元素-2，依次和已排序序列中元素比较，找到比-2大的元素0，将-2插入0之前，结束。
此时已排序序列为[-2, 0, 1, 3, 4, 4, 32, 63]、待排序序列为[]。

经过七轮排序后，待排序序列为空，排序结束。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] sort(int[] array) {
	for(int i=1; i<array.length; i++) {
		int temp = array[i];
		for(int j=0; j<i; j++) {
			//在已排序序列中找到一个比temp大的元素
			if(array[j] > temp) {
				//将较大元素（包括较大元素自身）往后的所有已排序序列中的元素向后移动
				for(int startIndex=i; startIndex>j; startIndex--) {
					array[startIndex] = array[startIndex-1];
				}
				//将temp插入到较大元素位置
				array[j] = temp;
				break;
			}
		}
	}
	
	return array;
}

选择排序

排序思想

选择排序和插入排序看上去很像，都是从未排序的序列中选择一个元素，然后插入到已排序序列中。
不同之处在于选择排序是从待排序序列中选择一个最小的元素，然后将这个元素插入到已排序序列的最后。

这个方法的优点是，不需要频繁的在数组中移动数据，只需要两两交换即可。

具体可步骤为：
第一步：从待排序序列中通过比较，找到最小的元素，记录其位置和值。
第二步：将这个元素与待排序序列的第一个元素（也就是已排序序列最后元素的下一个元素）交换值。
重复上述两步，直到所有元素已排完。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] sort(int[] array) {
	for(int i=0; i<array.length-1; i++) {
		int min = array[i];
		int minIndex = i;
		//从待排序序列中选择一个值最小的元素
		for(int j=i+1; j<array.length; j++) {
			if(min > array[j]) {
				min = array[j];
				minIndex = j;
			}
		}
		
		//待排序序列第一个元素和最小元素交换
		if(i < minIndex) {
			array[minIndex]  = array[i];
			array[i] = min;
		}
		System.out.println((i+1)+":"+Arrays.toString(array));
	}
	
	return array;
}

参考文章

  1. 面试题之——常用排序算法