cnblog-排序算法

选择排序

顾名思义选择最值（最大或者最小值）存放到排序数列的起始位置，然后在剩余数列中寻找最值，然后将其放到已排序数列的末尾。以此类推，直到所有元素排序完毕。

算法描述

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。跟选择排序的不同点是插入排序时向前搜索，而选择排序是向后搜索

  • 初始状态：无序区为R[1..n]，有序区为空；
  • 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
  • n-1趟结束，数组有序化了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void selectionSort(int[]arr){
	for (int i = 0; i < arr.length; i++) {
		int maxIndex = i;
		for (int j = i + 1; j < arr.length; j++) {
		    if (arr[maxIndex] < arr[j]) {
		        maxIndex = j;
		    }
		}
		if (maxIndex != i) {
		    int temp = arr[maxIndex];
		    arr[maxIndex] = arr[i];
		    arr[i] = temp;
		}
	}
}

动图演示

插入排序

算法描述

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。可以想象手中的扑克牌的排序。

  • 从第一个元素开始，可以认为该元素是已经排序过的
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描
  • 如果元素大于（小于）新元素，则交换位置
  • 重复交换 直至 新元素在已排序数列中达到有序的位置上
  • 重复 2 ~ 5步骤

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public void insertSort(int[] arr){
	for (int i = 1; i < arr.length; i++) {
	    int temp = arr[i];
	    int preIndex = i - 1;
	    while (preIndex >= 0 && arr[preIndex] > temp) {
	        arr[preIndex + 1] = arr[preIndex];
	        preIndex--;
	    }
	    if (preIndex + 1 != i - 1) {
	        arr[preIndex + 1] = temp;
	    }
	}
}

动图演示