【数据结构入门】排序算法之插入排序与选择排序

前言

一、排序的概念及运用

1.排序的概念

2.排序的运用

3.常见排序算法

二、插入排序与选择排序

2.1插入排序

2.1.1直接插入排序

1）基本思想

2）具体步骤

3）算法特性

4）算法实现

2.1.2希尔排序

1) 基本思想

2）具体步骤

3）算法特性

4）算法实现

2.2选择排序

2.2.1直接选择排序

1) 基本思想

2）具体步骤

3）算法特性

4）算法实现

2.2.2 堆排序

1) 基本思想

2）具体步骤

3）算法特性

4）算法实现

三、算法复杂度及稳定性分析

总结

前言

在数据结构中，排序是指将一组数据按照特定的规则重新排序的过程。排序可以使数据按照升序或者降序排列，从而方便后续的操作和查找。

一、排序的概念及运用

1.排序的概念

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

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

例如：

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

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

2.排序的运用

排序在生活中的使用无处不在，成绩排名、商品排名、电影榜单等等数不胜数。

3.常见排序算法

二、插入排序与选择排序

2.1插入排序

2.1.1直接插入排序

1）基本思想

直接插入排序是一种简单的排序算法，它的基本思想是将待排序的数据分成已排序和未排序两部分，每次从未排序部分中取出一个元素，然后将其有序地插入到已排序部分的合适位置。

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

动画演示：

2）具体步骤

将第一个元素视为已排序部分，将剩余的元素视为未排序部分。
从未排序部分取出第一个元素，将其插入到已排序部分的合适位置。插入时，从后往前逐个比较已排序部分的元素，将大于待插入元素的元素依次后移，直到找到一个小于或等于待插入元素的位置。
重复步骤2，直到未排序部分中的所有元素都插入到已排序部分。

3）算法特性

元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：直接插入排序的时间复杂度是O(n^2)，其中n是待排序数据的个数。当输入数据已经基本有序时，直接插入排序的性能较好，时间复杂度可以降低到O(n)。但当输入数据完全逆序时，直接插入排序的性能较差，时间复杂度会达到最大值O(n^2)。
空间复杂度：O(1)，它是一种稳定的排序算法
稳定性：稳定

4）算法实现

void InsertSort(int* a, int n)
{for (int i = 0; i < n; i++){int end = i-1;int tmp = a[i];//将tmp插入到[0, end]区间中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}	
}

2.1.2希尔排序

希尔排序法又称缩小增量法。

1) 基本思想

将待排序的数据按照一定的增量分组，对每组数据进行插入排序，然后逐渐减小增量，重复上述步骤，直至增量为1，完成最后一轮的插入排序。

图示：

2）具体步骤

选择一个增量序列，常用的增量序列是希尔增量（N/2, N/4, N/8...，直到增量为1）。
对于每个增量，以增量作为间隔将待排序的数据分成多个组，分别对每个组进行插入排序。
逐渐减小增量，重复上述步骤，直至增量为1。

3）算法特性

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度较为复杂，最好情况下为O(n log^2 n)，最坏情况下为O(n^2)，平均情况下为O(n log n)。希尔排序的性能优于直接插入排序，尤其是对于数据量较大的情况，其性能优势更加明显。这里一般可以认为时间复杂度为O(N^1.3)左右。
稳定性：不稳定

4）算法实现

多组同时排法：

void ShellSort(int* a, int n)
{//预处理int gap = n;while (gap > 1){//这里必须保证gap最后一次是1//gap /= 2;gap = gap / 3 + 1;for (int i = gap; i < n; i++){int end = i - gap;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;}}	
}

排完一组再排下一组：

void ShellSort(int* a, int n)
{//预处理int gap = n;while (gap > 1){//这里必须保证gap最后一次是1//gap /= 2;gap = gap / 3 + 1;for (int j = 0; j < gap; j++){for (int i = gap+j; i < n; i += gap){int end = i - gap;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;}}}	
}

2.2选择排序

2.2.1直接选择排序

1) 基本思想

每一次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾，直到全部待排序的数据元素排完。

动画演示：

2）具体步骤

找到待排序序列中最小（或最大）的元素，记为A。
将A与待排序序列的第一个元素交换位置。
然后在剩余的待排序序列中找到最小（或最大）的元素，再与待排序序列的第二个元素交换位置。
重复上述步骤，直到待排序序列变为空。

3）算法特性

直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
时间复杂度：直接选择排序的时间复杂度是O(n^2)，无论输入数据的情况如何，都需要进行n-1次的比较和若干次元素交换。虽然直接选择排序的时间复杂度较高，但是它的优点是原地排序，不需要额外的空间。
空间复杂度：O(1)
稳定性：不稳定

4）算法实现

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){int mini = left, maxi = left;for (int i = left + 1; i <= right; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[left], &a[mini]);//如果left和maxi重叠，交换后修正一下，否则这里会出问题，换两次换回去了if (maxi == left){maxi = mini;}Swap(&a[right], &a[maxi]);left++;right--;}
}

2.2.2 堆排序

堆排序是一种利用堆的数据结构进行排序的算法。堆是一种特殊的二叉树，满足堆性质：任意节点的值都大于等于（或小于等于）其子节点的值。需要注意的是排升序要建大堆，排降序建小堆。

1) 基本思想

将待排序的数据构造成一个堆，然后将堆顶元素与末尾元素交换，再对剩余的元素重新构造堆，以此类推，最终得到有序的序列。

2）具体步骤

构建最大堆（或最小堆），将待排序的数据转换为堆。
将堆顶元素（即最大值或最小值）与堆的最后一个叶子节点交换位置。
重新调整堆，将堆顶元素下沉，使得堆仍然满足堆性质。
重复上述步骤，直到堆只剩一个元素或为空。

3）算法特性

堆排序使用堆来选数，效率就高了很多。
时间复杂度：堆排序的时间复杂度是O(nlogn)，堆的构建需要O(n)的时间，每次调整堆的时间为O(logn)。堆排序是一种原地排序算法，不需要额外的空间。由于堆排序具有良好的局部性，适合用于大规模数据的排序。
空间复杂度：O(1)
稳定性：堆排序是一种不稳定的排序算法，相同元素的相对位置可能会改变。

4）算法实现

void ADjustDown(int* a, int sz, int parent)
{int child = parent * 2 + 1;while (child < sz){//选出左右孩子中大的一个//这里child+1的判断在前，不要先访问再判断//这里a[child + 1] > a[child] 建大堆用>， 建小堆用<if (child + 1 < sz && a[child + 1] > a[child]){//这地方可能会越界++child;}//这里a[child] > a[parent] 建大堆用>， 建小堆用<if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int sz)
{//1.建堆 -- 向上调整建堆   NlogN//左右子树必须是大堆/小堆/*for (int i = 1; i < sz; i++){ADjustUp(a, i);}*///2.向下调整建堆  N//左右子树必须是大堆/小堆for (int i = (sz - 1 - 1) / 2; i >= 0; i--){ADjustDown(a, sz, i);}int end = sz - 1;while (end > 0){Swap(&a[end], &a[0]);ADjustDown(a, end, 0);--end;}
}

堆排序在前文中已经详细介绍了，具体见：

【数据结构入门】二叉树之堆排序及链式二叉树