【数据结构】排序算法篇一

【数据结构】排序算法篇一

• 1. 插入排序
• • （1）基本思想：
  • （2）动态图解：
  • （3）具体步骤：
  • （4）代码实现：
  • （5）特性总结：
• 2. 希尔排序( 缩小增量排序 )
• • （1）基本思想：
  • （2）静态图解：
  • （3）具体步骤：
  • （4）代码实现：
  • （5）特性总结：
• 3. 堆排序
• • （1）基本思想：
  • （2）具体步骤：
  • （3）代码实现：
  • （4）特性总结：
• 4. 选择排序
• • （1）基本思想：
  • （2）动态图解：
  • （3）具体步骤：
  • （4）代码实现：
  • （5）特性总结：

1. 插入排序

（1）基本思想：

由下图可以得出：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

（2）动态图解：

（3）具体步骤：

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

（4）代码实现：

void InsertSort(int *a,int aSize)
{
	for (int i = 1; i < aSize; i++)
	{
		int end = i - 1;
		int tmp = a[i];//tmp需要保存的是数组i处的值（a[i]）,如果存下标，会被a[end + 1] = a[end];该句代码覆盖
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
			a[end + 1] = tmp;
		}
	}
}

（5）特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2. 希尔排序( 缩小增量排序 )

（1）基本思想：

先选定一个整数（gap），把待排序文件中所有记录分成个若干组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后gap缩小，重复上述分组和排序的工作。当gap到达=1时，所有记录在统一组内排好序。

（2）静态图解：

（3）具体步骤：

该排序部分类似于插入排序

（4）代码实现：

void ShellSort(int* a, int aSize)
{
	int gap = aSize;
	while (gap > 1)
	{
		//gap > 1 预排序//gap = 1 插入排序
		gap /= 2;//或gab/=3+1;保证gab最后可等于1，此时即为最后一遍插入排序
		for (int i = 0; i < aSize - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
				a[end + gap] = tmp;
			}
		}

	}
}

（5）特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，因此希尔排序的时间复杂度未固定

3. 堆排序

（1）基本思想：

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是
通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

（2）具体步骤：

先实现一个向下调整建大堆函数，利用其将欲排序数组建为大堆，然后按照下面思想实现升序

（3）代码实现：

void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}
void AdjustDown(int* a, int aSize, int parent)//向下调整建大堆
{
	int child = 2 * parent + 1;
	while (child < aSize)
	{
		//不要漏掉条件child + 1 < aSize
		if (child + 1 < aSize && a[child] < a[child + 1])
		{
			child++;
		}
		//此时a[child]为大孩子
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int aSize)
{
	for (int i = (aSize - 1 - 1) / 2; i >= 0; i--)//将数组a建为大堆
	{
		AdjustDown(a, aSize, i);
	}
	//实现升序
	int end = aSize - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

（4）特性总结：

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

4. 选择排序

（1）基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

（2）动态图解：

（3）具体步骤：

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换，在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

（4）代码实现：

void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}
void SelectSort(int* a, int aSize)
{
	for (int j = 0; j < aSize; j++)
	{
		int min = j;
		for (int i = j; i < aSize; i++)
		{
			if (a[i] < a[min])
			{
				min = i;
			}
		}
		Swap(&a[min], &a[j]);
	}
}

（5）特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定