liyuxia713

蹣跚前行者

導(dǎo)航

<

2009年4月

>

日

一

二

三

四

五

六

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

24

29

30

1

2

3

4

5

6

7

8

9

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

隨筆 - 50
文章 - 0
評(píng)論 - 32
引用 - 0

Algorithms

lzmagic (rss)
正在更新數(shù)據(jù)結(jié)構(gòu)中的一些經(jīng)典算法
第四維空間
數(shù)據(jù)結(jié)構(gòu) 算法
極限定律
算法

C++

鷹之夢(mèng)園
C++ Primer 學(xué)習(xí)筆記

基本排序算法及分析（一）：插入排序，直接選擇排序

聲明待排序元素類型

1

/*--------------------------
2

typedef.h
3

方便修改待排序元素類型
4

-------------------------------------*/
5

#ifndef TYPEDEF_H
6

#define TYPEDEF_H
7

8

typedef int T;
9

10

#endif

插入排序：

1

/*---------------------------------------------------------------------------------------
2

Insertion_sort.h
3

直接插入排序
4

對(duì)以數(shù)組形式給出的元素排序
5

時(shí)間復(fù)雜度為(逆序數(shù))N(N-1)/4 = O(N^2),并且在最壞情形下達(dá)到這個(gè)值
6

最好情形下運(yùn)行N次，最壞情形下運(yùn)行2+3+…+N
7

------------------------------------------------------------------------------------------------*/
8

9

#ifndef INSERTION_SORT_H
10

#define INSERTION_SORT_H
11

12

#include "typedef.h"
13

//直接插入排序
14

void Insertion_sort(T *a, int n)
15

{
16

for(int i = 1; i != n; ++i)
17

{
18

T temp = a[i];
19

int j = i - 1;
20

for(; j >= 0 && temp < a[j]; --j )
21

a[j + 1] = a[j];
22

a[j + 1] = temp;
23

}
24

}
25

26

#endif

直接選擇排序：

1

/*----------------------------------------------
2

DirectSelection_sort.h
3

直接選擇排序
4

時(shí)間復(fù)雜度O(N^2)
5

--------------------------------------------------------*/
6

#ifndef DIRECTSELECTION_SORT_H
7

#define DIRECTSELECTION_SORT_H
8

9

#include "typedef.h"
10

#include "swap.h"
11

12

//直接選擇法排序
13

void DirectSelection_sort(T*a, int n)
14

{
15

for(int i = 0; i != n; ++i)
16

{
17

int k = i;
18

for(int j = i; j != n; ++j)
19

if(a[j] < a[k]) k = j;
20

swap(a[k],a[i]);
21

}
22

}
23

24

#endif

posted on 2009-04-22 16:44 幸運(yùn)草閱讀(841) 評(píng)論(0) 編輯收藏引用所屬分類: Algorithms

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


相關(guān)文章: 基本排序方法及分析（九）：Randomized-Quicksort快速排序的隨機(jī)化版本 Order Statistics 順序統(tǒng)計(jì)（找出第i小元素）基本排序方法及分析（八）：CoungtingSort 計(jì)數(shù)排序基本排序方法及分析（七）：HeapSort 堆排序同時(shí)求最大最小值基本排序算法及分析（六）：桶式排序基本排序算法及分析（五）：歸并排序基本排序算法及分析（四）：快速排序基本排序算法及分析（三）：shell排序基本排序算法及分析（二）：冒泡排序

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

liyuxia713

導(dǎo)航

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

Algorithms

C++

最新評(píng)論

基本排序算法及分析（一）：插入排序，直接選擇排序