数据结构|排序算法（三）选择排序 堆排序 归并排序

一、选择排序

1.算法思想

选择排序（Selection Sort）是一种简单直观的排序算法，其基本思想是：每次都从待排序部分中选出最小的一个数据和待排序的第一个数据交换。

将待排序序列分为已排序和未排序两部分，初始时已排序部分为空，未排序部分包含整个待排序序列。在每一轮迭代中，从未排序部分中选择最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，从而将该元素添加到已排序部分的末尾。重复这个过程，直到整个序列都被排序。
选择排序的具体步骤：
从整个序列中选择最小的元素，将其与第一个位置的元素交换。此时，第一个位置的元素就是整个序列中最小的元素，已排序部分包含这一个元素，未排序部分包含剩余的元素。
在剩余的未排序元素中选择最小的元素，将其与未排序部分的第一个位置（即第二个位置）的元素交换。此时，前两个位置的元素是有序的，已排序部分包含两个元素，未排序部分包含剩余的元素。
重复上述步骤，每次都从未排序部分中选择最小的元素，并将其与未排序部分的第一个位置的元素交换，直到未排序部分只剩下一个元素。此时，整个序列已经完全有序。

2.代码实现 

//选择排序
void SelectSort(int* arr, int len)
{int tmp;int minIndex;//最小值的下标for (int i = 0; i < len - 1; i++){minIndex = i;for (int j = i + 1; j < len; j++){if (arr[minIndex] > arr[j]){minIndex = j;}}if (minIndex != i)//最小值和待排序的第一个为同一个，则不交换，提高效率{tmp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = tmp;}}
}

 3.复杂度分析

1.选择排序的时间复杂度为O(n2)，其中n是待排序序列的长度。这是因为对于一个长度为n的序列，需要进行n−1轮选择和交换操作，每轮操作需要遍历未排序部分的元素，平均需要比较n/2次。

2.选择排序的空间复杂度为O(1)，因为它只需要使用常数级别的额外空间来进行元素的交换。

3. 不稳定：在选择排序里，当把最小元素和未排序序列的首个元素交换时，可能会改变相等元素的相对顺序。

二、堆排序

堆是一种特殊的完全二叉树，分为大根堆和小根堆。

大根堆的每个节点的值都大于或等于其左右子节点的值，小根堆则相反，每个节点的值都小于或等于其左右子节点的值。（大根堆小根堆只看父子关系）

堆排序的基本思想是将待排序的序列构建成一个堆，然后依次取出堆顶元素并调整堆，直到整个序列有序。

1.算法思想

• 建堆：将给定的数组构建成一个大根堆（或小根堆）。从最后一个非叶子节点开始，依次向上调整每个节点，使其满足堆的性质。
• 交换元素：将堆顶元素与堆的最后一个元素交换位置，此时堆顶元素是当前堆中的最大（或最小）值，将其取出，放到已排序序列的末尾。
• 调整堆：交换元素后，堆的性质可能被破坏，需要对剩余的元素重新调整堆，使其再次满足堆的性质。重复步骤 2 和 3，直到堆中只剩下一个元素，此时整个数组已经有序。

 1->调整成大根堆

(1)从最后一棵子树开始，从后往前调整

(2)每次调整，从上往下

(3)整体调整成大根堆

具体调整：

定义一个临时变量tmp，把根放到tmp里，找左右孩子的最大值，和tmp比较，如果比tmp大，则放到根的位置，继续递归比较新的左右孩子的最大值

调整顺序：

调整子树：

 调整完成：

 2->根和待排序的最后一个交换

根是最大的，交换后则视作有序

3->再次调整成大根堆

2.代码实现

//堆排序void HeapAdjust(int* arr, int start, int end)
{int tmp = arr[start];for (int i = 2 * start + 1; i <= end;i=2*i+1)//从上往下{if (i < end && arr[i] < arr[i + 1])//如果有右孩子，且左孩子的值小于右孩子{i++;}//i一定是左右孩子的最大值if (arr[i] > tmp){arr[start] = arr[i];start = i;}else{break;}}arr[start] = tmp;
}void HeapSort(int* arr, int len)
{//第一次建立大根堆（从后往前，多次调整）//根分别为4 3 2 1的子树for (int i = (len-1-1)/2; i >= 0; i--)//i的初值与结点总数有关，i=总结点数len-根-{HeapAdjust(arr, i, len - 1);}//每次将根和待排序的最后一个交换，然后再次调整（注意是待排序部分）int tmp;//用于交换for (int i = 0; i < len - 1; i++){tmp = arr[0];arr[0] = arr[len - 1 - i];arr[len - 1 - i] = tmp;//再次调整HeapAdjust(arr, 0, len - 1 - i - 1);}return;
}

