一.数组的排序与查找
1 // 数组的排序和查找
2 func testArrSort() {
3 // 内部排序：将需要处理的所有数据都加载到内部存储器中进行排序（交换式排序法、选择式排序法、插入式排序）
4
5 // 交换式排序法-冒泡排序:递归将最大或最小值冒泡到数组尾
6 BubbleSort := func(arr1 []int32) (result bool) {
7 result = false
8 for i := 0; i < len(arr1); i++ {
9 tmpb := false
10 for j := 0; j < len(arr1)-i-1; j++ {
11 if (arr1)[j] > (arr1)[j+1] {
12 tem := (arr1)[j]
13 (arr1)[j] = (arr1)[j+1]
14 (arr1)[j+1] = tem
15 tmpb = true
16 }
17 }
18 if !tmpb {
19 break
20 }
21 }
22 result = true
23 return
24 }
25 // 插入式排序法:将无序的数组插入到有序的数组
26 InserSort := func(arr1 []int32) (result bool) {
27 result = false
28 for i := 1; i < len(arr1); i++ {
29 for j := i; j > 0; j-- {
30 if arr1[j] < arr1[j-1] {
31 tmp := arr1[j]
32 arr1[j] = arr1[j-1]
33 arr1[j-1] = tmp
34 }
35 }
36 }
37 result = true
38 return
39 }
40
41 // 希尔式排序(交换式排序):高效的利用每次的比较成果
42 type funXierOrderType func([]int32, int) bool
43 var XierOrder funXierOrderType
44 XierOrder = func(arr1 []int32, step int) (result bool) {
45 result = false
46 for i := 0; i < len(arr1); i++ {
47 if (i + step) >= len(arr1) {
48 break
49 }
50 for j := 0; ; {
51 j += step
52 if j >= len(arr1) {
53 break
54 }
55 if arr1[j-step] > arr1[j] {
56 tem := arr1[j-step]
57 arr1[j-step] = arr1[j]
58 arr1[j] = tem
59 }
60 }
61 }
62 if step == 1 {
63 result = true
64 return
65 }
66
67 return XierOrder(arr1, step/2)
68 }
69
70 // 快速排序法:选数组第0个元素作为参考,将其他元素与之比较,比他大的放左侧比他小的放右侧,以此分割数组作递归
71 type funQuickSortType func([]int32) bool
72 var QuickSort funQuickSortType
73 QuickSort = func(arr1 []int32) (result bool) {
74 result = false
75 leftIndex := 0
76 rightIndex := len(arr1) - 1
77 if len(arr1) < 1 {
78 return true
79 }
80
81 type Pivot struct {
82 pivot int32
83 status string
84 }
85
86 if rightIndex == 0 {
87 result = true
88 return
89 }
90 if rightIndex == 1 {
91 if arr1[0] > arr1[1] {
92 tem := arr1[0]
93 arr1[0] = arr1[1]
94 arr1[1] = tem
95 }
96 result = true
97 return
98 }
99 var pivot Pivot = Pivot{pivot: arr1[0], status: "R"}
100 for leftIndex != rightIndex {
101 if pivot.status == "R" {
102 if arr1[rightIndex] < pivot.pivot {
103 arr1[leftIndex] = arr1[rightIndex]
104 pivot.status = "L"
105 leftIndex++
106 } else {
107 pivot.status = "R"
108 rightIndex--
109 }
110 } else if pivot.status == "L" {
111 if arr1[leftIndex] < pivot.pivot {
112 pivot.status = "L"
113 leftIndex++
114 } else {
115 arr1[rightIndex] = arr1[leftIndex]
116 pivot.status = "R"
117 rightIndex--
118 }
119 }
120 }
121 arr1[leftIndex] = pivot.pivot
122 QuickSort(arr1[:leftIndex])
123 QuickSort(arr1[leftIndex+1:])
124 return true
125 }
126
127 // 堆排序:二叉树,大小堆.步骤:1.建堆 2.堆顶与堆尾交换固定堆尾 3.继续重复做建堆
128 type funBuildHeapType func([]int32)
129 type funHeapifyType func([]int32, int, int)
130 var BuildHeap funBuildHeapType
131 var Heapify funHeapifyType
132 Heapify = func(arr1 []int32, n int, i int) {
133 maxIndex := n - 1
134 c1 := (i * 2) + 1
135 c2 := c1 + 1
136 if c1 > maxIndex {
137 return
138 }
139 if arr1[i] < arr1[c1] {
140 tem := arr1[i]
141 arr1[i] = arr1[c1]
142 arr1[c1] = tem
143 Heapify(arr1, n, c1)
144 }
145 if (c2 <= maxIndex) && (arr1[i] < arr1[c2]) {
146 tem := arr1[i]
147 arr1[i] = arr1[c2]
148 arr1[c2] = tem
149 Heapify(arr1, n, c1)
150 }
151
152 }
153 BuildHeap = func(arr1 []int32) {
154 if len(arr1) < 2 {
155 return
156 }
157 maxIndex := len(arr1) - 1
158 heapIndex := (maxIndex - 1) / 2
159
160 for i := heapIndex; i >= 0; i-- {
161 Heapify(arr1, len(arr1), i)
162 }
163 }
164 HeapSort := func(arr1 []int32) {
165 BuildHeap(arr1)
166 // fmt.Println("BuildHeap=", arr1)
167 for i := len(arr1) - 1; i > 0; i-- {
168 tem := arr1[i]
169 arr1[i] = arr1[0]
170 arr1[0] = tem
171 Heapify(arr1, i, 0)
172 }
173 // fmt.Println("BuildHeap=", arr1)
174 }
175
176 // 选择排序:不停的找出最大或最小的元素放前面
177 var SelectSort funBuildHeapType
178 SelectSort = func(arr1 []int32) {
179 for i := 0; i < len(arr1); i++ {
180 for j := i + 1; j < len(arr1); j++ {
181 if arr1[i] > arr1[j] {
182 tem := arr1[i]
183 arr1[i] = arr1[j]
184 arr1[j] = tem
185 }
186 }
187 }
188 }
189
190 // 合并排序算法
191 type MergeTable struct {
192 startIndex int
193 endIndex int
194 len int
195 }
196 MergeArray := func(arr []int32, tab1 MergeTable, tab2 MergeTable) {
197 var arr1 []int32 = make([]int32, tab1.len+tab2.len)
198 for tab1Index, tab2Index, i := tab1.startIndex, tab2.startIndex, 0; ; i++ {
199 if (tab1Index > tab1.endIndex) && (tab2Index > tab2.endIndex) {
200 break
201 }
202 if tab1Index > tab1.endIndex {
203 arr1[i] = arr[tab2Index]
204 tab2Index++
205 continue
206 }
207 if tab2Index > tab2.endIndex {
208 arr1[i] = arr[tab1Index]
209 tab1Index++
210 continue
211 }
212 if arr[tab1Index] < arr[tab2Index] {
213 arr1[i] = arr[tab1Index]
214 tab1Index++
215 } else {
216 arr1[i] = arr[tab2Index]
217 tab2Index++
218 }
219 }
220 index := 0
221 for i := tab1.startIndex; i <= tab1.endIndex; i++ {
222 arr[i] = arr1[index]
223 index++
224 }
225 for i := tab2.startIndex; i <= tab2.endIndex; i++ {
226 arr[i] = arr1[index]
227 index++
228 }
229 }
230 var MergeSort funBuildHeapType
231 MergeSort = func(arr []int32) {
232 alen := len(arr)
233 if alen == 1 {
234 return
235 }
236 for step := 1; ; step *= 2 {
237 for i := 0; i < len(arr); {
238 tab1 := MergeTable{i, i + step - 1, step}
239 tab2 := MergeTable{(i + step), i + step*2 - 1, step}
240 if tab1.endIndex > (len(arr) - 1) {
241 tab1.endIndex = len(arr) - 1
242 tab1.len = tab1.endIndex - tab1.startIndex + 1
243
244 tab2.len = 0
245 tab2.startIndex = 0
246 tab2.endIndex = -1
247 } else if tab2.endIndex > (len(arr) - 1) {
248 if tab2.startIndex > (len(arr) - 1) {
249 tab2.len = 0
250 tab2.startIndex = 0
251 tab2.endIndex = -1
252 } else {
253 tab2.endIndex = len(arr) - 1
254 tab2.len = tab2.endIndex - tab2.startIndex + 1
255 }
256 }
257 fmt.Println(tab1, tab2)
258 MergeArray(arr, tab1, tab2)
259 i = i + step*2
260 }
261 fmt.Println("step=", step, " :", arr)
262 if step >= len(arr)-1 {
263 break
264 }
265 }
266
267 }
268
269 // 基数排序(待)
270 // 计数排序(待)
271 // 桶排序(待)
272 var arr [9]int32 = [9]int32{14, 2, 5, 12, 68, 6, 8, 99, 61}
273 // var arr [6]int32 = [6]int32{2, 5, 3, 1, 10, 4}
274 fmt.Println(arr)
275 MergeSort(arr[:])
276 fmt.Println(arr)
277 SelectSort(arr[:])
278 HeapSort(arr[:])
279 rb := QuickSort(arr[:])
280 rb = XierOrder(arr[:], len(arr)/2)
281 rb = BubbleSort(arr[:])
282 rb = InserSort(arr[:])
283 fmt.Println(rb)
284
285 type funType func([]int32, int32) (int32, string)
286 var BunaryFind funType
287 // 二分查找法:以下代码针对必须从小到大排序好了的数组
288 BunaryFind = func(arr1 []int32, findValue int32) (result int32, err string) {
289 err = "error!"
290 result = findValue
291 if len(arr1) == 1 {
292 if arr1[0] == findValue {
293 result = findValue
294 err = ""
295 return
296 } else {
297 err = "not find value!"
298 return
299 }
300 } else {
301 if arr1[len(arr1)/2] > findValue {
302 result, err = BunaryFind(arr1[:len(arr1)/2], findValue)
303 } else {
304 result, err = BunaryFind(arr1[len(arr1)/2:], findValue)
305 }
306 }
307 return
308 }
309
310 result, err := BunaryFind(arr[:], 99)
311 fmt.Println("result:", result, err)
312 // 外部排序：数据量过大，无法全部家在到内存，需借助外部存储进行排序。（合并排序法(二路归并 多路归并...路多耗CPU,路少耗IO,需根据情况选择)、直接合并排序法）
313
314 }
标签：...,arr,int32,tab2,len,Glang,冒泡,arr1,result From： https://www.cnblogs.com/watermeloncode/p/17699260.html