-
Notifications
You must be signed in to change notification settings - Fork 0
/
SwapSort.cpp
59 lines (53 loc) · 1.47 KB
/
SwapSort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//
// Created by zzqni on 2024/5/1.
//
#include "SwapSort.h"
/**
* 交换:冒泡排序
*/
void Sort_SwapBubble(SortSqList &list) {
int totalCompare = 0;
for (int i = 0; i < list.length - 1; ++i) {
bool swapped = false;
for (int j = 0; j < list.length - i - 1; ++j) {
printf("元素 %d 和 元素 %d 比较\n", list.r[j].key, list.r[i].key);
totalCompare++;
if (list.r[j].key > list.r[j + 1].key) {
ElementType temp = list.r[j + 1];
list.r[j + 1] = list.r[j];
list.r[j] = temp;
swapped = true;
}
SortPrint(list);
}
if (!swapped) break;
}
printf("总共比较%d次\n", totalCompare);
}
/**
* 交换:快速排序 分组
*/
int Sort_SwapQuickPartition(SortSqList &list, int low, int high) {
ElementType data = list.r[low];
KeyType pivotKey = list.r[low].key;
while (low < high) {
while (low < high && list.r[high].key >= pivotKey)
--high;
list.r[low] = list.r[high];
while (low < high && list.r[low].key <= pivotKey)
++low;
list.r[high] = list.r[low];
}
list.r[low] = data;
return low;
}
/**
* 交换:快速排序
*/
void Sort_SwapQuick(SortSqList &list, int low, int high) {
if (low < high) {
int pivotPos = Sort_SwapQuickPartition(list, low, high);
Sort_SwapQuick(list, low, pivotPos - 1);
Sort_SwapQuick(list, pivotPos + 1, high);
}
}