- 1Github 2024-06-26 C开源项目日报 Top10
- 2鸿蒙OS开发实例：【ArkTS类库异步并发简述Promise】_鸿蒙开发[object promise]
- 3小白篇--如何在本地搭建 go环境
- 4Linux系统资源监控nmon工具下载及使用介绍_linux 在线下载 nmon
- 5第七篇：微信小程序的跳转页面_小程序跳转页面
- 6使用supportFragmentManager管理多个fragment切换_the fragment supportrequestmanagerfragment{45c75e5
- 7Linux中永久挂载_linux永久挂载
- 8数电（第一章 数制和码制）_数电第一章
- 9基于STM32单片机智能无人机姿态检测MPU6050陀螺仪角度设计23-179_单片机控制陀螺仪
- 10基于Visual Studio Code搭建Python开发环境_vscode配置python开发环境_visual studio code python
数据结构之内部排序总结_数据结构内部排序总结
赞
踩
排序
排序算法小结
若待排序的元素个数较小（小于50），可以直接插入排序或者简单选择排序.
若文件的初始状态已按关键基本有序，则选用直接插入或冒泡排序
若排序元素较大，应该采用时间复杂度为O(nlog₂n)的排序：快速排序、堆排序、归并。其中快速平均时间最短，堆辅助空间小于快速排序，不会出现快速排序的最坏情况，但是二者都不稳定。若是要求排序稳定，选择归并排序。
任何借助比较的排序算法至少需要O（nlog₂n）的时间
若n很大，记录的关键字位数又比较小且可以分解，采用基数排序较好。
当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。
对n个整数排序，在最坏的情况能保证以少于O(n)的时间完成
**排序的稳定性,**就是指,在对a关键字排序后会不会改变其他关键字的顺序
替换选择法是外排序中用于生成更长有序段的方法
- 插入排序
*简单插入排序(在待排序序列局部有序时，效率最高)
思想：将整个数组a分为有序和无序的两个部分。开始有序的部分只有a[0] , 其余都属于无序的部分。每次取出无序部分的第一个（最左边）元素，把它加入有序部分。假设插入合适的位置p，则原p位置及其后面的有序部分元素都向右移动一个位置，有序的部分即增加了一个元素。一直做下去，直到无序的部分没有元素。
#include<stdio.h> void Insert(int a[],int n) { int i,j,temp; for(i=1;i<n;i++) { temp=a[i]; for(j=i;(j>0)&&(temp<a[j-1]);j--) a[j]=a[j-1];//依次与已排序元素比较并右移 a[j]=temp; } for(int i=0;i<n;i++) { printf("%d ",a[i]); } } int main() { int n; scanf("%d",&n); int a[n]; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } Insert(a,n); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
*希尔排序
思想：算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。 一般的初次取序列的一半为增量,以后每次减半,直到增量为1。
#include<stdio.h> void ShellInsert(int a[],int n,int c[])//c为增量序列 { int D,i,P,S; int tmp; for(S=0;c[S]>=n;S++)//初始增量不超过待排序的序列长度 { for(D=c[S];D>0;D=c[S++]) { for(P=D;P<n;P++) { tmp=a[P]; for(i=P;i>=D&&a[i-D]>tmp;i-=D) a[i]=a[i-D]; a[i]=tmp; } } } for(i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } int main() { int n,a[100],c[5]={7,5 ,3,2,1}; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } ShellInsert(a,n,c); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 选择排序（时间复杂度与初始排序序列无关)
*简单选择排序（与冒泡排序的思想恰好相反）
思想：如果有N个元素需要排序，那么首先从N个元素中找到最小的那个元素与第0位置上的元素交换然后再从剩下的N-1个元素中找到最小的元素与第1位置上的元素交换，之后再从剩下的N-2个元素中找到最小的元素与第2位置上的元素交换，…直到所有元素都排序好
对N个记录进行简单选择排序，比较次数和移动次数分别为O(N^)和O(N)
经过一趟选择排序：将最小的放在数组前端
#include<stdio.h> void selectionSort(int a[], int n) { int i,k,j,temp; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(a[j]<a[k]) k=j; if(k!=j) { temp=a[i]; a[i]=a[k]; a[k]=temp; } } for(i=0;i<n;i++) printf("%d ",a[i]); } int main() { int n,a[100]; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } selectionSort(a,n); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
*堆排序
思想：
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
分为两步：
1，构造最大堆
2，进行堆排序
#include<stdio.h> void Adjust(int a[],int i,int n) {//构造堆 int child,temp; for(temp=a[i]; (2*i+1)<n; i=child) { child=2*i+1; if((child!=n-1)&&(a[child+1]>a[child])) child++;//符合堆的构造 if(temp<a[child]) a[i]=a[child];//交换堆顶与子节点 else break; } a[i]=temp; } void HeapSort(int a[],int n) { int i,temp; for(i=(n-1)/2; i>=0; i--) Adjust(a,i,n);//首先遍历各个节点调整一次堆 for(i=n-1; i>0; i--) { temp=a[0]; a[0]=a[i]; a[i]=temp; Adjust(a,0,i);//不断更新堆顶元素 } } int main() { int n,i; scanf("%d",&n); int a[n]; for(i=0; i<n; i++) scanf("%d",&a[i]); HeapSort(a,n); for(i=0; i<n; i++) printf("%d ",a[i]); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 交换排序（核心：消除逆序）
冒泡排序(与选择排序的思想恰好相反）
思想：比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。
> N个数字要排序完成，总共进行N-1趟排序，每进行一趟排序，就会少比较一次，每进行一趟排序都会找出一个较大值，放在数组的后面
经过一趟冒泡排序：找到一个较大值放在数组尾
#include<stdio.h> void bubblesort(int a[],int n) { bool flag; for(int i=n-1;i>=0;i--)//注意：使用数组下标从后向前比较 { flag=false; for(int j=0;j<i;j++) { if(a[j]>a[j+1]) { int x; x=a[j]; a[j]=a[j+1]; a[j+1]=x; flag=true; } } if(flag==false) break; } for(int i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } int main() { int n; scanf("%d",&n); int a[n]; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } bubblesort(a,n); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
*快速排序（排序趟数与序列的原始状态有关）
思想：快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
1、先从数列中取出一个数作为基准数
2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
3、再对左右区间重复第二步，直到各区间只有一个数
特点：经过一次快速排序后元素将呈现：
每一趟确定一个值的位置，比它大的在右边，小的左边，然后分成两个数组接着排
即从后往前将比关键字小的放在前面
从前往后将比关键字大的放在后面
经过一趟快排
//对数组进行快排 #include<stdio.h> void quicksort(int a[],int first,int end) {//快排核心 int i,j,temp; i=first; j=end; temp=a[i]; while(i<j) { while(i<j&&temp<=a[j]) j--;//从右向左判断确保数值比标准值大 a[i]=a[j]; while(i<j&&temp>=a[i]) i++;//从左向右判断确保数值比标准值小 a[j]=a[i]; } a[i]=temp; if(first<i-1) quicksort(a,first,i-1); if(end>i+1) quicksort(a,i+1,end); } void Qsort(int a[],int n) {//快排实现 for(int i=0;i<n;i++) quicksort(a,0,n-1); for(int i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); } int main() { int n,a[100],i; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); Qsort(a,n);//最终用排序函数实现输出 return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
方法二
（优）
//确定枢轴的位置 int quick(int a[],int l,int h) { int i=l,j=h; int temp=a[l]; while(i!=j) { if(i<j&&a[j]>=temp) j--; a[i]=a[j]; if(i<j&&a[i]<=temp) i++; a[j]=a[i]; } a[i]=temp; return i;//返回该位置 }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
//排序
void sort(int a[],int l,int h)
{
if(l<h)
{
int t=quick(a,l,h);
sort(a,l,t-1);
sort(a,t+1,h);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
//输出结果
void print(int a[],int n)
{
printf("%d",a[0]);
for(int i=1;i<n;i++)
printf(" %d",a[i]);
printf("\n");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 基数排序
思想：
利用桶排序：首先定义10个“桶”，下标为0~9，且只能用“队列”来定义，这里后面会有解释；然后遍历数组，按照元素的“个位”数值，依次放入对应下标的桶中，放完所有元素后，从第0个桶开始遍历，以此取出桶中元素按顺序放入原始数组中；同理，之后再遍历数组，按照元素的“十位”数值，做上一步相同的操作；以此类推，直到按照数组中最大元素的最高位操作完为止。
#include<stdio.h> #define MAX 20 #define BASE 10 void print(int *a, int n) { int i; for (i = 0; i < n; i++) { printf("%d\t", a[i]); } } void radixsort(int *a, int n) { int i, b[MAX], m = a[0], exp = 1; for (i = 1; i < n; i++) { if (a[i] > m) { m = a[i]; } } while (m / exp > 0) { int bucket[BASE] = { 0 }; for (i = 0; i < n; i++) { bucket[(a[i] / exp) % BASE]++; } for (i = 1; i < BASE; i++) { bucket[i] += bucket[i - 1]; } for (i = n - 1; i >= 0; i--) { b[--bucket[(a[i] / exp) % BASE]] = a[i]; } for (i = 0; i < n; i++) { a[i] = b[i]; } exp *= BASE; #ifdef SHOWPASS printf("\nPASS : "); print(a, n); #endif } } int main() { int arr[MAX]; int i, n; printf("Enter total elements (n <= %d) : ", MAX); scanf("%d", &n); n = n < MAX ? n : MAX; printf("Enter %d Elements : ", n); for (i = 0; i < n; i++) { scanf("%d", &arr[i]); } printf("\nARRAY : "); print(&arr[0], n); radixsort(&arr[0], n); printf("\nSORTED : "); print(&arr[0], n); printf("\n"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 归并排序
一趟二路归并
思想：将序列两两分组，将序列归并为[n/2]个组，组内单独排序；然后将这些组再两两归并，生成[n/4]个组，组内再单独排序；以此类推，直到只剩下一个组为止，其核心在于如何将两个有序序列合并成一个有序序列。
#include<stdio.h> //合并算法 void Merge(int a[],int left,int mid,int right,int b[]) { //将有序的a[left]~a[mid-1]和 a[mid]~a[right] 归并成一个有序序列 //存放在辅助数组b中,b的下标从left开始 int i,j,k; i=left; j=mid+1; k=left; while((i<=mid)&&(j<=right)) { if(a[i]<=a[j]) { b[k]=a[i];i++; } else{ b[k]=a[j];j++; } k++; } //有一个有序数组已完成排序工作 while(i<=mid) { b[k]=a[i]; k++;i++; } while(j<=right) { b[k]=a[j]; k++;j++; } } // 归并排序算法 void MSort(int a[],int left,int right,int c[]) { //数组a[]经排序后存放在数组c中 int b[100];//b为辅助数组 if(right==left)//只有一个数，不用排序 c[left]=a[left]; else { int mid; mid=(left+right)/2; MSort(a,left,mid,b);//递归将左侧排序 MSort(a,mid+1,right,b);//将右侧派苏 Merge(b,left,mid,right,c);//将数组b的左右两个有序子序列合并 } } int main() { int n; scanf("%d",&n); int a[n],c[n]; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } MSort(a,0,n-1,c); for(int i=0;i<n;i++) printf("%d ",c[i]); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
