选择排序直接选择排序 和 堆排序

目录

1. 排序的概念：

2.选择排序的基本思想

3.直接选择排序

4.堆排序

1. 排序的概念：

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的;否则称为不稳定。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2.选择排序的基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

3.直接选择排序

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

选择排序图解：这张动图是选择后面最小的数与前面做交换

当让我们还可以优化，如果是升序，每一次遍历分别选出最小的元素和最大的元素，分别与前面和后面数据做交换。

代码实现：

1.  
   //交换函数
2.  
   void Swap(int* p1, int* p2)
3.  
   {
4.  
   int t = *p1;
5.  
   *p1 = *p2;
6.  
   *p2 = t;
7.  
   }
8.  
    
9.  
   // 选择排序 升序
10.  
    void SelectSort(int* arr, int n)
11.  
    {
12.  
    int begin = 0;
13.  
    int end = n - 1;
14.  
    while (begin < end)
15.  
    {
16.  
    int maxi = begin;
17.  
    int mini = begin;
18.  
    for (int i = begin; i <= end; i )
19.  
    {
20.  
    if (arr[i] > arr[maxi])
21.  
    {
22.  
    maxi = i;
23.  
    }
24.  
    if (arr[i] < arr[mini])
25.  
    {
26.  
    mini = i;
27.  
    }
28.  
    }
29.  
    Swap(&arr[mini], &arr[begin]);
30.  
    if (begin == maxi)
31.  
    {
32.  
    maxi = mini;
33.  
    }
34.  
    Swap(&arr[maxi], &arr[end]);
35.  
    begin ;
36.  
    end--;
37.  
    }
38.  
    }

直接选择排序的特性总结:

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1)
4. 稳定性:不稳定

4.堆排序

我们这里需要先了解堆的结构，如果不了解可以看我之前的文章【数据结构】这堆是什么。

当我们了解完堆的结构后，我们就可以开始学习堆排序了。 

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的
种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

1. 首先要构建一个堆，
2. 然后让堆顶元素与最后一个元素交换，把最后一个位置元素当作不在堆内。
3. 然后通过向下调整法调整堆。循环就可以排序

图解：

 建堆可以使用向上调整法建堆和向下调整法建堆，这两种方法在【数据结构】这堆是什么 中有详细讲解。向上调整法建堆时间复杂度为O(N*logN)，但是向下调整法时间复杂度低，为O(N)。所以我们这里使用向下调整法建堆。

代码实现：

1.  
   //向下调整法
2.  
   void AdjustDown(int* arr, int n, int parent)
3.  
   {
4.  
   int child = parent * 2 1;
5.  
   while (child < n)
6.  
   {
7.  
   if (child 1 < n && arr[child 1] > arr[child])
8.  
   {
9.  
   child ;
10.  
    }
11.  
    if (arr[parent] < arr[child])
12.  
    {
13.  
    Swap(&arr[parent], &arr[child]);
14.  
    parent = child;
15.  
    child = parent * 2 1;
16.  
    }
17.  
    else
18.  
    {
19.  
    break;
20.  
    }
21.  
    }
22.  
    }
23.  
    //堆排序
24.  
    void HeapSort(int* arr, int n)
25.  
    {
26.  
    //建堆
27.  
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
28.  
    {
29.  
    AdjustDown(arr, n, i);
30.  
    }
31.  
    //排序
32.  
    int end = n - 1;
33.  
    while (end > 0)
34.  
    {
35.  
    Swap(&arr[end], &arr[0]);
36.  
    AdjustDown(arr, end, 0);
37.  
    end--;
38.  
    }
39.  
    }

堆排序的特性总结:

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(1)
4. 稳定性:不稳定

这篇好文章是转载于：学新通技术网