选择排序

---

---

1. 简单选择排序

• 时间复杂度O(n²)
• 空间复杂度O(1)
• 不稳定
• 适用：顺序存储和链式存储的线性表

n个元素，n-1趟排序，每趟把最小的往前放。

int i, j;
int min;
for (i = 0; i < n - 1; i++) {
    min = i;
    for (j = i + 1; j < n; j++) {
        if (L[j] < L[min]) min = j;
    }
    if (min != i) {
        int tmp = L[i];
    	L[i] = L[min];
    	L[min] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 堆排序

• 时间复杂度O(nlog₂n)
• 空间复杂度最好O(1)
• 不稳定
• 适用：顺序存储的线性表

堆的定义 n个关键字序列L[1 ~ n]称为堆，当满足：

1. (大根堆)L[i] >= L[2i] && L[i] >= L[2i + 1] 或
2. (小根堆)L[i] <= L[2i] && L[i] <= L[2i + 1]

堆和完全二叉树有着非常紧密的联系，下面也会使用完全二叉树的数组表示来完成算法

使用堆排序需要解决两个问题：

1. 无序表建堆
2. 取数后的堆调整

2.1 建堆(大根堆)

从最后一个子树往树根遍历，如果不符合每个子树的根最大，则调整(siftDown)该子树

// 堆化
void heapfiy(ElemType L[], int n)
{
    for (int i = n / 2; i > 0; i--) {
        siftDown(L, i, n);
    }
}
// 调整以k为根的子树，将k点siftDown(下滤)
void siftDown(ElemType L[], int k, int n)
{
    L[0] = L[k];
    for (int i = 2 * k; i <= n; i <<= 1) {
        if (i < n && L[i] < L[i + 1]) { // 如果有右兄弟，且右兄弟更大
            i++;
        }
		if (L[i] <= L[0]) {
        	break;	// 此刻已经k子树已经形成大根堆
        } else {	
            L[k] = L[i];	// 需要下滤
            k = i;	// 最终位置暂时判定到i处，否则先不变
        }
    }
    L[k] = L[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.2 堆排序

堆排序时，每次都把根和最后一个元素交换，再下滤，重新生成大根堆。

int heapSort(ElemType L[], int n)
{
    heapify(L, n);
    for (int i = n; i > 1; i--) {
        // 取堆顶放在最后
        int tmp = L[i];
        L[i] = L[1];
        L[1] = tmp;
        siftDown(L, 1, i - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11

3. 例

LeetCode 912. 排序数组

// 简单选择排序
int* sortArray(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    int i, j;
    int min;
    for (i = 0; i < numsSize - 1; i++) {
        min = i;
        for (j = i + 1; j < numsSize; j++) {
            if (nums[j] < nums[min]) min = j;
        }
        if (min != i) {
            int tmp = nums[i];
            nums[i] = nums[min];
            nums[min] = tmp;
        }
    }
    return nums;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 堆排序
// 下滤
void siftDown(int *L, int k, int n) 
{
    int tmp = L[k - 1];
    for (int i = 2 * k; i <= n; i <<= 1) {
        if (i < n && L[i - 1] < L[i]) {
            i++;
        }
        if (L[i - 1] <= tmp) {
            break;
        } else {
            L[k - 1] = L[i - 1];
            k = i;
        }
    }
    L[k - 1] = tmp;
}
// 堆化
void heapify(int* L, int n) 
{
    for (int i = n / 2; i > 0; i--) {
        siftDown(L, i, n);
    }
}

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    heapify(nums, numsSize);
    for (int i = numsSize; i > 1; i--) {
        int tmp = nums[i - 1];
        nums[i - 1] = nums[0];
        nums[0] = tmp;
        siftDown(nums,1,i - 1);
    }
    return nums;
}
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

4. 其他

4.1 堆插入

// 调整k点，上滤
void siftUp(ElemType L[], int k, int n)
{
    L[0] = L[k]
    for (int i = k / 2; k >= 1; k >>= 1) {
        if (L[i] >= L[0]) {
            break;
        } else {
            L[k] = L[i];
            k = i;
        }
    }
    L[k] = L[0]
}

void HeapInsert(ElemType L[], int &n, int v)
{
    L[n + 1] = v;
    n++;
    siftUp(L, n, n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21