排序算法汇总I

发表于 2022-04-13 分类于算法思想本文字数： 2.8k 阅读时长 ≈ 3 分钟

排序算法汇总 I

冒泡排序

一边比较一边向后两两交换，将最大值/最小值冒泡到最后一位。
经过优化的写法，使用一个变量记录当前的轮次是否发生过交换，如果没有发生过交换表示已经有序，不需要继续排序。
进一步优化：除了变量记录当前轮次是否发生过交换外，在使用一个变量记录上次发生交换的位置，下一次排序时到上次交换的位置就停止比较。

具体写法如下：

第一种写法

public static void bubbleSort(int[] arr){
	for(int i=0;i<arr.length-1;i++){
		for(int j=0;j<arr.length-1-i;j++){
			if(arr[j]>arr[j+1]){
				// 如果左边的数大于右边的数，则交换，保证右边的数字最大
                swap(arr, j, j + 1);
			}
		}	
	}
}
//交换元素
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

这种写法相当于相邻的数字两两比较，并且规定：“谁大谁站右边”。经过 n-1n−1 轮，数字就从小到大排序完成了。整个过程看起来就像一个个气泡不断上浮，这也是“冒泡排序法”名字的由来。

第二种写法

public static void bubbleSort(int[] arr){
	// 初始时 swapped 为 true，否则排序过程无法启动
	boolean swapped = true;
	for(int i=0;i < arr.length-1 ; i++){
	    // 如果没有发生过交换，则说明剩余部分已经有序，排序完成
	    if(!swapped) break;
	    swapped = false;
	    // 设置 swapped 为 false，如果发生交换，则将其置为 true
	    for(int j=0;j < arr.length-1-i;j++){
	        if(arr[j] > arr[j+1]){
	            // 如果左边的数大于右边的数，则交换，保证右边的数字最大
	        	swap(arr,j,j+1);
	        	// 表示发生了交换
	        	swapped = true;
	        }
	    }
	}
}

最外层的 for 循环每经过一轮，剩余数字中的最大值仍然是被移动到当前轮次的最后一位。这种写法相对于第一种写法的优点是：如果一轮比较中没有发生过交换，则立即停止排序，因为此时剩余数字一定已经有序了。

第三种写法

public static void bubbleSort(int[] arr){
	boolean swapped = true;
	// 最后一个没有经过排序的元素的下标
	int indexTerm = arr.length - 1 ;
	// 上次发生交换的位置
	int swapIdx = -1;
	while(swapped){
		swapped = false;
		for(int i=0 ;i<indexTerm;i++){
		   if(arr[i] > arr[i+1]){
		   	   // 如果左边的数大于右边的数，则交换，保证右边的数字最大
		       swap(arr,i,i+1)
		       // 表示发生了交换
		       swapped = true;
		       // 更新交换的位置
		       swapIdx = i;
		   }
		}
		// 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置
		indexTerm = swapIdx ; 
	}
}

经过再一次的优化，代码看起来就稍微有点复杂了。最外层的 while 循环每经过一轮，剩余数字中的最大值仍然是被移动到当前轮次的最后一位。

在下一轮比较时，只需比较到上一轮比较中，最后一次发生交换的位置即可。因为后面的所有元素都没有发生过交换，必然已经有序了。

当一轮比较中从头到尾都没有发生过交换，则表示整个列表已经有序，排序完成。

选择排序

算法思想：双重循环遍历数组，每经过一轮比较，找到最小元素的下标，将其交换到首位。

public static void selectSort(int[] arr){
	int minIndex;
	for(int i = 0; i <arr.length-1 ; i++){
		minIndex = i;
		for(int j=i+1;j<arr.length;j++){
			if(arr[minIndex] > arr[j]){
			   // 记录最小值的下标
				minIndex = j;
			}
		}
		int temp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = temp;
	}
}

选择排序就好比第一个数字站在擂台上，大吼一声：“还有谁比我小？”。剩余数字来挨个打擂，如果出现比第一个数字小的数，则新的擂主产生。每轮打擂结束都会找出一个最小的数，将其交换至首位。经过 n-1 轮打擂，所有的数字就按照从小到大排序完成了。

冒泡排序和选择排序的比较：

都是两层循环，时间复杂度都为 O(n^2)；都只使用有限个变量，空间复杂度 O(1)。
冒泡排序在比较过程中就不断交换；而选择排序增加了一个变量保存最小值 / 最大值的下标，遍历完成后才交换，减少了交换次数。
冒泡排序法是稳定的，选择排序法是不稳定的。

扩展：

关于排序算法的稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

在冒泡排序中，只有左边的数字大于右边的数字时才会发生交换，相等的数字之间不会发生交换，所以它是稳定的。
选择排序中，最小值和首位交换的过程可能会破坏稳定性。比如数列：[2, 2, 1]，在选择排序中第一次进行交换时，原数列中的两个 2 的相对顺序就被改变了，因此，我们说选择排序是不稳定的。
排序的稳定性的意义：

当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。举个例子，如果我们要对一组商品排序，商品存在两个属性：价格和销量。当我们按照价格从高到低排序后，要再按照销量对其排序，这时，如果要保证销量相同的商品仍保持价格从高到低的顺序，就必须使用稳定性算法。