选择排序

发表于

标题：选择排序

选择排序的基本思想：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法

【直接选择排序】：

  • 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
  • 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
  • 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中， 重复上述步骤，直到集合剩余1个元素

代码如下 ( 下面代码是一次循环同时挑选出最大和最小数, 并将其与左右交换 ): 

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
62
63
64
65
66
67
68
69
70
71
72
73
74
//选择排序
void SelectionSort(int *a, int len)
{
	int left = 0, right = len - 1;
	while (left < right){
		//max记录最大数的下标,min记录最小数的下标
		int max = left, min = left;
		for (int i = left; i <= right; i++){
			if (a[i]>a[max])
				max = i;
			if (a[i] < a[min])
				min = i;
		}
		Swap(&a[min], &a[left]);
		//如果最大数的下标在为left,证明要交换的最大数已经被
		//换到min小标所表示的位置,只需要将right和min位置交换即可
		if (max == left)
			Swap(&a[min], &a[right]);
		else
			Swap(&a[max], &a[right]);
		left++, right--;
	}
}
```  

--- 
### 【堆排序基本思想】：堆排序 (Heap sort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

创建堆的规则：升序—>大堆，降序—>小堆

![建堆示意图](/img/SelectionSort/20181018.png)

#### 执行如下步骤，直到数组为空

1. 把堆顶array[0]元素和当前最堆的最后一个元素交换
2. 堆元素个数减1
3. 由于第1步后根节点不再满足最堆定义，向下调整根结点

##### 把一棵完全二叉树调整为堆，以及每次将堆顶元素交换后 进行调整的时间复杂度均为O(log2^n)，所以堆排序的时 间复杂度为：O(N*log2^n)  堆排序是一种不稳定的排序算法

代码如下：

```c
//向下调整
void AdjustDown(int *a, int parent, int len)
{
	assert(a);
	while (parent <= len / 2 - 1){
                //取父节点的左孩子
		int child = parent * 2 + 1;
                //取左右子树中最大值
		if (child + 1 < len)
			child = a[child] > a[child + 1] ? child : child + 1;
                //如果孩子节点大于父节点,则交换
		if (a[child] > a[parent])
			Swap(&a[child], &a[parent]);
                //更新父节点,继续向下调整
		parent = parent + 1;
	}
}
//堆排序
void HeapSort(int *a, int len)
{
	assert(a);
        //从底向上依次向下调整
	for (int parent = len / 2 - 1; parent >= 0; parent--)
		AdjustDown(a, parent, len);
	int i = len-1;
        //将堆顶元素和数组最后一个元素交换,并且重新向下调整
	for (; i > 0 ; i--){
		Swap(&a[0], &a[i]);
		AdjustDown(a, 0, i);
	}
}

完整代码如下：

 #include <stdio.h>
 #include <stdlib.h>
 #include <assert.h>
//交换数据
void Swap(int *m, int *n)
{
    int tmp = *m;
    *m = *n;
    *n = tmp;
}
//选择排序
void SelectionSort(int *a, int len)
{
    int left = 0, right = len - 1;
    while (left < right){
        //max记录最大数的下标,min记录最小数的下标
        int max = left, min = left;
        for (int i = left; i <= right; i++){
            if (a[i]>a[max])
                max = i;
            if (a[i] < a[min])
                min = i;
        }
        Swap(&a[min], &a[left]);
        //如果最大数的下标在为left,证明要交换的最大数已经被
        //换到min小标所表示的位置,只需要将right和min位置交换即可
        if (max == left)
            Swap(&a[min], &a[right]);
        else
            Swap(&a[max], &a[right]);
        left++, right--;
    }
}
//向下调整
void AdjustDown(int *a, int parent, int len)
{
    assert(a);
    while (parent <= len / 2 - 1){
        int child = parent * 2 + 1;
        if (child + 1 < len)
            child = a[child] > a[child + 1] ? child : child + 1;
        if (a[child] > a[parent])
            Swap(&a[child], &a[parent]);
        parent = parent + 1;
    }
}
//堆排序
void HeapSort(int *a, int len)
{
    assert(a);
    for (int parent = len / 2 - 1; parent >= 0; parent--)
        AdjustDown(a, parent, len);
    int i = len-1;
    for (; i > 0 ; i--){
        Swap(&a[0], &a[i]);
        AdjustDown(a, 0, i);
    }
}
//打印数组
void PrintArray(int *a, int len)
{
    assert(a);
    for (int i = 0; i < len; i++)
        printf("%d ", a[i]);
    printf("\n");
}
int main()
{
    int a[] = { 58, 25, 49, 25, 16, 34 };
    SelectionSort(a, sizeof(a) / sizeof(int));
    //HeapSort(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
    system("pause");
    return 0;
}