C++各种常见排序算法 冒泡排序，插入排序，快排序，选择排序，希尔排序
BubbleSort.cpp ~ 657B 下载(216)
01 | // BubbleSort.cpp: implementation of the CBubbleSort class. |
05 | #include “BubbleSort.h” |
06 | |
07 | // |
08 | // Construction/Destruction |
09 | // |
10 | |
11 | CBubbleSort::CBubbleSort() |
12 | { |
13 | |
14 | } |
15 | |
16 | CBubbleSort::~CBubbleSort() |
17 | { |
18 | |
19 | } |
20 | |
21 | void CBubbleSort::Sort (int * arr,const int size) |
22 | { |
23 | int tmp =0 ; |
24 | for (int i =0 ;i<size ;i++) |
25 | for (int j=i+1;j<size ;j++) |
26 | { |
27 | if(arr[i]>arr[j]) |
28 | { |
29 | tmp =arr[i]; |
30 | arr[i] = arr[j]; |
31 | arr[j] = tmp ; |
32 | } |
33 | } |
34 | } |
[文件] BubbleSort.h ~ 613B 下载(167)
01 | // BubbleSort.h: interface for the CBubbleSort class. |
02 | // |
03 | // |
04 | |
05 | #if !defined(AFXBUBBLESORT_H2A6E4581_4C19_4061_BD68_9FA2DD286EB5INCLUDED) |
06 | #define AFXBUBBLESORT_H2A6E4581_4C19_4061_BD68_9FA2DD286EB5INCLUDED |
07 | |
08 | #if _MSC_VER > 1000 |
09 | #pragma once |
10 | #endif // _MSC_VER > 1000 |
11 | |
12 | #include “Sort.h” |
13 | |
14 | class CBubbleSort : public CSort |
15 | { |
16 | public: |
17 | CBubbleSort(); |
18 | virtual ~CBubbleSort(); |
19 | |
20 | virtual void Sort(int * arr,const int size) ; |
21 | |
22 | }; |
23 | |
24 | #endif // !defined(AFXBUBBLESORT_H2A6E4581_4C19_4061_BD68_9FA2DD286EB5INCLUDED) |
[文件] InsertSort.h ~ 682B 下载(149)
01 | // InsertSort.h: interface for the CInsertSort class. |
02 | // |
03 | // |
04 | |
05 | #if !defined(AFXINSERTSORT_HFF5699F7_8D6A_4709_93F1_97CDC299528AINCLUDED) |
06 | #define AFXINSERTSORT_HFF5699F7_8D6A_4709_93F1_97CDC299528AINCLUDED |
07 | |
08 | #if _MSC_VER > 1000 |
09 | #pragma once |
10 | #endif // _MSC_VER > 1000 |
11 | |
12 | #include “Sort.h” |
13 | #include <stdlib.h> |
14 | |
15 | class CInsertSort : public CSort |
16 | { |
17 | public: |
18 | CInsertSort(); |
19 | virtual ~CInsertSort(); |
20 | |
21 | virtual void Sort (int * arr,const int size) ; |
22 | void DirectInsertSort(int *arr,const int size); |
23 | }; |
24 | |
25 | #endif // !defined(AFXINSERTSORT_HFF5699F7_8D6A_4709_93F1_97CDC299528AINCLUDED) |
[文件] InsertSort.cpp ~ 1KB 下载(98)
01 | // InsertSort.cpp: implementation of the CInsertSort class. |
02 | // |
03 | // |
04 | |
05 | #include “InsertSort.h” |
06 | |
07 | // |
08 | // Construction/Destruction |
09 | // |
10 | |
11 | CInsertSort::CInsertSort() |
12 | { |
13 | |
14 | } |
15 | |
16 | CInsertSort::~CInsertSort() |
17 | { |
18 | |
19 | } |
20 | /* |
21 | if (mid != high&& mid != low) |
22 | { |
23 | exit(0); |
24 | } |
25 | */ |
26 | |
27 | |
28 | //���ֲ������� |
29 | void CInsertSort::Sort (int * arr,const int size) |
30 | { |
31 | if(!arr) |
32 | return ; |
33 | // |
34 | for (int i =1 ;i<size ;i++) |
35 | { |
36 | int tmp = arr[i]; |
38 | int low =0,high = i-1 ,mid ; |
39 | while (low<= high) |
40 | { |
41 | mid= (low+high)/2; |
42 | if(arr[i]<arr[mid]) |
43 | high = mid-1; |
44 | else |
45 | low = mid +1 ; |
46 | } |
47 | //high ָ��tmpӦ�����ǰһλ�ã�lowֵΪhigh+1 |
48 | for (int j =i-1 ;j>=low;j—) |
49 | { |
50 | arr[j+1]= arr[j]; |
51 | } |
52 | arr[low]= tmp ; |
57 | void CInsertSort::DirectInsertSort(int *arr,int size) |
58 | { |
59 | if(!arr) |
60 | return ; |
61 | for (int i=1;i<size ;i++) |
62 | { |
63 | int tmp = arr[i]; |
64 | for (int j = i-1; j>=0 && tmp < arr[j];j—) |
65 | { |
66 | arr[j+1] = arr[j]; |
67 | } |
68 | arr[j+1] =tmp ; |
69 | |
70 | } |
71 | } |
[文件] Main.cpp ~ 1KB 下载(149)
01 | #include <iostream> |
02 | #include <stdlib.h> |
03 | #include <memory> |
04 | #include “BubbleSort.h” |
05 | #include “InsertSort.h” |
06 | #include “QuickSort.h” |
07 | #include “SelectionSort.h” |
08 | #include “ShellSort.h” |
09 | |
10 | #define LENGTH 100 |
11 | |
12 | using namespace std; |
13 | |
14 | int main() |
15 | { |
16 | // FILE *pFile ; |
17 | //auto_ptr<FILE> apFile(pFile); |
18 | //std::tr1::shared_ptr<int> sp(new int(0)); |
19 | //tr1::shared_ptr<FILE> spFile ; |
20 | // pFile = fopen( (“2.txt”), (“wt”)); |
21 | // if(!pFile) |
22 | // { |
23 | // std::cout<<”File open error!\n”<<std::endl; |
24 | // exit(0); |
25 | // } |
26 | int arr[LENGTH]; |
27 | int i =0 ; |
28 | for(i=0;i<LENGTH ;i++) |
29 | { |
30 | arr[i] = rand()%1000; |
31 | //cout<<arr[i]<<endl; |
32 | } |
33 | |
34 | CSort *pSort ; |
35 | pSort = new CShellSort ; |
36 | pSort->Sort(arr,LENGTH) ; |
37 | // CInsertSort is ; |
38 | // is.DirectInsertSort(arr,LENGTH); |
39 | |
40 | delete pSort ; |
41 | for ( i =0 ;i<LENGTH;i++) |
42 | { |
43 | std::cout<<arr[i]<<std::endl; |
44 | } |
45 | // for( i=0;i<LENGTH ;i++) |
46 | // { |
47 | // fprintf(pFile, (“%d\n”),arr[i]); |
48 | // //cout<<arr[i]<<endl; |
49 | // } |
50 | // fclose(pFile); |
51 | |
52 | // FILE *pFileReader ; |
53 | // pFileReader = fopen(“1.txt”,”rt”); |
54 | // if(!pFileReader) |
55 | // { |
56 | // std::cout<<”File open error!\n”<<std::endl; |
57 | // exit(0); |
58 | // } |
59 | |
60 | // int n =0; |
61 | // for(i=0;i<LENGTH;i++) |
62 | // { |
63 | // fscanf(pFileReader,”%d\n”,&n); |
64 | // std::cout<<n<<std::endl; |
65 | // } |
66 | // //fclose(pFileReader); |
67 | |
68 | return 0 ; |
69 | } |
[文件] SelectionSort.cpp ~ 776B 下载(148)
view source
print ?
01 | // SelectionSort.cpp: implementation of the CSelectionSort class. |
02 | // |
03 | // |
04 | |
05 | #include “SelectionSort.h” |
06 | |
07 | // |
08 | // Construction/Destruction |
09 | // |
10 | |
11 | CSelectionSort::CSelectionSort() |
12 | { |
13 | |
14 | } |
15 | |
16 | CSelectionSort::~CSelectionSort() |
17 | { |
18 | |
19 | } |
20 | |
21 | //����������ѡ��С�ģ�������������棬�Ӷ��������+1 |
22 | void CSelectionSort::Sort (int * arr,const int size) |
23 | { |
24 | if(!arr) |
25 | return ; |
26 | for (int i =0 ;i<size ;i++) |
27 | { |
28 | int pos= i ; |
29 | for (int j= i;j<size ;j++) |
30 | { |
31 | if(arr[pos] > arr[j]) |
32 | pos = j ; |
33 | } |
34 | int tmp = arr[i]; |
35 | arr[i] = arr[pos]; |
36 | arr[pos]= tmp ; |
37 | } |
38 | } |
[文件] SelectionSort.h ~ 635B 下载(151)
01 | // SelectionSort.h: interface for the CSelectionSort class. |
02 | // |
03 | // |
04 | |
05 | #if !defined(AFXSELECTIONSORT_H99AADAE2_AC7F_49BF_B382_388CD8A9E784INCLUDED) |
06 | #define AFXSELECTIONSORT_H99AADAE2_AC7F_49BF_B382_388CD8A9E784INCLUDED |
07 | |
08 | #if _MSC_VER > 1000 |
09 | #pragma once |
10 | #endif // _MSC_VER > 1000 |
11 | |
12 | #include “Sort.h” |
13 | |
14 | class CSelectionSort : public CSort |
15 | { |
16 | public: |
17 | CSelectionSort(); |
18 | virtual ~CSelectionSort(); |
19 | |
20 | virtual void Sort(int * arr,const int size) ; |
21 | }; |
22 | |
23 | #endif // !defined(AFXSELECTIONSORT_H99AADAE2_AC7F_49BF_B382_388CD8A9E784INCLUDED) |
[文件] Sort.cpp ~ 374B 下载(141)
01 | // Sort.cpp: implementation of the CSort class. |
02 | // |
03 | // |
04 | |
05 | #include “Sort.h” |
06 | |
07 | // |
08 | // Construction/Destruction |
09 | // |
10 | |
11 | CSort::CSort() |
12 | { |
13 | |
14 | } |
15 | |
16 | CSort::~CSort() |
17 | { |
18 | |
19 | } |
[文件] Sort.h ~ 530B 下载(144)
01 | // Sort.h: interface for the CSort class. |
02 | // |
03 | // |
04 | |
05 | #if !defined(AFXSORT_H39C9279B_CB59_4081_B68B_C8D0459C1C1EINCLUDED) |
06 | #define AFXSORT_H39C9279B_CB59_4081_B68B_C8D0459C1C1EINCLUDED |
07 | |
08 | #if _MSC_VER > 1000 |
09 | #pragma once |
10 | #endif // _MSC_VER > 1000 |
11 | |
12 | class CSort |
13 | { |
14 | public: |
15 | CSort(); |
16 | virtual ~CSort(); |
17 | |
18 | virtual void Sort(int * arr,const int size) =0; |
19 | |
20 | }; |
21 | |
22 | #endif // !defined(AFXSORT_H39C9279B_CB59_4081_B68B_C8D0459C1C1EINCLUDED) |
[文件] ShellSort.h ~ 652B 下载(145)
01 | // ShellSort.h: interface for the CShellSort class. |
02 | // |
03 | // |
04 | |
05 | #if !defined(AFXSHELLSORT_H77F1EA61_E5FA_42F9_96A0_A718CB82519EINCLUDED) |
06 | #define AFXSHELLSORT_H77F1EA61_E5FA_42F9_96A0_A718CB82519EINCLUDED |
07 | |
08 | #if _MSC_VER > 1000 |
09 | #pragma once |
10 | #endif // _MSC_VER > 1000 |
11 | |
12 | #include “Sort.h” |
13 | |
14 | class CShellSort : public CSort |
15 | { |
16 | public: |
17 | CShellSort(); |
18 | virtual ~CShellSort(); |
19 | |
20 | virtual void Sort(int * arr,const int size) ; |
21 | void ShellPass (int *arr ,int size ,int delta); |
22 | }; |
23 | |
24 | #endif // !defined(AFXSHELLSORT_H77F1EA61_E5FA_42F9_96A0_A718CB82519EINCLUDED) |
[文件] QuickSort.h ~ 709B 下载(129)
01 | // QuickSort.h: interface for the CQuickSort class. |
02 | // |
03 | // |
04 | |
05 | #if !defined(AFXQUICKSORT_H55ABF9C0_0E66_431F_B3CE_5D63EF7BE1C6INCLUDED) |
06 | #define AFXQUICKSORT_H55ABF9C0_0E66_431F_B3CE_5D63EF7BE1C6INCLUDED |
07 | |
08 | #if _MSC_VER > 1000 |
09 | #pragma once |
10 | #endif // _MSC_VER > 1000 |
11 | |
12 | #include “Sort.h” |
13 | |
14 | class CQuickSort : public CSort |
15 | { |
16 | public: |
17 | CQuickSort(); |
18 | virtual ~CQuickSort(); |
19 | |
20 | virtual void Sort (int * arr,const int size) ; |
21 | private : |
22 | int Partition(int * arr,int low ,int high) ; |
23 | void QuickSort(int *arr,int low , int high) ; |
24 | }; |
25 | |
26 | #endif // !defined(AFXQUICKSORT_H55ABF9C0_0E66_431F_B3CE_5D63EF7BE1C6INCLUDED) |
[文件] QuickSort.cpp ~ 1KB 下载(123)
01 | // QuickSort.cpp: implementation of the CQuickSort class. |
02 | // |
03 | // |
04 | |
05 | #include “QuickSort.h” |
06 | |
07 | // |
08 | // Construction/Destruction |
09 | // |
10 | |
11 | CQuickSort::CQuickSort() |
12 | { |
13 | |
14 | } |
15 | |
16 | CQuickSort::~CQuickSort() |
17 | { |
18 | |
19 | } |
20 | |
21 | void CQuickSort::Sort (int * arr,const int size) |
22 | { |
23 | if(!arr) |
24 | return ; |
25 | QuickSort(arr,0,size-1); |
26 | } |
27 | |
28 | void CQuickSort::QuickSort(int *arr,int low , int high) |
29 | { |
30 | |
31 | if (low<high) |
32 | { |
33 | int pivotloc = Partition(arr,low,high); |
34 | QuickSort(arr,low,pivotloc-1); |
35 | QuickSort(arr,pivotloc+1,high); |
36 | } |
37 | } |
38 | int CQuickSort::Partition(int * arr,int low ,int high) |
39 | { |
40 | int pivot = arr[low]; |
41 | while (low<high) |
42 | { |
43 | |
44 | while(low<high && arr[high]>=pivot) |
45 | high —; |
46 | arr[low]= arr[high] ; |
47 | while(low<high && arr[low]<=pivot) |
48 | low ++; |
49 | arr[high]= arr[low]; |
50 | } |
51 | arr[low] = pivot; |
52 | return low ; |
53 | } |
[文件] ShellSort.cpp ~ 851B 下载(99)
01 | // ShellSort.cpp: implementation of the CShellSort class. |
02 | // |
03 | // |
04 | |
05 | #include “ShellSort.h” |
06 | |
07 | // |
08 | // Construction/Destruction |
09 | // |
10 | |
11 | CShellSort::CShellSort() |
12 | { |
13 | |
14 | } |
15 | |
16 | CShellSort::~CShellSort() |
17 | { |
18 | |
19 | } |
20 | void CShellSort::Sort (int * arr,const int size) |
21 | { |
22 | if(!arr) |
23 | return ; |
24 | int increment = size ; |
25 | do { |
26 | increment = increment/3 +1; |
27 | ShellPass(arr,size,increment); |
28 | } while(increment>1); |
29 | } |
30 | void CShellSort::ShellPass(int *arr ,int size ,int delta) |
31 | { |
32 | for (int i = delta;i<size;i++) |
33 | { |
34 | int tmp = arr[i]; |
35 | for (int j = i-delta; j>=0 && tmp < arr[j];j-=delta) |
36 | { |
37 | arr[j+delta] = arr[j]; |
38 | } |
39 | arr[j+delta] = tmp ; |
40 | } |
41 | } |
た 入场券
ゞ 浴缸里的玫瑰
爱被打了一巴掌
还没有评论，来说两句吧...