选择排序和冒泡排序

本小节主要关于选择排序和冒泡排序的分析

选择排序

基本原理

• 扫描整个列表或数组（长度为n），找到最小元素，将其和第一个元素进行交换，此时最小元素在有序表中的最终位置上；
• 从第二元素开始扫描列表，找到最后n-1个元素中的最小元素，再和第二个元素交换位置；
• 之后，在对该列表做第i遍扫描时(i值为0~n-2)，在最后n-i个元素中寻找最小元素，然后将之和 A[i] 交换；
• 在经过n-1遍后，列表已序。

示例：

| 89   45   68   90   29   34   17
  17 | 45   68   90   29   34   89
  17   29 | 68   90   45   34   89
  17   29   34 | 90   45   68   89
  17   29   34   45 | 90   68   89
  17   29   34   45   68 | 90   89
  17   29   34   45   68   89 | 90

扫描这个7个数，找到最小数17，然后将其与第一个元素89进行交换，此时17已序；之后扫描剩下的6个数，找到其中最小数29，将其与45交换；接着依次找到34，45, 68，89，最后数组已序。

代码实现

伪代码：

算法 SelectionSort(A[0..n-1])
     //该算法用选择排序对给定列表排序
     //输入: 一个可排序数组 A[0..n-1]
     //输出: 升序排列的数组 A[0..n-1]
     for i = 0 to n - 2 do
         min = i
         for j = i + 1 to n - 1 do
             if A[j] < A[min]
                  min = j
         swap A[i] and A[min]

python实现：

def SelectionSort(A):
    #选择排序 对给定列表排序(升序)
    #输入: 待排序列表 A[0..n-1] list
    #输出: 已排序列表 A[0..n-1] list
    lenA = len(A)
    for i in range(lenA-1):
        minValIndex = i
        for j in range(i+1, lenA):
            if A[minValIndex] > A[j]:
                minValIndex = j
        A[i], A[minValIndex] = A[minValIndex], A[i]

java实现：

package selection_bubble_sort;

/**
 * @author jwj
 *
 */
public class SelectionSort {
	/**
	 * @param arr
	 */
	public static void selectSort(int[] arr) {
		int min = -1;
		for (int i = 0; i < arr.length-1; i++) {
			min = i;
			for (int j = i+1; j < arr.length; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			swap(arr, i, min);
		}
	}

	/**
	 * @param array
	 * @param i
	 * @param j
	 */
	public static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	/**
	 * @param array
	 */
	public static void print(int[] array) {
		for (int i : array) {
			System.out.print(i + " ");
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = {4, 2, 3, 6, 1, 7, 9, 8};
		selectSort(a);
		print(a);
	}
}

算法分析

选择排序的输入规模是由数组中元素的个数n决定的。整个算法的基本操作是键值比较$A[j] < A[min]$。比较的执行次数：
$$
C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^{n-2} [(n-1)-(i+1)+1] = \sum_{i=0}^{n-2}(n-1-i) = \frac{(n-1)n}{2}
$$
因此，对于任何输入来说，选择排序都是一个$\Theta(n^2)$的算法，其中数组元素交换的次数仅为$\Theta(n)$，更精确点，是$n-1$次（$i$循环每重复依次执行一次交换），这个特性使得选择排序优于许多其他的排序算法。

冒泡排序

基本原理

• 从第一个元素开始，依次比较相邻元素值，即第一个元素和第二个元素比较，若逆序，则交换位置；
• 第二个元素和第三个元素比较，若逆序，交换位置；
• 依次下去，则将最大元素移动到了最右端（“沉到最底部”）；
• 再次从列表头开始依次比较相邻数，重复多次后，第二大的数已移到最右第二个位置上；
• 多次比较后，列表已序。

示例：

89 <?> 45     68     90     29     34     17
45     89 <?> 68     90     29     34     17
45     68     89 <?> 90     29     34     17
45     68     89     90 <?> 29     34     17
45     68     89     29     90 <?> 34     17
45     68     89     29     34     90 <?> 17
45     68     89     29     34     17    |90

45 <?> 68     89     29     34     17    |90
45     68 <?> 89     29     34     17    |90
45     68     89 <?> 29     34     17    |90
45     68     29     89 <?> 34     17    |90
45     68     29     34     89 <?> 17    |90
45     68     29     34     17    |89     90

etc.

首先，比较数组中的第一、第二个元素值，89和45，逆序，交换位置；之后比较第二、第三个元素值，89和68，逆序，交换位置；接着比较第三、第四个元素值，89和90，已序，不变；然后继续依次比较后续的数值，直到最大数90移动到最右端为止。
再次从数组开头依次进行比较，最后将第二大的数值移动到最右第二个位置上。
之后就继续多次比较，直到所有数据已序。

代码实现

伪代码：

算法 BubbleSort(A[0..n-1])
     //该算法用冒泡排序对数组A[0..n-1]进行排序
     //输入：一个可排序数组A[0..n-1]
     //输出：非降序排列的数组A[0..n-1]
     for i = 0 to n - 2 do
         for j = 0 to n - 2 - i do
             if A[j+1] < A[j]
                 swap A[j] and A[j+1]

python实现：

def BubbleSort(A):
    #冒泡排序 对给定列表排序(升序)
    #输入: 待排序列表 A[0..n-1] list
    #输出: 已排序列表 A[0..n-1] list
    lenA = len(A)
    for i in range(lenA-1):
        for j in range(lenA-1-i):
            if A[j+1] < A[j]:
                A[j], A[j+1] = A[j+1], A[j]

java实现：

package selection_bubble_sort;

/**
 * @author jwj
 *
 */
public class BubbleSort {
	/**
	 * @param arr
	 */
	public static void bubbleSort(int[] arr) {
		int len = arr.length;
		for (int i = 0; i < len-1; i++) {
			for (int j = 0; j < len-1-i; j++) {
				if (arr[j+1] < arr[j]) {
					swap(arr, j, j+1);
				}
			}
		}
	}

	/**
	 * @param array
	 * @param i
	 * @param j
	 */
	public static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	/**
	 * @param arr
	 */
	public static void print(int[] arr) {
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] array = {5, 7, 4, 3, 6, 1, 2, 9, 8};
		bubbleSort(array);
		print(array);
	}
}

算法分析

对于所有规模为n的数组来说，该冒泡排序版本的键值比较次数都是相同的，次数：
$$
C(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-2-i} 1 = \sum_{i=0}^{n-2} [(n-2-i)-0+1] = \sum_{i=0}^{n-2}(n-1-i) = \frac{(n-1)n}{2}
$$
键交换次数取决于特定的输入。最坏的情况是遇到降序排列的数组，这时，键交换次数和键比较次数是相同的。
$$
S_{worst}(n) = C(n) = \frac{(n-1)n}{2}
$$