3.复杂度分析 

建立大根堆的时间复杂度：O(n)

调整大根堆时间复杂度：O(logn)

综合建堆和排序两个阶段，堆排序的时间复杂度为O(n+nlogn)，通常简化为O(nlogn)。这是堆排序的平均时间复杂度；空间复杂度O(1)；不稳定

三、归并排序

1.算法思想

归并排序的基本思想是将一个数组分成两个子数组，对每个子数组进行排序，然后将排序好的子数组合并成一个排序好的数组。这个过程是递归进行的，直到子数组的长度为 1，此时子数组已经是有序的。

1.分解：将待排序的数组不断地分成两半，直到每个子数组只有一个元素。可以使用递归实现这一步骤。
2.合并：将两个已经排序好的子数组合并成一个排序好的数组。在合并过程中，比较两个子数组的元素，将较小的元素依次放入一个临时数组中，直到其中一个子数组的元素全部被放入临时数组。然后将另一个子数组中剩余的元素全部放入临时数组。最后将临时数组中的元素复制回原数组。

注意边界越界。 

2.代码实现

//归并排序
//一次归并
//gap：归并段的长度
static void Merge(int* arr, int len, int gap)
{int low1 = 0;//第一个归并段的起始下标int high1 = low1 + gap - 1;//第一个归并段的结束下标int low2 = high1 + 1;//第二个归并段的起始下标int high2 = low2 + gap - 1 < len - 1 ? low2 + gap - 1 : len - 1;//第二个归并段的结束下标//防止越界//存放归并好的数据int* brr = (int*)malloc(len * sizeof(int));assert(brr != NULL);int i = 0;//brr的下标//有两个归并段while (low2 < len)//表面至少存在两个归并段{//两个归并段都有数据，需要比较low1和low2while (low1<=high1&&low2<=high2){if (arr[low1] <= arr[low2]){brr[i++] = arr[low1++];}else{brr[i++] = arr[low2++];}//谁小存谁}//一个归并段的数据已经完成了，另一个还有数据while (low1 <= high1)//第一个归并段还有数据{brr[i++] = arr[low1++];}while (low2 <= high2)//第二个归并段还有数据{brr[i++] = arr[low2++];}//下两个归并段low1 = high2 + 1;high1 = low1 + gap - 1;low2 = high1 + 1;high2 = low2 + gap < len ? low2 + gap - 1 : len - 1;}//只有一个归并段while (low1<len){brr[i++] = arr[low1++];}//将归并好的数据拷贝到arr中for (i = 0; i < len; i++){arr[i] = brr[i];}free(brr);
}void MergeSort(int* arr, int len)
{for (int i = 1; i < len; i *= 2){Merge(arr, len, i);//一次归并}
}

3.复杂度分析

归并排序是一种基于分治思想的排序算法：

时间复杂度：
最好情况：当待排序序列已经是有序的时候，归并排序依然需要进行logn层的归并操作，每层归并操作需要比较和移动n次元素，所以时间复杂度为O(nlogn)。
最坏情况：当待排序序列是逆序的时候，同样需要logn层归并操作，每层归并操作也需要比较和移动n次元素，时间复杂度也是O(nlogn)。平均情况：归并排序将序列分成两部分，然后对两部分分别排序，再将排好序的两部分合并。

在平均情况下，每次划分都能将序列分成大致相等的两部分，所以时间复杂度为O(nlogn)。

空间复杂度：归并排序在合并过程中需要借助额外的存储空间来存放临时数据，最坏情况下需要
O(n)的辅助空间来完成排序。

稳定性：归并排序是稳定的排序算法。在归并过程中，当左右两个子序列中出现相等元素时，先将左边子序列中的元素放入临时数组，然后再将右边子序列中的元素放入临时数组，这样相等元素的相对顺序在排序前后不会发生改变。
综上所述，归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)，并且是稳定的排序算法。

以上是排序算法第三部分关于选择排序、堆排序以及归并排序的知识，如果有帮助可以点赞收藏一下，会持续更新输出有用的内容，感兴趣可以关注我！