轉自：
http://m.shnenglu.com/Files/bujiwu/SortData.rar
http://m.shnenglu.com/bujiwu/archive/2008/10/25/65040.html
1 #include <iostream>
2 using namespace std;
3
4 /*/////////////////////////////////////////////////////////////////////////
5 以下為快速排序
6 /////////////////////////////////////////////////////////////////////////*/
7 /*
8 冒泡排序
9 算法：
10 核心思想是掃描數據清單，尋找出現亂序的兩個相鄰的項目。當找到這兩個項目后
11 交換項目的位置然后繼續掃描。重復上面的操作直到所有的項目都按順序排好
12 時間復雜度n*n (n-1)*n/2
13 */
14 void BubbleSortData(int SortData[], int Length)
15 {
16 int tmpData =0;
17 bool swapFlag =true;
18
19 for (int i=Length-1; i>0 && swapFlag; i--)
20 {
21 swapFlag =false;
22 for(int j=0; j<i; j++)
23 {
24 if ( SortData[j] > SortData[j+1])
25 {
26 tmpData =SortData[j];
27 SortData[j] =SortData[j+1];
28 SortData[j+1] =tmpData;
29 swapFlag =true;
30 }
31 }
32 }
33
34 return;
35 }
36 /*
37 快速排序是對起泡排序的一種改進，通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵
38 字小，則可分別對這兩部分繼續進行排序，以達到整個序列有序.
39 交換順序表L中子表L.r[low..high]的記錄，使樞軸記錄到位，并返回其所在位置，此時在它之前(后)的記錄均不大(小)于它
40 時間復雜度為 n*logn,其平均性能最好，若初始記錄序列按關鍵字有序或基本有序，快速排序將銳化為起泡排序
41 */
42 int Partition(int SortData[], int low, int high)
43 {
44 int tmpData =SortData[low];//用于子表的第一個記錄作樞軸記錄
45 int temp=0;
46
47 while ( low<high )
48 {
49 //從表的兩端交替的向中間掃描
50 while (low<high && SortData[high]>=tmpData)
51 {
52 high--;
53 }
54 //將比樞軸記錄小的記錄移到低端
55 SortData[low] =SortData[high];
56
57 while (low<high && SortData[low]<=tmpData)
58 {
59 low++;
60 }
61 //將比樞軸記錄大的記錄移到高端
62 SortData[high] =SortData[low];
63 }
64 //樞軸記錄到位
65 SortData[low] =tmpData;
66
67 return low;//返回樞軸所在位置
68 }
69
70 void QuickSortData(int SortData[], int low, int high)
71 {
72 int offset;
73
74 if ( low<high )
75 {
76 offset =Partition(SortData, low, high);
77 QuickSortData(SortData, low, offset-1);
78 QuickSortData(SortData, offset+1, high);
79 }
80 }
81
82 /*/////////////////////////////////////////////////////////////////////////
83 以下為插入排序
84 /////////////////////////////////////////////////////////////////////////*/
85 /*
86 直接插入排序
87 算法：經過i-1遍處理后，L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，
88 使得L[1..i]又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。
89 首先比較L[i]和L[i-1]，如果L[i-1]<=L[i]，則L[1..i]已排好序，第i遍處理就結束了;
90 否則交換L[i]與L[i-1]的位置，繼續比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，
91 使得L[j] ≤L[j+1]時為止
92 優點:移動元素次數少，只需要一個輔助空間
93 時間復雜度n*n
94 當待排序記錄的數量n很小時，這是一種很好的排序方法。但是n很大時，則不適合
95 */
96 void InsertSortData(int SortData[], int Length)
97 {
98 int tmpData =0;
99 int i=0;
100 int j=0;
101
102 for(i=1; i<Length; i++)
103 {
104 if ( SortData[i] <SortData[i-1])
105 {
106 tmpData =SortData[i];
107 //數據往后移動
108 for (j=i-1; j>=0 && tmpData<SortData[j]; j--)
109 {
110 SortData[j+1] =SortData[j];
111 }
112 //將數據插入到j+1位置
113 SortData[j+1] =tmpData;
114 }
115 }
116
117 return;
118 }
119
120 /*
121 拆半插入排序所需要的輔助空間和直接插入排序相同，從時間上比較，折半插入排序僅減少了關鍵字間的比較次數，而記錄的移動次數不變。
122 因為時間復雜度仍為n*n
123 */
124 void BInsertSortData(int SortData[], int Length)
125 {
126 int tmpData =0;
127 int i=0;
128 int j=0;
129 int low;
130 int high;
131 int middle;
132
133 for(i=1; i<Length; i++)
134 {
135 tmpData =SortData[i];
136 low =0;
137 high =i-1;
138 //在r[low..high]中折半查找有序插入的位置
139 while ( low<=high )
140 {
141 middle =(low+high)/2;
142 if ( tmpData <SortData[middle] )
143 {
144 high =middle-1;
145 }
146 else
147 {
148 low =middle+1;
149 }
150 }
151 //記錄后移
152 for (j=i-1; j>=high+1; j--)
153 {
154 SortData[j+1] =SortData[j];
155 }
156 SortData[high+1] =tmpData;
157 }
158
159 return;
160 }
161
162
163 //////////////////////////////////////////////////////////////////////////
164
165 /*
166 簡單選擇排序
167 算法：首先找到數據清單中的最小的數據，然后將這個數據同第一個數據交換位置；接下來找第二小的數據，再將其同第二個數據交換位置，以此類推。
168 所需移動的操作次數最少為0,,最大為3(n-1)
169 然而無論記錄的初始排列如何，需要比較的次數相同n(n-1)/2 復雜度為n*n
170 */
171 void SelectSortData(int SortData[], int Length)
172 {
173 int tmpData;
174 int offset =0;
175 int j=0;
176
177 for (int i=0; i<Length-1; i++)
178 {
179 offset =0;
180 tmpData =SortData[i];
181 for (j=i+1; j<Length; j++)
182 {
183 if ( tmpData>SortData[j] )
184 {
185 tmpData =SortData[j];
186 offset =j;
187 }
188 }
189
190 if( offset >i)
191 {
192 SortData[offset] =SortData[i];
193 SortData[i] =tmpData;
194 }
195 }
196
197 return;
198 }
199
200 int main()
201 {
202 //int Buffer[] ={1,2,3,4,5,6};
203 int Buffer[] ={6,5,4,3,2,1};
204
205 QuickSortData(Buffer,0, 5);
206
207 for (int i=0; i<6; i++)
208 {
209 cout<<Buffer[i]<<" ";
210 }
211 cout<<endl;
212
213 return 0;
214 }
posted on 2008-10-27 18:39
Sandy 閱讀(648)
評論(0) 編輯 收藏 引用 所屬分類:
算法學習