- 在线时间
- 514 小时
- 最后登录
- 2023-12-1
- 注册时间
- 2018-7-17
- 听众数
- 15
- 收听数
- 0
- 能力
- 0 分
- 体力
- 39393 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 12513
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1388
- 主题
- 1158
- 精华
- 0
- 分享
- 0
- 好友
- 15
TA的每日心情 | 开心 2023-7-31 10:17 |
---|
签到天数: 198 天 [LV.7]常住居民III
- 自我介绍
- 数学中国浅夏
|
无C不行,废物一个,算法导论:C语言
% N8 w5 _ @3 W( q: }直接插入排序法 原理:从无序数列向左遍历,从有序数组向左比较
* g6 s8 b; V0 y/ ^" c% d7 f2 W//插入排序法
; g. R8 O( w' Z. O5 O# `void straightsort(int*arr,int len)2 x2 e+ S1 @8 @$ F- _
{
/ N8 Q' L3 r9 T, f int temp,i,j;
3 F2 \% O7 Z5 s, ^% C for(i=1;i<len;i++)//将首元素看成有序数组,i=1表示从第二个元素开始排序( Z! j2 k9 l1 H$ u$ c
{; Z4 x* Z; ^2 W/ E5 D
temp=arr;//temp存放待插入元素- S! X/ [) }& n1 N. @- C
for(j=i-1;j>=0&&arr[j]>temp;j--)//待插入元素向左比较,arr[j]代表已经排序的有序数组,满足j>=0,且arr[j]>temp" l* Y( y, O: A2 u4 r, e
{; `) x! ~+ k( I1 {2 z# @7 x
arr[j+1]=arr[j];//若条件成立,则将已排序数组向右移位,arr[j]最大可达arr处,即temp处 t3 d$ t# d" D, o& s
}
/ E U* R* B* f# }2 T Z arr[j+1]=temp;//当循环不成立或循环终止,此时arr[j]<=temp(或j=-1,所有有序数组都大于待排元素,)temp应位于arr[j+1]处,j随temp左移而发生变化(减小)8 p5 v3 U0 `; V4 F# K3 K
}0 o9 H! @# c: T7 t
}, \- b/ o+ G1 I3 e" S: [
9 L/ c! x2 R, s8 S+ v
归并排序法 将一个数组从中间分为两部分,再分别对两部分进行排序(递归),最后将排好序的两部分对比合并
4 Z/ }# ]6 ], h//归并排序法
: M9 ?: ?. P" y* b1 M3 zvoid merge_sort(float data[],int left,int right,float sorted_data[])6 m+ L. Q" w/ `0 n( c# d
{) A9 @9 u. W, h' L5 N' Q
if(left<right)//排除原数组出现只有一个数据的情况(left=right)
) @7 X" f5 V& M" s {% y/ L8 |) u& L1 ? X
int mid=(left+right)/2;
2 T3 ~- m* `/ N' c$ i) E merge_sort(data,left,mid,sorted_data);
/ F; Q& d @7 h; k h% E merge_sort(data,min+1,right,sorted_data);
$ A& N2 M& \5 L2 |- L8 i# u merge_array(data,left,mid,right,sorted_data);6 \8 E0 [) m7 Y6 H
}
/ W' x6 j8 f4 ~/ s# r}
& x3 {6 [3 u. B) xvoid merge_array(float data[],int left,int mid,int right,float temp[])//data[]即待排子数组,直接用子数组排序,但将子数组分为两部分,temp[]即临时数组
+ |( O) h& M" |( X' p# B2 T3 D{
0 v. J- p9 \. Y! T& M int i=left,j=mid+1;
N, X$ [- ^/ x6 u; Q' B int k=0;
s+ V. o1 h, B* f: n4 S while(i<=mid&&j<=right)//循环条件,将较小数组放入临时数组temp[]中,同时i变为data[i+1]或j变为data[j+1]
- W# I- H$ ^ b2 g {, F: g* ?! u. B, ^: O1 O o
if(data<=data[j])
/ I0 z7 x, B3 h# k. U9 a6 ` {# y( g/ i2 t; m* Q
temp[k++]=data[i++];
; }; r6 _5 k c: H- `$ L }7 e U+ a5 [. J' i
else' [# I4 W2 f! E* j5 U) c7 E
temp[k++]=data[j++];
" f" g6 a) y3 Q% @/ O: Y: r }, C7 q% o( ~& ~; z( W" ~
while(i<=mid)//以下两个while代表可能出现的特殊情况:i/j所在数组已经全部完成排序,但另一数组仍有>=1的元素未放入临时数组中
& _6 W+ l7 k+ K* ]4 S U1 N2 t1 U temp[k++]=data[i++];
7 g9 k! H5 }6 m: L while(j<=right)
7 t; m6 V7 Y2 D& _. [ temp[k++]=data[j++];; M. u# K2 N# W1 Y
for(i=0;i<k;i++)//将临时数组中的元素全部放入原数组中,k=right-left,k代表了数组长度
* [0 k G3 z6 U data[left+i]=temp;. D. U1 ~; h+ x F4 x& I) z0 O j
}+ W( z- K+ T* N/ a+ c
void merge_array(float data[],int left,int mid,int right,float temp[])//哨兵简化
' `) r, u( y. v; y- F0 H{" }! a V- N3 U
int max_num=INT_MAX;
! u/ h& |! W' Y. Z int len=right-left+1;
! I; |5 T A# n3 |7 }# R int data_left=new int [mid-left+2];3 \4 X* q0 t8 h
int data_right=new int [right-mid+1];
+ E" R4 R+ u4 h" m/ \) ` int i=0,j=0,k=0;! |1 a4 I6 k7 E' g/ q" F7 V- T
for(int k=left;k<=mid;k++)
+ l4 Y; V2 S! R3 i: t5 a0 \ data_left[k-left]=data[k];- R8 [/ s" H% ^/ {! C& I
data_left[k-left]=max_num;# \; x1 \; Y4 h& P* G% T# H
for(int k=mid+i;k<=right;k++). s3 `7 y3 P3 _! Y
data_right[k-mid-1]=data[k];
Z& j# ]! W K# g data_right[k-mid-1]=max_num;0 n* V( o& C+ p( U
for(int k=0;k<len;k++)) b5 p8 B( y* S; Q8 C" E, Y3 ]
{5 {8 Q" J' \ \1 {2 \& m8 P
if(data_left<=data_right[j])( ?6 k4 G% Z9 O. O1 q
data[k+left]=data_left[i++];
' ^! @( A o3 w# |4 p else
, L7 a5 [: _1 {6 y8 z; t" S data[k+left]=data_right[j++];" U6 ]8 L6 l; k3 p. |
}* W+ p: p. ^3 K$ ] r* f/ q
}) L+ Y, o V( }8 f& |4 B. l
* f" l' g0 ]( J( M2 {
3 n1 S& S/ N- L' W- B @: w |
zan
|