比较排序 - 1：选择 插入 冒泡 鸡尾酒 希尔

Posted on | In
Words count in article: 803 | Reading time ≈ 3

Comparison sort

“A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a “less than or equal to” operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with:
if a ≤ b and b ≤ c then a ≤ c (transitivity)
for all a and b, a ≤ b or b ≤ a (connexity).”
From Wikipedia

完整排序算法代码：https://github.com/huangliu0909/Sort-Algorithms

比较排序的核心方法是进行两个数字的比较并进行位置的交换(swap)。

冒泡排序 Bubble sort

对每个元素逐个与后面的元素进行比较，如果顺序不正确则交换。类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来。i = 0时会把最大的数移动到数组的最后一位，i = k时会把第k+1大的数放在length-k-1处。

1
2
3
4
5
6
public static void bubble_sort(int[] array) {
	for (int i = 0; i < array.length - 1; i++) 
           for (int j = 0; j < array.length - i - 1; j++) 
               if (array[j] > array[j+1]) swap(array, j, j + 1);
               
}

选择排序 Selection sort

重复寻找剩余数组的最小值，与当前位置的值进行交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void selection_sort(int[] array) {
	for(int i = 0; i < array.length; i ++) {
		int min = array[i];
		int index = i;
		for(int j = i; j < array.length; j ++) {
			if(array[j] < min) {
				min = array[j];
				index = j;
			}
		}
		if(i != index) swap(array, i, index);
	}
}

插入排序 Insertion sort

遍历数组，将第i个数插入到前i-1个数的合适位置上。

1
2
3
4
5
6
7
8
9
10
11
public static void insertion_sort(int[] array) {
	for(int i = 1; i < array.length; i ++) {
		int index = array[i]; 
           int j = i - 1; 
           while (j >= 0 && array[j] > index) { 
           	array[j + 1] = array[j]; 
               j = j - 1; 
           } 
           array[j + 1] = index; 
	}    
}

鸡尾酒排序 Cocktail shaker sort

冒泡排序的变种。冒泡排序将最大的逐个放到最后，鸡尾酒排序是双向的冒泡。
第i轮时遍历范围索引是i到length-i-1，正向遍历一次，判断有无swap，无则返回，否则再进行一次逆向遍历，判断有无swap，循环直至没有swap。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void cocktail_shaker_sort(int[] array) {
	boolean swapped = true; 
	int i = 0;
	while(swapped == true) {
		swapped = false;
		for (int j = i; j < array.length - i - 1; j++) 
               if (array[j] > array[j+1]) {
               	 swap(array, j, j + 1);
               	 swapped = true;
               }
		if(swapped == false) return;
		swapped = false;
		for(int j = array.length - i - 2; j >= i; j --) {
			if (array[j] > array[j+1]) {
              	 swap(array, j, j + 1);
              	 swapped = true;
              }
		}
		i ++;
	}
}

希尔排序 Shellsort

插入排序的变种，首先对比间隔(gap)较远的元素而不是相邻(gap=1)元素，逐轮reduce到gap=1，这样可以有效减少最坏情况下元素的交换操作的数量。常见的gap选择为：gap=length/2，reduce过程gap=gap/2。最外层循环0~gap-1，对这其中的每个数不断+gap得到的间隔较远的元素进行插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	public static void shell_sort(int[] array) {
		int gap = array.length/2;
		while(gap != 0) {
			for(int i = 0; i < gap; i ++) {
				for(int j = i + gap; j < array.length; j += gap) {
					int index = array[j]; 
		            int k = j - gap; 
		            while (k >= i && array[k] > index) { 
		            	array[k + gap] = array[k]; 
		                k = k - gap; 
		            } 
		            array[k + gap] = index; 
				}
			}
			gap /= 2;
		}
	}
}

完整排序算法代码：https://github.com/huangliu0909/Sort-Algorithms