政府网站官网_网站建站工具有哪些_html友情链接_免费写文案神器

---

前言

  承上启下，正文开始！

---

一、希尔排序( 缩小增量排序 )

  希尔排序是一种基于插入排序的算法，通过引入增量的概念来改进插入排序的性能

基本思想

  通过预排序使得无序接近有序序列，大体流程:先选定一个整数gap，将待排序序列中所有记录分组，所有距离为gap记录分在同一组，并对每一组记录进行排序，重复上述分组和排序的工作(gap不断缩小)，当gap到达1，此时记录已经接近有序，最后整体进行插入排序，使得记录排好序

gap为1的时候，其实就已经退化为直接插入排序

实现思路

  gap就是增量，我们发现根据当前增量，数组被分为gap个子序列，这些子序列的元素在原数组中间隔着固定的增量。对每个子序列应用插入排序，因为gap一开始很大，最后才慢慢变回1，说明一开始如果升序且小数据在后面，能被很快的移动到前面，从而达到降低时间复杂度的目的，这也是我们优化的一种体现

在合理设置增量的前提下，一个数组一共可以分裂成增量个子序列，且每个子序列上相邻元素之差为增量

 我们以上图为例子，5个子序列分别是：

子序列1: 9，4
子序列2: 1，8
子序列3: 2，6
子序列4: 5，3
子序列5: 7，5

 然后对每个子序列进行独立的插入排序：

子序列1排序后：4，9
子序列2排序后：1，8
子序列3排序后：2，6
子序列2排序后：3，5
子序列3排序后：5，7

 一趟排序之后的数组：

4 1 2 3 5 9 8 6 5 7

 我们发现走了一轮希尔排序后，数组并不是完全有序，但是已经更接近有序了，接着就可以减小增量了！

 但是如何减小增量？一般有两种处理方式：

gap /= 2，保证了无论gap初始值多少，最后都能变为1，完成直接插入排序
gap = gap / 3 + 1; 因为如果gap为2的时候，在/3就直接等于0了，没有完成直接插入排序

 所以单独一个子序列排序：

int gap;
int end;
int tmp = a[end + gap];
while (end >= 0)
{if (a[end] > tmp){a[end + gap] = a[end];end-=gap;}else{break;}
}
a[end + gap] = tmp;

与直接插入代码不同的是，这里对end所加减的均为gap
如若不理解，请画图！！

 单趟排序实现：

//这里for循环的条件为 i < n-gap 防止数组越界
int gap;for (int i = 0; i < n-gap; i += gap)
{int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;
}

 全部子序列排序：

//外层循环（for (int j = 0; j < gap; j++)）意在对每个以gap为间隔的分组进行遍历
int gap;
for (int j = 0; j < gap; j++)
{for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}

  上述代码的三层循环着实不太美观，于是我们换一种思路，不再排完一个子序列再排另外一个子序列，因为每个子序列之间不会产生交互，于是我们把 i += gap，改为i++，并且脱去最外层的循环

//这时候就变成了统一排完每个子序列的同一个位置的元素后，再排下一个位置的元素
//比如n为10，gap为5，那么有5个子序列，这里就是统一排完5个子序列的第二个元素后，完成循环跳出
for (int i = 0; i < n - gap; i++)
{int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;
}	

  那么我们还要思考这个gap应该如何取值？

首先，还是要有这个意识：
gap越大，大的值更快调到后面，小的值更快调到前面，越不接近有序。
gap越小，大的值更慢调到后面，小的值更慢调到前面，越接近有序。
当gap为1，就是直接插入排序。

  因此，gap的值应该不是固定的，应该随着n的值而变化，这里我建议先设计为n，进入循环后再 gap /= 2，循环条件为gap > 1

void ShellSort(int* arr, int n)
{// 预排序，接近有序// 直接插入排序，有序// 越大的数越快跳到后面，越小的数越快跳到前面int gap = n;while (gap > 1){gap /= 2;for (int i = 0 ; i < n - gap ; i++){ // 减少for循环的个数,每次对不同组进行预排序int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else {break;}arr[end + gap]  = tmp;}}}
}

时间空间复杂度分析

  希尔排序的时间复杂度并不固定，它依赖于所选择的间隔序列（增量序列）。直到今天，已经有多种不同的间隔序列被提出来，每种都有自己的性能特点

《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

空间复杂度为O(1)，在原数组上操作，时间复杂度为O(N^1.25) 到 O(1.6* N^1.25)

总结

1. 时间复杂度：O(N²) -> 很复杂，有多种可能
2. 空间复杂度：O(1)
3. 稳定性：不稳定
4. 复杂性：简单

二、选择排序

基本思想

  选择排序是一种简单直观的比较排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最小（或最大）元素，然后将其放置到未排序序列的起始位置，这个过程一直重复直至整个数组被排序

实现思路

