[排序算法] 选择排序（2种）

1.直接选择排序

【思想】选出剩下的未排序数据中的最小元素与第i个元素交换

【特点】不稳定

空间代价：O(1)

时间代价：O(n^2)

 1 void SelectSort(int Array[], int n)
 2 {
 3     // 依次选出第i小的记录，即剩余记录中最小的那个
 4     for (int i=0; i< n - 1; i ++)
 5     {
 6         // 首先假设记录i就是最小的
 7         int Min = i;
 8         // 开始向后扫描所有剩余记录
 9         for (int j = i + 1; j < n; j++)
10             // 如果发现更小的记录，记录它的位置
11             if (Array[j] < Array[Min])
12                 Min = j;
13         //将第i小的记录放在数组中第i个位置
14         swap(Array[i], Array[Min]);
15     }
16 }

2.堆排序

【思想】基于最大推来实现，效率更高。堆排序的基本思想是：首先将n个记录按关键码建成堆（初始堆），将堆顶元素与最后一个元素交换，然后将剩余的元素调整成堆...如此反复，便得到了一个按关键码有序的序列。

可参考我整理的最大堆的类实现http://www.cnblogs.com/lca1826/p/6590864.html

【特点】不稳定

空间代价：O(1)

时间代价：O(nlogn)

 1 /*
 2 堆排序
 3 (1)用大根堆排序的基本思想
 4  ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
 5  ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，
 6     由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
 7  ③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。
 8     然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，
 9     由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n- 2].keys≤R[n-1..n].keys，
10     同样要将R[1..n-2]调整为堆。
11     ……
12     直到无序区只有一个元素为止。
13 
14 (2)大根堆排序算法的基本操作：
15  ① 初始化操作：将R[1..n]构造为初始堆；
16  ② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
17 
18  注意：
19  ①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
20  ②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。
21    堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，
22    且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
23 */
24 #include <iostream>
25 using namespace std;
26 
27 void HeapAdjust(int SortData[],int StartIndex, int Length)
28 {
29     int MaxChildIndex = 2*StartIndex + 1;
30     while(MaxChildIndex < Length)
31     {
32         //比较左子树和右子树，记录最大值的j
33         if((MaxChildIndex < Length - 1) && (SortData[MaxChildIndex] < SortData[MaxChildIndex + 1])){
34             MaxChildIndex ++;
35         }
36         if(SortData[StartIndex] < SortData[MaxChildIndex])
37         {
38             //交换i与j位置的数据
39             int temp = SortData[StartIndex];
40             SortData[StartIndex] = SortData[MaxChildIndex];
41             SortData[MaxChildIndex] = temp;
42             //堆被破坏，重新调整
43             StartIndex = MaxChildIndex;
　　　　　　　　　MaxChildIndex = 2*StartIndex + 1;
44         }
45         else break;
46     }
47     return;
48 }
49 
50 //堆排序
51 void HeapSortData(int SortData[], int Length)
52 {
53     int i=0;
54 
55     //将SortData[0,Lenght-1]建成大根堆
56     for (i=Length/2-1; i>=0; i--)
57     {
58         HeapAdjust(SortData, i, Length);
59     }
60 
61     for (i=Length-1; i>0; i--)
62     {
63         //与最后一个记录交换
64         int tmpData =SortData[0];
65         SortData[0] =SortData[i];
66         SortData[i] =tmpData;
67         //将SortData[0..i-1]重新调整为大根堆
68         HeapAdjust(SortData, 0, i);
69     }
70     return;
71 }
72 
73 int main()
74 {
75     int array[6] = {10, 15, 56, 25, 30, 70};
76     HeapSortData(array, 6);
77     for (int index = 0; index != 6; ++index)
78     {
79         cout<<array[index]<<" ";
80     }
81     cout<<endl;
82     return 0;
83 }