查看: 4364|回复: 2

无C不行-废物一个-算法导论：C语言

字体大小: 正常放大

1178 主题	15 听众	1万积分

TA的每日心情

	开心 2023-7-31 10:17

签到天数: 198 天

[LV.7]常住居民III

自我介绍: 数学中国浅夏

电梯直达

1^#

发表于 2021-11-28 01:29 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

无C不行，废物一个，算法导论：C语言

直接插入排序法

原理：从无序数列向左遍历，从有序数组向左比较

//插入排序法
void straightsort(int*arr,int len)
{
int temp,i,j;
for(i=1;i<len;i++)//将首元素看成有序数组，i=1表示从第二个元素开始排序
{
temp=arr;//temp存放待插入元素6 k6 S2 C: C- Y
for(j=i-1;j>=0&&arr[j]>temp;j--)//待插入元素向左比较，arr[j]代表已经排序的有序数组，满足j>=0,且arr[j]>temp
! T3 R* }7 ], }+ e* S. v {2 n5 Y- G3 t- I  |2 v
arr[j+1]=arr[j];//若条件成立，则将已排序数组向右移位，arr[j]最大可达arr处，即temp处
" j, N0 {3 O4 @/ ~+ p/ [5 C }
0 u, {, ~& W( W% m4 r4 Q arr[j+1]=temp;//当循环不成立或循环终止，此时arr[j]<=temp（或j=-1，所有有序数组都大于待排元素,）temp应位于arr[j+1]处，j随temp左移而发生变化（减小）; o) T, K' }% \- j$ J* Y
}# r( u6 B; ]4 `( P+ ]. R& v  [
}
7 y! A6 B' d7 L% M5 \) s+ V9 f( {$ O  o8 \) j

归并排序法
将一个数组从中间分为两部分，再分别对两部分进行排序（递归），最后将排好序的两部分对比合并
- G. O! n$ t8 e9 q) ~% i
//归并排序法- p% p8 {9 `8 x* q: @" T7 ]2 |
void merge_sort(float data[],int left,int right,float sorted_data[])
) B6 C8 h0 B* j" [{# t0 K- W0 ]! ]3 H1 b( g8 }
if(left<right)//排除原数组出现只有一个数据的情况(left=right)
) ]6 G* u- X9 K$ c {9 n# s6 p# u4 s% |
int mid=(left+right)/2;2 S) _# W) c& J) Z+ I; |6 C. G
merge_sort(data,left,mid,sorted_data);
# J  w7 k% R9 T2 Q merge_sort(data,min+1,right,sorted_data);) }2 n0 }+ {" B4 M! D' e) n
merge_array(data,left,mid,right,sorted_data);
6 Q3 ]9 b0 w% X: B: Y }- @; d% m4 s7 e
}
5 Y3 _3 L/ {& R* V# |) n* Q+ avoid merge_array(float data[],int left,int mid,int right,float temp[])//data[]即待排子数组,直接用子数组排序，但将子数组分为两部分，temp[]即临时数组( I: F% w: t0 a: b) p* m2 s# R, F6 z
{
, {" S# r6 h/ H; O int i=left,j=mid+1;" J4 x, x$ K$ G0 J6 L% _
int k=0;" ]+ ]. m5 H8 V1 D4 G
while(i<=mid&&j<=right)//循环条件，将较小数组放入临时数组temp[]中，同时i变为data[i+1]或j变为data[j+1]3 b. l, Z- J  s; K9 S+ b. S
{& _% l+ r; i" i; X$ v, F
if(data<=data[j])
+ D  N# N( j; r. U& G& e {
) h2 I4 p9 E/ O" r" X temp[k++]=data[i++];
4 }  W9 f# b# Q$ J0 ` }2 }% ~. p  V- _2 C1 i0 b* d
else
8 j5 U3 b" N( M temp[k++]=data[j++];- A0 Z+ z2 E! ]& C/ D6 Z
}4 I. H. m1 ]  X
while(i<=mid)//以下两个while代表可能出现的特殊情况：i/j所在数组已经全部完成排序，但另一数组仍有>=1的元素未放入临时数组中' M9 R0 i9 }! |0 s* Z
temp[k++]=data[i++];
: t$ @! L5 g9 ?$ r, n+ L9 C+ N while(j<=right)6 g% x! u. I6 W+ ]- m9 k
temp[k++]=data[j++];% }2 Y4 x9 T2 g! J
for(i=0;i<k;i++)//将临时数组中的元素全部放入原数组中，k=right-left,k代表了数组长度
5 ^1 v# ^/ |1 i" M1 v5 B3 @8 G* Y data[left+i]=temp;" @; T/ w8 W0 s$ T) b. N# }
}
+ F. z  d* @! [  `8 Xvoid merge_array(float data[],int left,int mid,int right,float temp[])//哨兵简化7 Y( V/ r# l0 ?' `7 ^7 q1 e
{) w% o' [* o1 A; Z
int max_num=INT_MAX;
6 f& f. d  U+ c- Z2 P int len=right-left+1;
/ _1 `1 `9 W3 a- [  b: |5 @ int data_left=new int [mid-left+2];
6 h6 F7 a# Q& Z, r- ?# M int data_right=new int [right-mid+1];( ~5 Q4 f- r8 I* @" D, j  j: p
int i=0,j=0,k=0;
# ?3 I: E, N6 [- l% c7 i for(int k=left;k<=mid;k++)
6 I' _- q5 a5 c8 A. ~ data_left[k-left]=data[k];
. H& j' l* ~6 v5 i3 W- T4 o data_left[k-left]=max_num;9 V3 L; p9 T* ]8 l" |( `. j3 s0 v
for(int k=mid+i;k<=right;k++)1 a5 `. \/ W1 F
data_right[k-mid-1]=data[k];7 I' i, e* K# O: i. L* C  h
data_right[k-mid-1]=max_num;
) B% g& M" `: L$ ]  T5 z for(int k=0;k<len;k++)& i" \- G+ [2 D% U. H; S
{
) T3 D( ]' c* _0 T- S if(data_left<=data_right[j]); e& G& k2 d% V
data[k+left]=data_left[i++];- C( I0 J2 v+ }; ?+ `1 U# O
else
' ]: o: o; C! s. O6 C data[k+left]=data_right[j++];
9 a% J  o# n/ @7 _+ I; G }
. @( n. [8 j, V* g}5 ?" D  \% G, f8 s# f+ S
& U4 A8 H& f# k8 K0 F5 W8 y
3 {# a, s1 C2 p# T' I