博客

冒泡排序

void maopao()
{
	int arr[] = {1,11,3,45,2,4,2,6,1};
	int length = sizeof(arr) / sizeof(int);
	for (int i = 0; i < length - 1; i++)
	{
		for (int j = 0; j < length - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

分析


整个程序有两个循环，两两比较后将最大的数迁移至最右边，每次冒出最大的数。

由于每次右边的第i个数已经完成排序，没必要再排了，该程序还能优化，改成这样

for (int j = 0; j < length - i - 1; j++)

选择排序

void xuanze()
{
	int arr[] = { 1,11,3,45,2,4,2,6,1 };
	int min = arr[0];
	int length = sizeof(arr) / sizeof(int);
	for(int i = 0;i<length-1;i++)
	{
		int min = arr[i];
		for (int j = i+1; j < length; j++)
		{
			if (arr[j] < min)
			{
				int temp = arr[j];
				arr[j] = min;
				min = temp;
			}
		}
		arr[i] = min;
	}
}

分析


每次假设arr[i]最小，然后往后找到比arr[i]小的就将arr[j]和min交换（min一开始是arr[i],往后会变化），后面的再和min比较，直到找到最小的，覆盖arr[i]的位置。

插入排序

void charu()
{
	int arr[] = { 1,11,3,45,2,4,2,6,1 };
	int min = arr[0];
	int length = sizeof(arr) / sizeof(int);
	for (int i = 1; i < length; i++)
	{
		int temp = arr[i];
		for (int j = i; j >= 0; j--)
		{
			if (temp < arr[j-1])
			{
				arr[j] = arr[j - 1];
			}
			else
			{
				arr[j] = temp;
				break;
			}
		}
	}
}

分析


每次先把arr[i]存着，然后往前比较，遇用下标j，将前面的两两相邻的比较，遇到符合（temp<arr[j-1]）条件的就交换并继续往前比较，不符合就退出，并将temp覆盖回arr[j]，此时的arr[j]是当前需要排序的数arr[i]的正确位置，如果不符合就break(因为前面的都以经排好序了，没必要再排）。

希尔排序

优化后的插入排序。

分析前面的插入排序，发现，如果当最大的数在最左边，就会造成每次内层的循环都要进行到最后（每次左边位置+1）,这样效率明显低下，在非常大的数组进行排序时会非常慢。希尔排序很好的解决了这个问题。

void shell()
{
	int arr[] = { 1,11,3,45,2,4,2,6,1,22};
	int min = arr[0];
	int length = sizeof(arr) / sizeof(int);
	int step = length;
	while (step /= 2)
	{
		for (int i = step; i < length; i++)
		{
			int temp = arr[i];
			for (int j = i; j > 0; j -= step)
			{
				if (arr[j] < arr[j - step])
				{
					arr[j] = arr[j - step];
				}
				else
				{
					arr[j] = temp;
					break;
				}
			}
		}
	}
}

分析


在插入排序的基础上，加入了步长step这个概念。将内层循环的每次比较时移动一步改为移动step步，原理还有插入排序的原理。这种方法为什么能排好序？通过演算发现，无论步长为多少，最后都会经历步长为1的时候（）相当于上面的插入排序），只不过我们事先将极端情况规避掉了而已，而当步长为1时的数组早已经被排得差不多了，此时花费的时间就比较少了。