C++实现冒泡，选择，插入排序算法-创新互联

1.冒泡排序         1.主要思路过程

总体思想是通过两层循环，逐个来确定当前最值，并通过交换，把最值逐渐移动到某一端，从而完成升序或者降序排序，这段代码采用的是升序，也就是逐个把当前的大值挪向数组右边。

创新互联是专业的青羊网站建设公司，青羊接单;提供成都网站设计、成都网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行青羊网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!2.代码实现过程

冒泡排序中，选出了一个大值，放在了某一端，下一轮就不会访问到这个上一轮的大值了，而是从剩下的数中进行选择，这里通过while循环来控制“冒泡“的次数，length为数组长度，每一轮冒泡确定当前的最值，也就是一共需要进行length次循环，length用于计数，所以每执行一轮排序，需要length--，直到减为0也就是完成了length次循环，while内层用一个for循环从数组的0号位置的元素往后遍历如果当前这个arr[ i ]大于arr[ i+1 ]就对这两个数进行交换的操作，遍历到i=当前的length-1时就停止（每一个arr[ i ]都是和arr[ i+1 ]比较）。

3.冒泡排序的完善

  有可能某一步的循环中，实际上上剩下的部分已经是完好的升序排列了，这一次循环就没有进行交换，后面的循环如果继续进行同样不会进行交换，也就变成了多余的步骤，所以我们可以对这个排序算法进行优化，引入一个用来控制while循环的数字flag（旗帜），先设置它为1（真），进入while循环之后立马让它等于0（假），如果满足交换的条件进行了交换，再重新把他的值变为1，以便于下轮while循环能够进行，如果这一轮中没有进行交换的操作，就说明这些数已经是升序排列了，就不会把flag的值改成1了，flag=0，之后的while循环也就不会再执行了。

void bob_sort(int arr[], int length) {
	int flag = 1;
	while (length-- && flag == 1) {
		flag = 0;
		for (int i = 0; i< length; i++) {
			if (arr[i] >arr[i + 1]) {
				flag = 1;
				int tem = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = tem;
			}
		}
	}
}

2.选择排序

  选择排序同样也是双层循环，第一层控制的是循环执行的次数，每执行完内层循环，最多完成一次交换，并确定一个当下最值，以及每一次外层循环的 i 值对应的位置就是这一轮内层循环所选择出的最值应该被放置的位置，每一轮内层循环筛选一个最小的元素值所对应的下标，每次执行内层循环先默认当前的 j 号元素为最小值，用a记录，往后遍历数组，遇到更小的arr[ i ]后就用令a=i，把a值更新，遍历完后，那个a值下标对应的数组元素也就是最值，将这个值arr[ a ]与arr[ i ]交换后，i号元素也就是这次循环所确定下来的最值了

  选择排序减少的是交换的次数，用变量储存数组元素下标后只需要更新这个记录值就可以了，遍历完后才只需要执行一次交换。

void select_sort(int arr[], int length) {
	for (int i = 0; i< length; i++) {
		int a = i;
		for (int j = i + 1; j< length; j++) {
			if (arr[j]< arr[a]) {
				a = j;
			}
		}
		int tem = arr[i];
		arr[i] = arr[a];
		arr[a] = tem;
	}
}

3.插入排序

  外层循环用来控制循环次数，让i从1开始，比较它和前一个元素的大小，如果后置位的元素要比前置位要小，就进入内层循环，将这个元素和所有在他前置位的元素一一比较大小，满足后置位小于前置位的条件后，执行交换两者的操作，直到遇到了比它小的元素后停止内层循环，这个元素也就拍好了位置，i 继续自增，往后继续逐个给元素排位置。

  插入排序的中心就是从i=1号位元素开始往后面排位置，他能保证在每次内层循环开始时，当前的 i 号元素之前的所有元素都是有序的，需要做的只是把该 i 号元素插入到应该的位置上。思路上面理解起来会比较清晰，后面所学到的希尔排序，实际上也是对插入排序的一种优化。

void sert_sort(int arr[], int length) {
	for (int i = 1; i< length; i++) {
		if (arr[i]< arr[i - 1]) {
			for (int j = i; j >= 1 && arr[j]< arr[j - 1]; j--) {
				int tem = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = tem;
			}
		}
	}
}

4.希尔排序         1.大致思路介绍

希尔排序实际上是对插入排序的一个优化版本，思路其实和插入排序如出一辙，在希尔排序中，我们引入了一个新的概念，叫做步长，换一种说法，插入排序就是步长为1的希尔排序，当数据量特别庞大的时候，步长为1的话就会过于缓慢，所以需要自己设置一个步长，根据这个步长，给数据分组，分组后再比较大小，前者比后者小，即交换，比如步长为1的时候，相邻的元素都会两两一组来进行比较，步长为2的时候就是每一个元素与他后面第二个元素为一组，来进行比较。

最外层的while循环用来控制轮数，每进行一轮就缩短步长（步长除2），直到步长为1执行后就停止，内层循环中，令i从步长h处开始，跟他前一个步长距离的元素去做比较，后置位的元素要是小于前置位的元素就执行交换。

  2.希尔排序中

  需要注意的一点就是，希尔排序中，当满足后置位元素小于前置位元素而进入最内层循环的时候，该后置位元素前面的元素不止一个前置位元素时，后置位那个元素依次和前面的元素比较，内层循环的 j 不能 j--，而是应该j-=h，往前跨的是步长，如果j--的话，就和步长为1的插入排序没有区别了，反倒是会多出很多赘余的步骤。

void shell_sort(int arr[], int length) {
	int h = length / 3;
	while (h >= 1) {
		for (int i = h; i< length; i++) {
			if (arr[i]< arr[i - h]) {
				for (int j = i; j >= h && arr[j]< arr[j - h]; j -= h) {
					int tem = arr[j];
					arr[j] = arr[j - h];
					arr[j - h] = tem;
				}
			}
		}
		h /= 2;
	}
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

名称栏目：C++实现冒泡，选择，插入排序算法-创新互联
网页地址：http://cqcxhl.cn/article/cdpjdc.html