常见排序算法

前言

欢迎再次来到小鸥的博客，本系列总结了直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、~~快速排序、归并排序~~、计数排序八种（基数排序和桶排序不做演示）常见排序的原理，并使用C语言再现，

快排和归并由于实现方法有多种，篇幅较长，将单独在第二篇讨论

下篇：快排和归并-CSDN博客

本期专栏：算法_海盗猫鸥的博客-CSDN博客

个人主页：海盗猫鸥-CSDN博客

本篇中代码使用C，且数据序列使用数组为例

直接插入排序

原理解析：（升序）

当插入第 i(i>=1)个数时，前i-1个数已经有序，用arr[i]依次与arr[i-1],arr[i-2]...比较，若arr[i]小于比较数，则将次位置的数据向后挪动一位，直到arr[i]大于比较数，将arr[i]插入此位置；

每次完成一轮排序，前i-1个数都是有序的

void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){//[0,end]都为有序，向前插入数据；int end = i;//存储待插入数据int tmp = arr[end + 1];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}

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

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

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

当序列中的数据越接近倒序，直接插入排序的效率就越低，直到完全为倒序时，时间复杂度降低为O(N)

由此希尔排序是对直接插入排序的优化，可以防止上述情况

原理解析：

1.预排序（让数组接近有序）；

直接插入排序中，每次插入的都是紧邻着的下一个位置的数据

预排序将数组中数据，按照(i，i+gap，i+2*gap...，i+n*gap)的形式，将数组分为gap组；

分别对这些组进行插入排序

2.插入排序

预排序后，最后进行直接插入排序，

代码中gap取值不止一个，而是按照三分之一的规律减小

代码：

void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1)//gap为1时就是一次直接插入排序{//gap > 1时为预排序//gap == 1是插入排序gap = gap / 3 + 1;//加1保证最后一次为直接插入排序for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序，这样插入排序就会很快。整体而言，可以达到优化的效果。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，记：O(N^1.3)即可；
空间复杂度：O(1)；
稳定性：不稳定

直接选择排序

begin和end分别指向数组开头和末尾，使用mini和maxi来遍历寻找最大最小值，将最大最小值分别end和begin的值交换；

完成一次后最小值在数组最前面，最大值在数组最后面；begin++，end--进行下一轮循环，找到剩余数据中的最大最小值，如此循环；

代码：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//选择排序O(N^2)
void SelectSort(int* arr, int n)
{//最大最小值所在下标int mini;int maxi;int begin, end;mini = begin = 0;end = maxi = n - 1;//每次遍历存储找到最大最小值的位置while (begin < end){mini = begin;maxi = end;for (int i = begin + 1; i <= end; i++){if (arr[i] < arr[mini]){mini = i;}if (arr[i] > arr[maxi]){maxi = i;}}//交换begin和miniSwap(&arr[begin], &arr[mini]);//若begin本来是最大值，则maxi指向begin位置，且上述交换后，mini位置变为了最大值，begin位置变为了最小值//重新调整maxi指向if (begin == maxi)maxi = mini;Swap(&arr[end], &arr[maxi]);++begin;--end;}
}

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

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

堆排序

使用数据结构堆的向上调整和向下调整算法来模拟建堆，然后用向下调整排序

//向上调整
void AdjustUp(HPDataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent])//小堆{Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);//默认左孩子小int child = (parent * 2) + 1;//孩子元素的下标while (child < n){//让child指向左右孩子中小的一方if (child + 1 < n && a[child + 1] < a[child]){//右孩子小child++;}//判断孩子是否小于父亲节点，再交换if (a[child] < a[parent])//<是小堆，>是大堆{Swap(&a[child], &a[parent]);parent = child;child = (parent * 2) + 1;}else//孩子不小于父亲，即满足堆的结构，直接跳出调整函数{break;}}
}

堆排序

降序，建小堆
原理：小堆的top一定是最小值，将top和最后的元素交换，最小值就成为了顺序结构的最后一个元素
再进行向下调整，将除开最后一个元素以外的最小值放到top位置，循环可得降序

升序，建大堆

原理：大堆的top一定是最大值，将top和最后的元素交换，最大值就成为了顺序结构的最后一个元素
再进行向下调整，将除开最后一个元素以外的最大值放到top位置，循环可得升序

//堆排序
void HeapSort(HPDataType* a,int n)
{//降序，建小堆// 小堆的top一定是最小值，将top和最后的元素交换，最小值就成为了顺序结构的最后一个元素// 再进行向下调整，将除开最后一个元素以外的最小值放到top位置，循环可得降序//升序，建大堆//降序//向上调整，将数组视为完全二叉树，使其成为小堆//for (int i = 1; i < n; i++)//{//	AdjustUp(a, i);//}//向下调整，从倒数第一个非叶子节点开始（父节点），向下调整，建小堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);end--;}
}

堆排序的特性总结：

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

冒泡排序

以升序为例：

前后两个数据比较，将大的换到后一个数位置，循环一次就将最大的数据放到了数组的位置；

循环n次，待排序的数就减少n个（最后n个数据已经排序完成）；

// 冒泡排序
void BubbleSort(int* a, int n)
{//前后交换，每一轮将最大的放到最后//n个数循环n轮完成排序for (int i = 0; i < n - 1; i++)//第n轮只有第一个数，不需要交换{int flag = 0;for (int j = 1; j < n - i; j++)//j从1开始，所以结束的范围要比从0开始+1即n-i，而不是n-1-i;{if (a[j - 1] > a[j])//大的往后换{int tmp = a[j - 1];a[j - 1] = a[j];a[j] = tmp;flag = 1;}}if (flag == 0)break;}

冒泡排序的特性总结：

冒泡排序是一种非常容易理解的排序（教学意义）
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

计数排序（非比较排序）

使用额外开辟的数组count来统计每个数据出现的次数，并将数据的大小和count数组中的下标大小进行对应的映射。再将数据传回原序列即可。

图解：

代码：

//计数排序
//只适用于整数
void CountSort(int* arr, int n)
{int max = arr[0], min = arr[0];//假设最大最小值for (int i = 0; i < n; i++){if (arr[i] > max)max = arr[i];if (arr[i] < min)min = arr[i];}//范围int range = max - min + 1;//最大值到最小值的区间,代表count数组的空间大小//创建count数组记录每个数的出现次数int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail!");return;}//相当于遍历arr数组，计数到count数组中for (int i = 0; i < n; i++){count[arr[i]-min]++;//假设min = 100，那么当arr[i]=101时相对下标就是1，即arr[i]-min//数的大小映射count数组中的相对下标位置}//遍历count数组，将数据赋值返还给arrint j = 0;for (int i = 0; i < range; i++){//每个数有多少个，就放回arr中多少个while (count[i]--){arr[j++] = i + min;}}free(count);count = NULL;
}

计数排序的特性总结：