liyuxia713

蹣跚前行者

常用鏈接

統計

隨筆 - 50
文章 - 0
評論 - 32
引用 - 0

Algorithms

lzmagic (rss)
正在更新數據結構中的一些經典算法
第四維空間
數據結構算法
極限定律
算法

C++

鷹之夢園
C++ Primer 學習筆記

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

聲明待排序元素類型

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

typedef.h
3

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

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

#ifndef TYPEDEF_H
6

#define TYPEDEF_H
7

typedef int T;
9

#endif

插入排序：

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

Insertion_sort.h
3

直接插入排序
4

對以數組形式給出的元素排序
5

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

最好情形下運行N次，最壞情形下運行2+3+…+N
7

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

#ifndef INSERTION_SORT_H
10

#define INSERTION_SORT_H
11

#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

#endif

直接選擇排序：

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

DirectSelection_sort.h
3

直接選擇排序
4

時間復雜度O(N^2)
5

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

#ifndef DIRECTSELECTION_SORT_H
7

#define DIRECTSELECTION_SORT_H
8

#include "typedef.h"
10

#include "swap.h"
11

//直接選擇法排序
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

#endif

posted on 2009-04-22 16:44 幸運草閱讀(829) 評論(0) 編輯收藏引用所屬分類: Algorithms

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

liyuxia713

導航

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

Algorithms

C++

最新評論

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