算法擱置很久了，來填上之前的坑~
快速排序
说白了，就是找出每次一个数（称为基准），使得那个数所在的位置，其左边元素比基准数小，其右边元素比基准数大。
故我们需要3个函数：
getIndex找出基准数quickSortPartition针对当前的基准数，拆分成左右两个数组，再分别进行排序- 初始时，我们默认将数组第一个元素选为基准数
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
int getIndex(vector<int>& num,int left,int right){
// 默认将数组第一个元素选为基准数
int base_num = num[left];
// 左右下标符合左小于右
while(left < right){
// 右边的比基准数大，跳过
while (left < right && base_num<=num[right]){ // 一定要是<=，不能是<，否则碰到重复元素的排序会无限Loop
right --;
}
// 右边的比基准数小，将right赋值到最左边left
num[left] = num[right];
// 左边的比基准数小，跳过
while (left <right && base_num>=num[left]){
left ++;
}
// 左边的比基准数大，将left赋值到最右边right
num[right] = num[left];
}
// left最终位置就是我们基准数应该在的位置
num[left] = base_num;
return left;
}
void quickSortPartition(vector<int>& num,int left,int right){
if (left >= right){
return;
}
int index = getIndex(num,left,right);
quickSortPartition(num,left,index);
quickSortPartition(num,index+1,right);
}
堆排序
从了解下最大堆和最小堆的定义：
-
最大堆：结点的值大于等于其子结点的值；
-
最小堆：结点的值小于等于其子结点的值；
以下给出最大堆的算法：
以下有三个函数：
heapSort主函数，处理vector<int>数组中的值buildMaxHeap用于构建最大堆adjustMaxHeap用于调整当前堆，成为一个新的最大堆
思路：（从小到大排序）先把数组构建成一个最大堆。正是最大堆的根结点的值一定是最大的，于是我们把它和数组尾元素交换一下，于是这个数组的最后一个元素就确定啦~那么我们排除掉数组尾部的那个最大的元素，让其余的通过调整的方式组成最大堆，于是倒数第二个元素也就确定啦~一次类推
所以大体思路：
- 先构建一个最大堆
- 选举出的根结点放至尾部，然后剩余元素继续调整成一个最大堆。以此类推
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
60
61
void adjustMaxHeap(vector<int> &v, int index, int length)
{
// 当这个index有子结点
while ((index << 1) + 1 < length)
{
int left = (index << 1) + 1;
int right = (index << 1) + 2;
int largest = index;
if (left < length)
{
// 左子结点比当前最大的还要大，记录下来
if (v[left] > v[largest])
{
largest = left;
}
}
if (right < length)
{
// 右子结点比当前最大的还要大，记录下来
if (v[right] > v[largest])
{
largest = right;
}
}
// 如果左右结点比index结点大，则交换一下，否则无需调整了
if (largest == index){
break;
} else {
swap(v[largest],v[index]);
// 交换后，index变成largest子结点，调整他的子树（因为调整后，子树可能不满足最大堆的定义了）
index = largest;
}
}
}
void buildMaxHeap(vector<int> &v, int length)
{
// 有子结点
for (int i = v.size() / 2 - 1; i >= 0; i--)
{
// 调整每一个元素结点
adjustMaxHeap(v, i, length);
}
}
void heapSort(vector<int> &v)
{
// justify the max Heap
int length = v.size();
buildMaxHeap(v, length);
for (int i = v.size() - 1; i > 0; i--)
{
// 放至当前堆的尾部
swap(v[0], v[i]);
// 长度 - 1
length--;
// 调整最大堆
adjustMaxHeap(v, 0, length);
}
}
测试效果
