初等排序（三）：选择排序

迷南。 2022-02-24 04:04 151阅读 0赞

选择排序法作为一种非常直观的排序方法，会在每一个计算步骤中选出一个最小值，依次选出，进而完成排序。

selectionSort(A,N)   //包含N个元素的0起点数组A
    	for i 从0到 n-1
    		minj = i
    		for j 从 i 到 N-1
    			if A[j] < A[minj]
    				minj = j
    		A[i] 与 A[minj] 交换

同之前的插入排序法和冒泡排序法一样，选择排序法的各个计算步骤中，数组也分为“已排序部分”和“未排序部分”

**选择排序法：**  
重复执行N-1次下述处理  
1. 找出未排序部分最小值的位置minj  
2. 将minj位置的元素与未排序部分的起始元素交换

下面以数组A=\{5,4,8,7,9,3,1\}为例，对其使用选择排序法，过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzOTAyNQ_size_16_color_FFFFFF_t_70]  
步骤0为初始状态。所有元素出于未排序状态。  
步骤1，找出未排序部分最小值的位置（minj=6），然后将该位置的值A\[6\] (=1)与未排序部分的起始元素A\[0\] (=5)交换。未排序部分新增一个元素  
步骤2，剩下未排序元素中找出最小值的位置（minj=5）,然后将该位置元素A\[5\] （=3）与未排序部分起始元素A\[1\] (=4)交换。未排序部分元素个数变至2.  
重复此类过程，依次从数组开头按由小到大的顺序逐步确定每个位置的值。

实现选择排序法时的主要变量有：i，j，minj  
**其中 i** 循环变量，表示未排序部分的开头元素，从数组开头向数组末尾移动  
**j** 循环变量，用来查找未排序部分中最小值的位置（minj）  
**minj**各轮的循环处理中，第i号到N-1号元素中最小值元素的位置  
在每一轮i的循环中，通过j自增来遍历A\[i\]到A\[N-1\]，从而确定minj。确定minj后，让起始元素A\[i\]与最小值元素A\[minj\]进行交换。

//选择排序函数如下：
    int selectionSort(int A[],int N){ 
    	int i,j,t,sw=0,minj;
    	for(i=0;i<N-1;i++){ 
    		minj=i;
    		for(j=i;j<N;j++){ 
    			if(A[j]<A[minj])  minj=j;
    		}
    		t=A[i]; A[i]=A[minj]; A[minj]=t;
    		if(i!=minj) sw++;
    	} 
    	return sw;
    }

下边是Java语言实现的选择排序代码:

/** * 初始序列 : 5 4 7 3 2 * 第一趟: 2 4 7 3 5 * 第二趟: 2 3 7 4 5 * 第三趟: 2 3 4 7 5 * 第四趟: 2 3 4 5 7 * * @param array */
    	public static void selectSort(int[] array) { 
    		int len = array.length;
    		for (int i = 0; i < len - 1; i++) { 
    			int minIndex = i;
    
    			// 一趟循环结束,确定未排序序列中最小值元素的下标minIndex;
    			for (int j = i + 1; j < len; j++) { 
    				if (array[minIndex] > array[j]) { 
    					minIndex = j;
    				}
    			}
    			// 将最小值 放到合适位置
    			if (i != minIndex) { 
    				array[i] = array[minIndex] ^ array[i];
    				array[minIndex] = array[minIndex] ^ array[i];
    				array[i] = array[minIndex] ^ array[i];
    			}
    			System.out.println("第" + (i + 1) + "次排序:");
    			outArray(array);
    		}
    	}
    	
    	/** * 输出数组元素 * * @param array */
    	public static void outArray(int[] array) { 
    		for (int i = 0; i < array.length - 1; i++) { 
    			System.out.print(array[i] + " ");
    		}
    		System.out.println(array[array.length - 1]);
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzOTAyNQ_size_16_color_FFFFFF_t_70]: /images/20220224/4ab2e3cba8fb43cb943d41f4340c809e.png