提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

冒泡排序，选择排序，插入排序，折半插入排序

数组 排序
2023-03-14 22:49:18 时间

今天我们来聊聊简单算法：冒泡，简单选择，直接插入

1.冒泡排序：

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录的为止，这里的反序指的是不符合当前指定排序规则的数字

（1）对数组做交换排序（冒泡排序初级版）

//冒泡排序初级版---升序
void BubbleSort(int arr[],int len)
{
	for (int i = 0; i < len-1; i++)
	{
		for (int j = i + 1; j <= len - 1; j++)
		{
			if (arr[i]>arr[j])
			{
				int temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
	}
}

思路：让每一个关键字都和他后面的一个关键字进行比较，如果前一个大于后一个则交换，那么第一个位置关键字经过一趟内层循环比较就变成了最小值，由此可见： 外层循环：每一次将当前外层循环对应位置i变成仅此于前一位的最小值 内层循环：负责把外层循环对应i的值与i后面到数组结尾的元素进行大小比较，从而选出最小值替换当前I位置的值 （2）正宗冒泡算法

//正宗冒泡排序---升序
void BubbleSort(int arr[],int len)
{
	for (int i = 0; i < len-1; i++)
	{
		for (int j = len-2; j >=i; j--)
		{
			if (arr[j]>arr[j+1])
			{
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

思路：从后面开始进行比较交换操作，此时i后面到数组开头元素都是有序序列，而从位置i起到数组结尾都是无序元素，内存循环每一次从数组尾部两两比较，进行交换操作，一直比较到i的位置，从而最后一次交换，把i当前的值变成仅此于其前一位的最小或者最大值，内存循环每结束一次，对应在无序序列中找到一个最小值，外层循环i++,对应有序序列在增加，无序序列在减少

此时对应内存循环完成一次，在从i开始到数组结尾的范围内找出了一个最小值赋值给了i，但是此时我们发现数组已经有序，但是循环还要继续，直到结束，此时我们就需要对冒泡排序进行改进，让其避免在已经有序的情况下进行无意义的循环判断 （3）冒泡排序的优化—针对基本有序的序列，进行无意义比较操作

//冒泡排序优化---升序
void BubbleSort(int arr[],int len)
{
	bool flag = true;//用flag作为标记
	for (int i = 0; i < len-1&&flag; i++)//当flag为假的时候，退出循环
	{
		flag = false;//设置flag为假
		for (int j = len-2; j >=i; j--)
		{
			if (arr[j]>arr[j+1])
			{
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				flag = true;//如果内存循环进行了交换操作，设置flag为真
				//说明此时数组并不完全有序，还需要进行一次外层循环确认经过上次内存循环交换后，数组是否已经有序
			}
		}
	}
}

思路：设置一个flag标志，用来判断数组是否已经处于有序状态，初始时设置falg为真，表示需要先进入循环一次检查数组有序性，进入外层循环后，设置flag为真，然后进入内层循环，如果内存循环里面进行了交换操作，就重新设置flag为真，表示当前数组再交换完后，不确定是否处于有序状态，还需要进行一次循环，来检验是否已经有序。如果内存循环里面没有进行交换操作，表示当前数组已经有序，那么退出内存循环的时候，flag仍为假，此时不满足外层循环条件，退出外层循环，数组排好序

选择排序

冒泡排序的思想就是不断在交换，通过交换完成最终的排序，而选择排序不断进行比较而非交换操作，最终找到最小值后，赋值给当前i对应的值，相当于省去了交换的时间损耗

//简单选择排序
void SelectSort(int arr[], int len)
{
	int i, j, min;
	for (i = 0; i < len-1; i++)
	{
		min = i;//假设当前位置i为最小值
		for (j = i + 1; j < len; j++)
		{
			if (arr[min] > arr[j])
			{
				min = j;//找到比当前min位置更小的值，更小j的值
			}
		}
		//如果当前i位置就是最小值，就不进行交换操作,否则交换
		if (i != min)
		{
			int temp = arr[i];
			arr[i] = arr[min];
			arr[min] = temp;
		}
	}
}

思路：相对于初级版的冒泡排序（交换排序），就是省去了交换过程，变成了下标的更新，最后再完成一次交换

3.直接插入排序

直接插入排序就是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表

//直接插入排序----升序
void InsertSort(int arr[], int len)
{
	//一开始把数组的第一个元素看做有序序列，从第二个元素开始到数组结尾为无序序列
	//外层循环每执行一次，有序序列长度加一，无序序列长度减一
	int j;
	for (int i = 1; i < len; i++)
	{
		//满足下面条件说明：取出来的无序序列第一个元素，小于有序序列最后一个元素，需要将这个元素插入到有序序列中的合适位置
		if (arr[i] <arr[i - 1])//i是无序序列的第一个元素下标  i-1就是有序序列最后一个元素下标
		{
			int temp = arr[i];//保存这个需要插入的无序序列元素，因为一会该值会因为数组元素移动而被覆盖掉
			//通过下面这个循环在有序序列中找到一个位置，此时temp值大于他前一个元素，小于他后一个元素
			for (j = i - 1;temp<arr[j]&&j>=0; j--)
			{
				//在不断寻找的过程中，把数据进行后移操作，以便在找到合适位置的时候能够直接插入
				arr[j + 1] = arr[j];
			}
			//最后将temp插入到合适的位置
			arr[j + 1] = temp;
		}
	}
}

降序版本

//直接插入排序----升序
void InsertSort(int arr[], int len)
{
	int j;
	for (int i = 1; i < len; i++)
	{
		if (arr[i]>arr[i - 1])
		{
			int temp = arr[i];
			for (j = i - 1;temp>arr[j]&&j>=0; j--)
			{
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = temp;
		}
	}
}

折半插入排序

将比较找到合适位置的过程用二分查找替代，在需要对海量数据进行排序的时候，提高了效率 升序：

//折半插入排序----升序
void InsertSort(int arr[], int len)
{
	int j, low, high, m,temp;
	for (int i = 1; i < len; i++)
	{
		//先通过二分查找在有序序列中找到无序元素合适的插入位置，在通过数组元素后移，将无序元素插入其中
		low = 0;
		high = i - 1;
		temp = arr[i];
		//最后退出while循环的时候，low>high
		//high指向待插入位置的前一位，而low指向待插入位置
		while (low <= high)
		{
			//找到有序序列中间位置
			m = (low + high) / 2;
			//将无序元素和中间元素值进行比较，看该元素是比中间元素大，还是比中间元素小
			if (arr[i] >=arr[m])
			{
				low = m + 1;
			}
			else 
			{
				high = m - 1;
			}
		}
		//找到合适位置，此时进行有序序列元素后移，腾出空间存放无序元素
		for ( j = i - 1; j > high; j--)
		{
			arr[j + 1] = arr[j];
		}
		arr[j + 1] =temp;
	}
}

降序：

#include<iostream>
using namespace std;
//折半插入排序----升序
void InsertSort(int arr[], int len)
{
	int j, low, high, m,temp;
	for (int i = 1; i < len; i++)
	{
		//先通过二分查找在有序序列中找到无序元素合适的插入位置，在通过数组元素后移，将无序元素插入其中
		low = 0;
		high = i - 1;
		temp = arr[i];
		//最后退出while循环的时候，low>high
		//high指向待插入位置的前一位，而low指向待插入位置
		while (low <= high)
		{
			//找到有序序列中间位置
			m = (low + high) / 2;
			//将无序元素和中间元素值进行比较，看该元素是比中间元素大，还是比中间元素小
			if (arr[i] <=arr[m])
			{
				low = m + 1;
			}
			else 
			{
				high = m - 1;
			}
		}
		//找到合适位置，此时进行有序序列元素后移，腾出空间存放无序元素
		for ( j = i - 1; j > high; j--)
		{
			arr[j + 1] = arr[j];
		}
		arr[j + 1] =temp;
	}
}
void test()
{
	int arr[6] = { 5,4,2,1,3,6 };
	InsertSort(arr, 6);
	for (int i = 0; i < 6; i++)
		cout << arr[i] << " ";
}
int main()
{
	test();
	system("pause");
	return 0;
}

相关文章