【数据结构】排序（1）

目录

一、概念：

二、直接插入排序：

三、希尔排序：

四、直接选择排序：

五、堆排序：

六、冒泡排序：

---

一、概念：

排序的概念：

        使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

排序又分为内部排序和外部排序：

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

常见的排序算法：

二、直接插入排序：

基本思想：

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

例如在我们玩扑克牌斗地主时的码牌操作中就运用到了这个思想。

代码实现：

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

//时间复杂度: O(N^2)	逆序
//最好的情况: O(N)	顺序有序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)// i小于n-1是为下面条件做铺垫，防止越界
	{
		// 设置end为下标，将其与tmp下标位置的数进行比较，并不断更新end
		int end = i;
		int tmp = a[end + 1];// 在单趟排序中，tmp固定
 
		// 设置数组最小数的条件
		while (end >= 0)
		{
			// 对tmp和end位置数进行比较
			if (tmp < a[end]) 
			{
				// 将end位置数复制在end+1处，本质上是更新去排序后对应的位置
				a[end + 1] = a[end];
				end--;// 更新end
			}
			else
			{
				break;
			}
		}
		// 将tmp数放入对应的位置
		a[end + 1] = tmp;
	}
}

直接插入排序的特性总结：

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

三、希尔排序：

又称缩小增量排序 

基本思想：

先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。

gap越大，大的值更快调到后面，小的值可以更快的调到前面，越不接近有序。

gap越小，跳的越慢，但是越接近有序，如果gap == 1，就是直接插入排序。

代码实现：

void ShellSort(int* a, int Size)
{
	int gap = Size;
	// gap > 1时是预排序，目的让他接近有序
	// gap == 1是直接插入排序，目的是让他有序
	while (gap > 1)
	{
		gap = gap / 3 + 1;//保证最后一次gap是1，就是直接插入排序，但是数列已经非常接近有序了
						 //gap代表的是有多少组
 
		// 这里就跟直接插入排序的模板一样
		for (int i = 0; i < Size - 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;
		}
	}
}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，就是直接插入排序。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多。

4. 时间复杂度(平均)：O(N^1.3)

5. 空间复杂度：O(1)

6. 稳定性：不稳定。

四、直接选择排序：

基本思想：

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

代码实现：

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

// 时间复杂度: O(N^2)
// 最好的情况: O(N^2) 即使原本就有序，还是要暴力取数
// 空间复杂度: O(1)
void SelectSort(int* a, int Size)// 升序
{
	//设置下标
	int begin = 0;
	while (begin < Size)
	{
		int min = begin;
		// 暴力选数
		for (int i = begin + 1; i < Size; i++)
		{
			if (a[i] < a[min])
			{
				min = i;
			}
		}
 
		swap(a[begin], a[min]); //这里的swap使用的是库函数中写好了的，
								// 使用自己写的注意形参与实参
		begin++;
	}
}

直接选择排序的特性总结：

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

五、堆排序：

基本思想：

利用堆删除思想来进行排序使用向下调整。需要注意的是排升序要建大堆，排降序建小堆。

代码实现：

// 向下调整:升序建大堆
void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
 
	// 一层层的往下判别
	while (child < size)
	{
		// 在保证不越界的前提下找出数大的子节点
		if (child + 1 < size && a[child + 1] > a[child])
		{
			child++;
		}
 
		if (a[child] > a[parent])
		{
			swap(a[child], a[parent]);// 这里的swap使用的是库函数中写好了的，
                                      // 使用自己写的注意形参与实参
			// 更新父，子节点
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
// 升序
void HeapSort(int* a, int Size)
{
	// O(N)
	// 要排升序，所以建大堆->找最后一个分叶节点向下调整，然后向前依次操作
	for (int i = (Size - 1 - 1) / 2; i >= 0; i--)
	// Size是个数，要下标所以-1，结合找最后一个分叶结点公式化简
	{
		AdjustDown(a, Size, i);
	}
 
	// O(N*logN)
 
	int end = Size - 1;
	while (end > 0)
	{
 
		swap(a[0], a[end]);
 
		// 在向下调整使用end时，取的值是小于end，默认忽略最后一位,由前Size-1个数进行向下调整
		AdjustDown(a, end, 0);
		end--;
	}
}

堆排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

六、冒泡排序：

基本思想：

       两两元素相比，前一个比后一个大就交换，直到将最大/最小（升序/降序）的元素交换到末尾位置。这为一趟；一共进行 n-1 趟这样的交换将可以把所有的元素排序好。

代码实现：

//时间复杂度: O(N^2)	乱序
//最好的情况: O(N)   有序
void BubbleSort(int* a, int Size)
{
	// n个数只需排 n - 1 躺即可
	for (int i = 0; i < Size - 1; i++)
	{
		// 设置一个条件，判断一趟排序下来是否有位置交换
		bool exchange = false;
		for (int j = 1; j < Size - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				swap(a[j - 1], a[j]); // 这里的swap使用的是库函数中写好了的，
                                      // 使用自己写的注意形参与实参
				exchange = true;
			}
		}
 
		// 如果单趟下来并没有数交换位置则说明这个数列本就有序
		if (exchange = false)
		{
			break;
		}
	}
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定