软考——排序（直接插入排序、冒泡排序）

直接插入排序

1、基本思想：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过。

2、评价：该方法，稳定

3、动图展示：
软考——排序（直接插入排序、冒泡排序）
4、代码展示：

template<class T>
void InsertSort(T* array, int n) {               //array待排序数组,n:数组元素数量
	int i, j;                                    //循环变量
	T temp;                                      //存储待排序元素
	for (i = 1; i < n; i++) {
		j = i;
		temp = array[i];                         //待排序元素赋值给临时变量
		while (j > 0 && temp < array[j - 1]) {   //当未达到数组的第一个元素或者待插入元素小于当前元素
			array[j] = array[j - 1];             //就将该元素后移
			j--;                                 //下标减一，继续比较
		}
		array[j] = temp;                         //插入位置已经找到，立即插入
	} 
}

冒泡排序

1、将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素；（第一轮结束后，序列最后一个元素一定是当前序列的最大值；）对序列当中剩下的n-1个元素再次执行步骤1

2、动图展示：
软考——排序（直接插入排序、冒泡排序）

3、代码展示：

template<class T>
void BubbleSort(T[], int n) {
	for (int i = 1; i < n; i++) {                    //共进行n - 1趟排序：从1到n-1,逐步缩小待排序列
		for (int j = n - 1; j >= i; j--) {           //反向检测，检查是否逆序
			if(T[j] > T[j - 1]){                     //发生逆序，交换元素的位置
				T temp = T[j];
				T[j] = T[j - 1];
				T[j - 1] = temp;
			}
		}
	}
}

软考的过程中，分享过后，对于排序方法和其代码都有了一定的理解，开心呐

软考——排序（直接插入排序、冒泡排序）

相关推荐