1. 从数组的当前未排序部分选择最小（或最大）的一个元素
2. 将这个最小（或最大）元素与未排序序列的第一个元素交换位置
3. 然后从剩余未排序的元素中继续这个过程，将每一次找到的最小（或最大）元素放到未排序序列的开始
4. 这个过程一直进行到整个数组的所有元素都被排为有序状态

  其实我们还可以再优化一下，既要找到最小，又要找到最大，然后一个跟头交换，一个跟尾交换，这样能有一个常数级别的优化

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void SelectSort(int a[], int n)
{int begin = 0;int end = n - 1;while (begin < end){int maxi = begin;//找最大值的下标int mini = begin;//找最小值的下标for (int i = begin + 1; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);Swap(&a[end], &a[maxi]);begin++;end--;}
}

1. 首先初始化两个索引begin和end，分别代表当前未排序序列的开始和结束位置。
2. 进入一个循环，条件是begin < end，确保在数组中还有未排序的元素。
3. 遍历一遍序列，找到最大元素和最小元素的下标。
4. 将最小元素与序列的始端交换，最大元素与序列的尾端交换。
5. 更新begin与end

可是我们要思考这样书写会不会有问题，事实上是有的：

因为这里我们是首先进行最小元素与首位置更换，再进行最大元素与末尾更换，如果我的最大元素就在首位置就会有问题

  本来找到了最大值和最小值的下标，头跟最小值交换位置，最大值被交换走了，可是最大值的下标还是没变，仍然指向头，所以要加个判断，如果最大值是begin的话，我们把最大值的下标改为最小值的下标

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void SelectSort(int a[], int n)
{int begin = 0;int end = n - 1;while (begin < end){int maxi = begin;//找最大值的下标int mini = begin;//找最小值的下标for (int i = begin + 1; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);//最大值的位置跟最小值重合//mini被换到maxi位置时  原本的最大值则是miniif (maxi == begin)maxi = mini;Swap(&a[end], &a[maxi]);begin++;end--;}
}

时间空间复杂度分析

  对于时间复杂度来说，最好、平均、最坏情况下的时间复杂度都是 O(n^2)，因为不管数组的初始顺序如何，选择排序都需要比较所有未排序的元素来找到最小（或最大）的元素，并执行这个过程 n-1 次（对于 n 个元素的数组），每次选择操作需要比较的次数从 n-1 次减少到 1 次

  对于空间复杂度来说，选择排序是一种原地排序算法，除了输入数组外，它只需要有限的几个变量（比如，用于存储最小元素下标的变量和循环计数器）。因此，它的空间复杂度为常数空间O(1)

总结

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

三、堆排序

  直接参考前文就行：

堆排序的讲解

void AdjustDown(int* arr, int n, int parent)
{// 假设法先选出大的孩子int child = parent * 2 + 1;while (child < n) {if (child + 1 < n && arr[child] < arr[child + 1]){ // child + 1 < n是为了防止右孩子越界child += 1;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}void HeapSort(int* arr, int n)
{// 要升序，建大堆for (int i = (n - 2) / 2 ; i >= 0 ; i--){AdjustDown(arr, n, i);}int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}

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

四、冒泡排序

基本思想

  比较两个相邻的元素，当不满足某一条件时，发生相邻元素的交换，直到整个序列有序为止

序列中两个相邻元素进行比较，当满足条件发生交换操作，导致最小或大元素放到后面位置，不断重复该过程，直到有序

实现思路

  我们的目的是直到有序就停下来，但是上面的逻辑是地毯式查找，对此我们需要设置一个标识变量去标识是否有序，如果不需要交换说明有序直接退出

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int main()
{int arr[10] = { 0 };int sz = sizeof(arr) / sizeof(arr[0]);for (int i = 0; i < sz; i++){scanf("%d ", &arr[i]);///输入数据}int tap = 0;for (int i = 0; i < sz - 1; i++){int flag=1;for (int j = 0; j < sz - 1 - i; j++){if (arr[j] > arr[j + 1]){tap = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tap;flag=0;}}if(flag==1){break;}}for (int i = 0; i < sz; i++){printf("%d ", arr[i]);//打印数据}return 0;
}

总结

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

五、归并排序

基本思想

  归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序序列即先使每个子序列有序，再使子序列间有序。若加你个两个有序表合并成一个有序表，称为二路归并

实现思路

  其实你猜一下就知道这里肯定还要运用到递归~哈哈！

  归并排序主要是通过已有序的子序列合并，得到完全有序的序列。那么将已有序的左右子树得到完全有序的根序列，完成这项操作还需要借助一块空间完成合并，再使用内存函数复制或转移到原本序列中，所以先要排好左边和右边，其实是一种后序

void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right){return ;}int mid = (left + right) >> 1;_MergeSort(arr, left, mid, tmp); 		//排好了左边_MergeSort(arr, mid + 1, right, tmp);	//排好了右边// 归并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = left;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else {tmp[index++] = arr[begin2++];}}while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}// 拷贝回去，在回溯的过程中就要返回
//    for (int i = left ; i <= right ; i++){
//        arr[i] = tmp[i];
//    }memcpy(arr + left, tmp + left, sizeof(int)*(right - left + 1));
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}

总结

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的使解决在磁盘中的外排序问题。
2. 时间复杂度: O(N*logN)
3. 空间复杂度: O(N)
4. 稳定性:稳定
5. 没有进行交换，更加适合外排序

六、计数排序

基本思想

  计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用

void CountSort(int* a, int n)
{int min = a[0], max = a[0];for (int i = 1; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1; // 节省空间，存储数据并不是从0开始，采用相对映射int* count = (int*)calloc(range, sizeof(int));if (count == NULL){printf("calloc fail\n");return;}// 统计次数for (int i = 0; i < n; i++){count[a[i] - min]++;}// 排序int i = 0;for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;//加回去}}
}

总结

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)

---

总结

  是不是被排序这一高深的学问给吓到了？哈哈，别急，下篇我会介绍一种最常用的排序算法，它有很多变式，也很美妙~