文章目录
- 前言
- 一、希尔排序( 缩小增量排序 )
- 基本思想
- 实现思路
- 时间空间复杂度分析
- 总结
- 二、选择排序
- 基本思想
- 实现思路
- 时间空间复杂度分析
- 总结
- 三、堆排序
- 四、冒泡排序
- 基本思想
- 实现思路
- 总结
- 五、归并排序
- 基本思想
- 实现思路
- 总结
- 六、计数排序
- 基本思想
- 总结
- 总结
前言
承上启下,正文开始!
一、希尔排序( 缩小增量排序 )
希尔排序是一种基于插入排序的算法,通过引入增量的概念来改进插入排序的性能
基本思想
通过预排序使得无序接近有序序列,大体流程:先选定一个整数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)
总结
- 时间复杂度:O(N²) -> 很复杂,有多种可能
- 空间复杂度:O(1)
- 稳定性:不稳定
- 复杂性:简单
二、选择排序
基本思想
选择排序是一种简单直观的比较排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最小(或最大)元素,然后将其放置到未排序序列的起始位置,这个过程一直重复直至整个数组被排序
实现思路
- 从数组的当前未排序部分选择最小(或最大)的一个元素
- 将这个最小(或最大)元素与未排序序列的第一个元素交换位置
- 然后从剩余未排序的元素中继续这个过程,将每一次找到的最小(或最大)元素放到未排序序列的开始
- 这个过程一直进行到整个数组的所有元素都被排为有序状态
其实我们还可以再优化一下,既要找到最小,又要找到最大,然后一个跟头交换,一个跟尾交换,这样能有一个常数级别的优化
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--;}
}
- 首先初始化两个索引begin和end,分别代表当前未排序序列的开始和结束位置。
- 进入一个循环,条件是begin < end,确保在数组中还有未排序的元素。
- 遍历一遍序列,找到最大元素和最小元素的下标。
- 将最小元素与序列的始端交换,最大元素与序列的尾端交换。
- 更新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)
总结
- 选择排序思考非常好理解,但是效率不是很好。实际中很少使用。
- 时间复杂度:O(N^2)
- 空间复杂度:O(1)
- 稳定性:不稳定
- 复杂性:简单
三、堆排序
直接参考前文就行:
堆排序的讲解
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--;}
}
- 堆排序使用堆来选数,效率就高了很多。
- 时间复杂度:O(N*logN)
- 空间复杂度:O(1)
- 稳定性:不稳定
四、冒泡排序
基本思想
比较两个相邻的元素,当不满足某一条件时,发生相邻元素的交换,直到整个序列有序为止
序列中两个相邻元素进行比较,当满足条件发生交换操作,导致最小或大元素放到后面位置,不断重复该过程,直到有序
实现思路
我们的目的是直到有序就停下来,但是上面的逻辑是地毯式查找,对此我们需要设置一个标识变量去标识是否有序,如果不需要交换说明有序直接退出
#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;
}
总结
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度: O (N2)
- 空间复杂度: O(1)
- 稳定性:稳定
五、归并排序
基本思想
归并排序(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);
}
总结
- 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的使解决在磁盘中的外排序问题。
- 时间复杂度: O(N*logN)
- 空间复杂度: O(N)
- 稳定性:稳定
- 没有进行交换,更加适合外排序
六、计数排序
基本思想
计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用
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;//加回去}}
}
总结
- 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
- 时间复杂度:O(MAX(N,范围))
- 空间复杂度:O(范围)
总结
是不是被排序这一高深的学问给吓到了?哈哈,别急,下篇我会介绍一种最常用的排序算法,它有很多变式,也很美妙~