假設有N筆資料，將他儲存至data陣列中。
1.從頭到尾選出最小的資料，然後將該筆資料輸出，再以一個足夠大的數，取代該筆資料。
2.重複上列動作直到所有N筆資料都被選出。
第一次我的作法:(不標準)
SelectionSort.h:
1: #ifndef _SELECTION_SORT_H_
2: #define _SELECTION_SORT_H_
3:
4: #include <iostream>
5:
6: #define MaxSelectionNum 10
7: #define IsPickup 99999
8: class SelectionSort
9: {
10: private:
11: int min;
12: int count;
13: int date[MaxSelectionNum];
14: int newDate[MaxSelectionNum];
15: public:
16: SelectionSort(void);
17: ~SelectionSort(void);
18: void Initialize();
19: void PrintArray(void);
20: void PrintNewArray(void);
21: void Sorting(void);
22: void Processing();
23: };
24: #endif
SelectionSort.cpp:
1: #include "SelectionSort.h"
2: SelectionSort::SelectionSort(void)
3: {
4: }
5:
6:
7: SelectionSort::~SelectionSort(void)
8: {
9: }
10:
11: void SelectionSort::Initialize(void)
12: {
13: int tmp[MaxSelectionNum] = {73,65,52,24,83,17,35,96,41,9};
14:
15:
16: //Copy Array to another Array tmp<=>data
17: for (int i = 0; i < MaxSelectionNum; i++)
18: date[i] = tmp[i];
19: //Counter
20: count =0;
21:
22: }
23:
24: void SelectionSort::PrintArray(void)
25: {
26:
27: for (int i = 0; i < MaxSelectionNum; i++)
28: {
29: std::cout << date[i] << std::endl;
30: }
31: }
32:
33: void SelectionSort::PrintNewArray(void)
34: {
35: std::cout <<"AfterSorting"<<std::endl;
36: for (int i = 0; i < MaxSelectionNum; i++)
37: {
38: std::cout << newDate[i] << std::endl;
39: }
40: }
41:
42: void SelectionSort::Sorting()
43: {
44: min =IsPickup;
45: for (int i = 0; i < MaxSelectionNum; i++)
46: {
47: if(min > date[i])
48: min = date[i];
49: }
50:
51: for (int i = 0; i < MaxSelectionNum; i++)
52: {
53: if(min == date[i])
54: {
55: date[i] = IsPickup;
56: }
57: }
58:
59: newDate[count] = min;
60: count++;
61: }
62:
63: void SelectionSort::Processing()
64: {
65: while (count < MaxSelectionNum)
66: {
67: Sorting();
68: }
69: PrintNewArray();
70: }
main.cpp:
1: #include "SelectionSort.h"
2: int main()
3: {
4: SelectionSort sortS;
5: sortS.Initialize();
6: sortS.PrintArray();
7: sortS.Processing();
8: return 0;
9: }
不好的地方:
1.多浪費一個Array空間存儲新陣列。int = 4 byte,ArrySize 4byte*10 = 40.
2.Big O = MaxSelectionNum*MaxSelectionNum*MaxSelectionNum。N的三次方
3.SelectionSort沒辦法重複使用。
比較好的做法:
1.Swap，若遇到較小的數字則交換。Big O 則變成 MaxSelectionNum * MaxSelectionNum。N平方
2.不需要”以一個足夠大的數，取代該筆資料”這個步驟。
SelectionSort.h:
1: #ifndef _SELECTION_SORT_H_
2: #define _SELECTION_SORT_H_
3:
4: #include <iostream>
5:
6: #define MaxSelectionNum 10
7: class SelectionSort
8: {
9: public:
10: SelectionSort(void);
11: ~SelectionSort(void);
12: void Swap(int&,int&);
13: void Initialize();
14: void PrintArray(void);
15: void Sorting(int*,int);
16: int date[MaxSelectionNum];
17: };
18: #endif
SelectionSort.cpp:
1: #include "SelectionSort.h"
2: SelectionSort::SelectionSort(void){}
3: SelectionSort::~SelectionSort(void){}
4:
5: void SelectionSort::Swap(int &a,int&b)
6: {
7: int tmp = b;
8: b = a;
9: a = tmp;
10: }
11:
12: void SelectionSort::Initialize(void)
13: {
14: int tmp[MaxSelectionNum] = {73,65,52,24,83,17,35,96,41,9};
15:
16:
17: //Copy Array to another Array tmp<=>data
18: for (int i = 0; i < MaxSelectionNum; i++)
19: date[i] = tmp[i];
20:
21: }
22:
23: void SelectionSort::PrintArray(void)
24: {
25:
26: for (int i = 0; i < MaxSelectionNum; i++)
27: {
28: std::cout << date[i] << std::endl;
29: }
30: }
31: void SelectionSort::Sorting(int *date,int size)
32: {
33: for (int i = 0; i < size; i++)
34: {
35: for (int j = 0; j < size; j++)
36: {
37: if(date[i] < date[j])
38: Swap(date[i],date[j]);
39: }
40: }
41: }
main.cpp:
1: #include "SelectionSort.h"
2: #define MaxSelectionNum 10
3: int main()
4: {
5: SelectionSort sortS;
6: sortS.Initialize();
7: sortS.Sorting(sortS.date,MaxSelectionNum);
8: sortS.PrintArray();
9: return 0;
10: }
SourceCode
No comments:
Post a Comment