本文实例为大家分享了C++选择排序算法的具体代码，供大家参考，具体内容如下
基本思想
每一趟从无序区中选出最小的元素，顺序放在有序区的最后，直到全部元素排序完毕。
由于选择排序每一趟总是从无序区中选出全局最小（或最大）的元素，所以适用于从大量元速度中选择一部分排序元素。例如，从10000个元素中选出最小的前10位元素。
直接选择排序
1.排序思路
从第i趟开始，从当前无序区arr[i…n-1]中选出最小元素arr[k]，将它与有序区的最后一个元素，也就是无序区的第一个元素交换。每趟排序后，有序区增加一个元素，无序区减少一个元素，且有序区中所有元素均小于等于无序区中的元素。经过n-1趟排序后，无序区只剩下arr[n-1]一个元素，它必然为整个序列的最大值，故无需再排。
2.排序算法
|
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
|
void SelectSort(int *arr, int size){ if (arr == NULL) return; //1.找到无序区中最小的元素和它的下标 int i, j; for (i = 0; i < size - 1; i++) { int k = i; for (j = i + 1; j < size; j++) { if (arr[j] < arr[k]) { k = j; } } //2.把最小的元素与无序区第一个元素交换 //swap(arr[i], arr[k]); if (k != i) { int tmp = arr[i]; arr[i] = arr[k]; arr[k] = tmp; } }} |
3.算法分析
由于要选出最小值，故无序区中的每个元素都要参与比较，所以无论初始数据序列的状态如何，总的比较次数为：
C = n-1 +n-2+n-3+…+2+1 = n(n-1)/2
故直接选择排序的时间复杂度为O(N^2)，空间复杂度为O(1)。直接选择排序是一个不稳定的算法。例如，排序序列为{5，3，2，5，4，1}，第一趟排序后得到{1，3，4，5，4，5}，两个5的相对位置发生了变化。
4.优化版本
每趟排序同时找出最大值和最小值，把最小值放在序列的左边，最大值放在序列的右边，然后同时缩小左右排序范围。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
//优化，每趟排序同时找出最大值和最小值void SelectSort1(int *arr, int size){ if (arr == NULL) return; int left = 0; int right = size - 1; while (left < right) { for (int i = left; i < right; i++) { if (arr[i] < arr[left]) swap(arr[i], arr[left]); if (arr[i] > arr[right]) swap(arr[i], arr[right]); } left++; right--; }} |
堆排序
1.排序思路
堆排序是一种树形选择排序方法，在排序过程中，将arr[0…n-1]看成一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子结点之间的内在关系，在当前无序区中选择最大（或最小）的元素。
下标从0开始，节点i的两个孩子节点可表示为2*i+1、2*i+2。
2.排序算法
|
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
|
void AdjustDown(int *arr, int size, int parent){ int child = 2 * parent + 1; while (child < size) { if (child + 1 < size && arr[child] < arr[child + 1]) { child++; } if (arr[parent] < arr[child]) { swap(arr[parent], arr[child]); parent = child; child = 2 * parent + 1; } else break; }}void HeapSort(int *arr, int size){ if (arr == NULL) return; //1.建立初始堆（此处为大堆） int root; for (root = (size / 2)-1; root >= 0; root--) { AdjustDown(arr, size, root); } //2.将arr[0]与arr[n-1]交换，然后再调整arr[0...n-1]，使其满足大堆，如此反复操作 for (root = size-1; root >= 1; root--) { swap(arr[root], arr[0]); AdjustDown(arr, root, 0); }} |
3.算法分析
堆排序的时间主要由建堆和反复调整堆这两部分的时间构成，由于可以把堆看成完全二叉树的结构，所以堆排序的时间复杂度为O(N*lgN)，空间复杂度为O(1)，堆排序算法不稳定。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://blog.csdn.net/tttjp/article/details/76461108
