- 在线时间
- 514 小时
- 最后登录
- 2023-12-1
- 注册时间
- 2018-7-17
- 听众数
- 15
- 收听数
- 0
- 能力
- 0 分
- 体力
- 39436 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 12526
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1388
- 主题
- 1158
- 精华
- 0
- 分享
- 0
- 好友
- 15
TA的每日心情 | 开心 2023-7-31 10:17 |
---|
签到天数: 198 天 [LV.7]常住居民III
- 自我介绍
- 数学中国浅夏
|
无C不行,废物一个,算法导论:C语言6 H9 q2 @6 I* @. l5 u+ T8 m
直接插入排序法 原理:从无序数列向左遍历,从有序数组向左比较 4 L& S$ E2 r6 D! M( Q) C/ i
//插入排序法
8 `7 V' |/ D6 \3 F- ~void straightsort(int*arr,int len)3 N- }" w) y# s# r
{
$ }' d0 t9 s$ k7 \4 n% B2 u* r int temp,i,j;
' _% |; h. w5 f# D: K* u for(i=1;i<len;i++)//将首元素看成有序数组,i=1表示从第二个元素开始排序! h! v# J) | T2 b) U3 ~% {
{& [' C; d& y R
temp=arr;//temp存放待插入元素
8 t! X7 e6 V7 S$ |2 k for(j=i-1;j>=0&&arr[j]>temp;j--)//待插入元素向左比较,arr[j]代表已经排序的有序数组,满足j>=0,且arr[j]>temp& b) q z8 t5 x
{
! H0 c. S8 `+ z9 b3 {; v* e arr[j+1]=arr[j];//若条件成立,则将已排序数组向右移位,arr[j]最大可达arr处,即temp处: w& r& q2 ^8 ?# d7 h* p
}
& X) ~2 s: I# C) {4 m9 G arr[j+1]=temp;//当循环不成立或循环终止,此时arr[j]<=temp(或j=-1,所有有序数组都大于待排元素,)temp应位于arr[j+1]处,j随temp左移而发生变化(减小)* }7 X, d2 j2 z# m9 _+ |4 \
}! H# \2 a$ h2 [ S
}; C) U- y. t0 ?! {' E# [
1 l M5 X1 {! _, H3 k
归并排序法 将一个数组从中间分为两部分,再分别对两部分进行排序(递归),最后将排好序的两部分对比合并 2 z( r: I7 b! R
//归并排序法
" D* [, @2 e" ]7 Uvoid merge_sort(float data[],int left,int right,float sorted_data[])
( Q% S3 o8 w& f{0 L/ H+ [% H/ c* W$ c) U% n
if(left<right)//排除原数组出现只有一个数据的情况(left=right)$ n8 \$ h3 l/ A j4 O
{
. u b% {4 q8 R3 f. n! _0 { int mid=(left+right)/2;
, J$ }: Q/ X, Y merge_sort(data,left,mid,sorted_data);
7 e" P+ Y2 ?' x merge_sort(data,min+1,right,sorted_data);' G: I3 q0 \$ g: m3 s2 x' u
merge_array(data,left,mid,right,sorted_data);
; i2 D/ ]3 l- z3 P }9 B4 G" W# A. [$ T c# C7 @, \
}
T& r4 |/ I; V: v: kvoid merge_array(float data[],int left,int mid,int right,float temp[])//data[]即待排子数组,直接用子数组排序,但将子数组分为两部分,temp[]即临时数组& V( A) v5 W5 S$ x ^% [
{. U1 e) f. K# w) e
int i=left,j=mid+1;1 M1 R5 A4 j# D( Z9 i0 u
int k=0;, B' ^) N* ]8 ?8 ]. B& A7 e
while(i<=mid&&j<=right)//循环条件,将较小数组放入临时数组temp[]中,同时i变为data[i+1]或j变为data[j+1]% y! L8 L0 {! v- b+ R, O/ e% c( C
{
1 @' X8 ?; Y" G/ O+ \6 Y* P if(data<=data[j])
* H; H. h( i5 I: e" u2 M8 X {3 z, @; u1 w' b1 u
temp[k++]=data[i++];5 R0 z% R! \8 B2 w5 u% _
}
, ]* K4 {7 F& }- h1 R! ^ else
0 s( A: v) {. t7 s8 Q0 ~ temp[k++]=data[j++];
9 E5 n/ z& ]9 |4 F% Q }3 b$ x& M, S% X4 }' z+ I
while(i<=mid)//以下两个while代表可能出现的特殊情况:i/j所在数组已经全部完成排序,但另一数组仍有>=1的元素未放入临时数组中
- q6 O8 K& V* i6 r. l temp[k++]=data[i++];
3 d& w7 {% G. c8 P) @/ T while(j<=right)
& K3 ]9 Q c/ _( r8 F temp[k++]=data[j++];" J& I8 a0 ]- u: l9 L, v8 Z
for(i=0;i<k;i++)//将临时数组中的元素全部放入原数组中,k=right-left,k代表了数组长度3 T) w* C2 Q7 w$ b( n
data[left+i]=temp;
+ p7 V: ]+ B% _. m}% |9 s. K8 w6 G& k4 o5 r- ]
void merge_array(float data[],int left,int mid,int right,float temp[])//哨兵简化/ b4 \# W/ ?7 U
{/ V+ g( B# r7 S& |
int max_num=INT_MAX;3 G& @8 T% f0 m: J! S: [* T, q
int len=right-left+1;
& ^) G; \; O( C int data_left=new int [mid-left+2];. F' W( m; q! p' v- {7 o- {3 Y" F9 s2 P
int data_right=new int [right-mid+1];. v+ S, _/ z& i6 K* S- \9 a0 y# d+ y
int i=0,j=0,k=0;
% c' A) N7 ? t; V6 O for(int k=left;k<=mid;k++)
7 E# l( F% o- N. l5 \( f data_left[k-left]=data[k];6 f8 p9 f) `% j+ |* }$ b, f+ k9 }6 [
data_left[k-left]=max_num;% I' u* w1 s, g* o1 L" J! L
for(int k=mid+i;k<=right;k++)
+ d" A% t% p9 ~5 a8 G, r6 t data_right[k-mid-1]=data[k];
# }( m3 N. e0 o$ h+ o y data_right[k-mid-1]=max_num;
; p% Y+ r. A* f* @ for(int k=0;k<len;k++)6 a* A6 c* s' V q9 j% r( F6 ]9 W0 t
{) o- e6 p* M4 v* j6 m r
if(data_left<=data_right[j])0 b+ K8 r* i% i* i: q6 t
data[k+left]=data_left[i++];
- Y9 P/ C* o; @0 r* `" P1 e else8 M% S; P. _3 G4 D4 O% i1 [
data[k+left]=data_right[j++];
& s B# X! f3 t9 j6 P }
. B& G) p" z" D: q8 u6 L, x}
; \$ g* G( c2 I& O: Q
/ M" v6 j, Z- C% S
8 M+ c; J# h$ x$ u% \ |
zan
|