算法和数据结构(2) ---- 冒泡排序和选择排序

短命女 2024-03-16 17:04 63阅读 0赞

### 1. 冒泡排序 ###

#### 算法思想 ####

以从小到大排序为例，冒泡排序的算法思想：

*  遍历原始数据，从第一个元素开始到倒数第二个元素结束，比较每一个元素和相邻元素的大小，如果当前的元素比相邻元素大，则交换两个元素的位置，这样可以将最大的数转移到数组的最后
 *  再次遍历原始数据，因为此时最后一个元素已经是最大，所以改为从**第一个元素开始到倒数第三个元素结束**，同样比较每一个元素和相邻元素的大小，如果当前的元素比相邻元素大，则交换两个元素的位置，这样就可以将第二大的元素移动到数组的倒数第二个位置
 *  重复上面的执行过程，一直到从第一个数开始，到第二个数结束，从而完成了排序过程

冒泡排序的示意图

![4e90d0b1434f4d5fa31221380a32ed46.jpeg][]

实现代码如下：

static void swap(int *a, int *b) // 交换两个变量
    {
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    
    
    //  冒泡排序
    static void _BubbleSort(int *array, int length) {
    	int i, j;
    
    	//  i 表示循环的次数
    	for (i = 1; i < length; i++ ) {
    		for (j = 0; j < length - i; j++) {
    			// 保证相邻的值 左边大于右边,第一轮可以保证最小的值移到右边
    			if (array[j] < array[j + 1]) {
    				swap(&array[j], &array[j+1]);
    			}
    		}
    	}
    }

第一轮： a\[j\] 和 a\[j +1\] 的比较，j 的取值范围是 0 ~ length -1 -1（从第一个到倒数第二个元素）

第二轮： a\[j\] 和 a\[j +1\] 的比较，j 的取值范围是 0 ~ length -1 -2（从第一个到倒数第三个元素）

......

第 n - 1 轮，a\[j\] 和 a\[j +1\] 的比较，j 的取值范围是 0（只剩第一个元素）

#### 时间复杂度 ####

冒泡排序的时间复杂度计算：外循环内循环和交换元素的时间开销，**最优的情况**也就是开始就已经排序好序了，那么就可以不用交换元素了，内层循环的执行次数 第 1 次：0 ~ n-2 共 n-1 次计算，第 2 次：0 ~ n-2 共 n-2 次计算 ，一直到最后：只剩下 0 共计 1 次计算；时间开销为 **1 + 2 + 3 + 4 + n-1**，时间花销为：\[ n(n-1) \] / 2；所以最优的情况时间复杂度为：***O*( n^2 )**；

**最差的情况**也就是开始的时候元素是逆序的，那么每一次排序都要交换两个元素，则时间花销为：\[ 3n(n-1) \] / 2，出现 3 的原因在于**交换元素的三个步骤**，所以最差情况下的时间复杂度为 ***O( n^2 )***

### 2. 选择排序 ###

#### 算法思想 ####

以从小到大排序为例，选择排序的算法思想：

*  在未排序序列中找到最小元素，放到序列的起始位置，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。

选择排序的思想和冒泡排序有相似的地方，都是在一次排序后将最小（最大）元素移动到最前面，但是过程不同，冒泡排序是相邻元素的比较和交换，而选择排序是整体的选择，每一次都能找出未排序序列的最小值，将最小值交换到最前面。

选择排序的动图：

![1a3e7d5d0ba84db0bda4fec3753a0f9c.gif][]

实现代码如下：

static void _selectSortIncrease(int *array, int length) {
    	int i, j;
    	//  如果 i = length - 1 表明已经到了最后一个元素 length -1, 则无需进行排序
    	for (i = 0; i < length - 1; i++) {
    
    		for (j = i + 1; j < length; j++) {
    			if (array[i] > array[j]) {
    				swap(&array[i], &array[j]);
    			}
    		}
    	}
    }
    
    
    //  优化后的选择排序算法
    static void _selectSortIncrease(int *array, int length) {
    	int i, j;
    	int min;
    	for (i = 0; i < length - 1; i++) {
    		min = i;
    		for (j = i + 1; j < length; j++) {
    			if (array[i] > array[j]) {
    				min = j;
    			}
    
    			swap(&array[i], &array[min]);
    		}
    	}
    }

#### 时间复杂度 ####

平均时间复杂度：O(n^2)，最佳时间复杂度：O(n^2)，最差时间复杂度：O(n^2)  
空间复杂度：O(1)，只需要一个额外变量记录最小值

选择排序的交换操作介于 0 ~ n-1 次之间，比较操作n(n-1)/2次之间，赋值操作介于0和3(n-1)次之间

[4e90d0b1434f4d5fa31221380a32ed46.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2791a39a579749c5ad7a17f6a6df84e9.png
[1a3e7d5d0ba84db0bda4fec3753a0f9c.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3d6bf322086b4eea9ef23ff19df2d7c1.png