liyuxia713

蹣跚前行者

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

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

Algorithms

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

C++

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

基本排序算法及分析（二）：冒泡排序

冒泡排序和改進的冒泡排序

1

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

Bubble_sort.h
3

冒泡排序：時間復雜度為O(N^2)
4

改進的冒泡排序：時間復雜度仍為O(N^2)
5

一般的冒泡排序方法有可能會在已經排好序的情況下繼續比較，改進的冒泡排序
6

設置了一個哨兵flag，如果一次for循環沒有進行交換，則元素已經排好序，由哨兵控制退出循環。
7

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

#ifndef BUBBLE_SORT_H
9

#define BUBBLE_SORT_H
10

11

#include "typedef.h"
12

#include "swap.h"
13

14

//冒泡排序
15

void Bubble_sort(T *a, int n)
16

{
17

for(int i=n-1; i != 0; --i)
18

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

if(a[j+1] < a[j]) swap(a[j+1],a[j]);
20

}
21

22

//改進的冒泡排序
23

void Improved_Bubble_sort(T *a, int n)
24

{
25

for(int i=n-1; i != 0; --i)
26

{
27

bool flag = true;
28

for(int j=0; j != i; ++j) //這一趟遍歷如果沒有交換，則已完成排序
29

if(a[j+1] < a[j]) { swap(a[j+1],a[j]); flag = false; }
30

if(flag == true) break;
31

}
32

}
33

34

#endif

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

只有注冊用戶登錄后才能發表評論。


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

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

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