【数据结构与算法】：选择排序与快速排序

1.选择排序

选择排序是一种简单直观的比较排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最小（或最大）元素，然后将其放置到未排序序列的起始位置，这个过程一直重复直至整个数组被排序。

选择排序的具体步骤如下：

从数组的当前未排序部分选择最小（或最大）的一个元素

将这个最小（或最大）元素与未排序序列的第一个元素交换位置

然后从剩余未排序的元素中继续这个过程，将每一次找到的最小（或最大）元素放到未排序序列的开始

这个过程一直进行到整个数组的所有元素都被排为有序状态

在这里我们可以遍历一次同时找到最小元素和最大元素，对应放到相应的位置，

基本代码如下：

void SelectSort(int* a, int n)
{
  int begin = 0;
  int end = n - 1;
  while (begin < end)
  {
  int minn = begin;
  int maxn = begin;
  for (int i = begin + 1; i <= end; i++)
  {
    if (a[i] < a[minn])
    {
    minn = i;
    }
    if (a[i] > a[maxn])
    {
    maxn = i;
    }
  }
  Swap(&a[begin], &a[minn]);
  Swap(&a[end], &a[maxn]);
  begin++;
  end--;
  }
}

首先初始化两个索引begin和end，分别代表当前未排序序列的开始和结束位置

进入一个循环，条件是begin < end，确保在数组中还有未排序的元素

遍历一遍序列，找到最大元素和最小元素的下标

将最小元素与序列的始端交换，最大元素与序列的尾端交换

更新begin与end

Swap函数如下：

void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

思考一下，这里我是首先进行最小元素与首位置更换，再进行最大元素与末尾更换，那如果我的最大元素就在首位置呢？

我们进行解释：

6f71.png)

在这组数组

我们首先找到0的下标8

再找到9的下标0

下标8与begin（0）交换

下标0与end交换

这里由于最大元素9在起始位置，所以第一次交换后，9的索引不在是0，我们需要更新索引：

1. void SelectSort(int* a, int n)
2. {
3.  int begin = 0;
4.  int end = n - 1;
5.  while (begin < end)
6.  {
7.   int minn = begin;
8.   int maxn = begin;
9.   for (int i = begin + 1; i <= end; i++)
10.   {
11.     if (a[i] < a[minn])
12.     {
13.     minn = i;
14.     }
15. 
16.     if (a[i] > a[maxn])
17.     {
18.     maxn = i;
19.     }
20.   }
21.   Swap(&a[begin], &a[minn]);
22.   if (maxn == begin)
23.   {
24.     maxn = minn;
25.   }
26.   Swap(&a[end], &a[maxn]);
27.   begin++;
28.   end--;
29.   }
30. 
31. }
32. 
33. if (maxn == begin)
34.   {
35.     maxn = minn;
36.   }

改变最大值的索引，再进行交换，这就是选择排序的完整过程

1.1复杂度分析

时间复杂度

最好、平均、最坏情况下的时间复杂度都是 O(n^2)

原因在于，不管数组的初始顺序如何，选择排序都需要比较所有未排序的元素来找到最小（或最大）的元素，并执行这个过程 n-1 次（对于 n 个元素的数组）。每次选择操作需要比较的次数从 n-1 次减少到 1 次，总共的比较次数是 (n-1) + (n-2) + … + 1 = n(n-1)/2，这是一个二次函数，因此时间复杂度为 O(n2)

空间复杂度

选择排序是一种原地排序算法，除了输入数组外，它只需要有限的几个变量（比如，用于存储最小元素下标的变量和循环计数器）。因此，它的空间复杂度为常数空间，O(1)

其他特点

选择排序是不稳定的排序算法，因为它会因为选择最小（或最大）元素的过程中交换距离较远的元素，从而可能改变相同元素的原始顺序

2.快速排序的层层实现

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序是一种高效的排序算法，**采用了分治法（Divide and Conquer）**的策略。它的基本思路可以概括为以下几个步骤：

选择枢轴（Pivot）： 快速排序首先从数组中选择一个元素作为枢轴，枢轴的选择可以有多种方式，比如总是选择第一个元素、最后一个元素、中间的元素，或者采用更复杂的策略如三数中值法

分区（Partitioning）： 一旦枢轴被选择，数组会被重新排列，所有比枢轴小的元素移动到枢轴的左边，所有比枢轴大的元素移动到右边。这个过程结束时，枢轴元素处于其最终排序后的正确位置。

递归排序： 接下来，快速排序算法递归地将左边和右边的子数组进行排序。递归的基准条件是子数组的大小为0或1，这意味着它们已经被排序了

我们不妨举个例子

假设我们有以下数组：

[3, 6, 8, 10, 1, 2, 4]

我们将用快速排序来对这个数组进行排序。为了简单起见，我们选择数组的第一个元素作为枢轴。实际应用中可能会使用更复杂的选择方法，如随机选择或三数中值法，以避免最坏情况的性能下降。现在，让我们开始排序：

初始数组:

[3, 6, 8, 10, 1, 2, 4]

枢轴是 3。

分区操作:

将数组中小于3的元素移动到左边，大于3的元素移动到右边。这一步结束后，枢轴3位于其最终位置。

[2, 1, 3, 10, 8, 6, 4]

此时，3位于索引2，是其最终位置。

递归排序左边 [2, 1] 和右边 [10, 8, 6, 4] 的子数组。

对于左边的 [2, 1]，选择2作为枢轴。

分区操作后，得到 [1, 2]。

对于右边的 [10, 8, 6, 4]，选择10作为枢轴。

分区操作后，得到 [4, 8, 6, 10]。

现在，对 [4, 8, 6] 进行快速排序。

选择4作为枢轴。

分区操作后，得到 [4, 8, 6]。

最后，对 [8, 6] 进行快速排序。

选择8作为枢轴。

分区操作后，得到 [6, 8]。

合并所有排好序的部分，最终排序结果是：

[1, 2, 3, 4, 6, 8, 10]

每次分区操作都确保枢轴元素被放置在其最终位置。通过递归地处理枢轴左侧和右侧的子数组，最终整个数组变得有序

2.1分区操作

分区操作是快速排序算法中的核心步骤。它的目标是根据枢轴元素重新排列数组的部分区间，使得所有比枢轴小的元素都移到它的左边，而所有比枢轴大的元素都移到它的右边。在这个过程中，枢轴元素自身也找到了其在数组中的正确位置。这个步骤是递归进行排序的前提。下面详细解释这个过程：

设置指针：

设置两个指针，left指向数组的开始（或枢轴的下一个元素，取决于枢轴的选择），right指向数组的末尾。

指针移动和交换：

向右移动left指针：从left开始向右移动，直到找到一个大于或等于枢轴值的元素，向左移动right指针：从right开始向左移动，直到找到一个小于或等于枢轴值的元素

检查和交换：如果left指针仍在right指针的左侧（即left < right），则交换left和right指向的元素，并继续移动指针。

递归的终止条件：

当left指针超过right指针，即left >= right时，分区操作结束。此时，所有比枢轴小的元素都在它的左边，而所有比枢轴大的元素都在它的右边

单趟排序代码实现如下：

int left = begin;
int right = end;
int key = begin;
while (left < right)
{
  while (left < right && a[right] >= a[key])
  {
  right--;
  }
  while (left < right && a[left] <= a[key])
  {
  left++;
  }
  Swap(&a[right], &a[left]);
}
Swap(&a[left], &a[key]);
key = left;

初始化指针和枢轴：

left初始化为begin，这是当前考虑的数组段的起始位置

right初始化为end，这是当前考虑的数组段的结束位置

key用于记录枢轴的位置，这里选择的是数组段的第一个元素作为枢轴，因此key初始化为begin

分区过程：

外层循环：while (left < right)确保当左右指针相遇或交错时，循环停止。这意味着分区过程完成。

右侧扫描：第一个内层循环while (left < right && a[right] >= a[key])从右向左移动right指针，寻找第一个小于枢轴值a[key]的元素。

左侧扫描：第二个内层循环while (left < right && a[left] <= a[key])从左向右移动left指针，寻找第一个大于枢轴值a[key]的元素。

交换：Swap(&a[right], &a[left])交换左右指针所指向的元素。这次交换是为了把小于枢轴值的元素移动到枢轴的左侧，大于枢轴值的元素移动到枢轴的右侧

枢轴归位：

循环结束时，left和right指针相遇。此时，left指针的位置就是枢轴元素应该所在的最终位置。（这里下面再做解释）

Swap(&a[left], &a[key])交换枢轴元素与left指针所指的元素。这步确保了枢轴元素被放置在其正确的位置，即所有左侧元素都不大于它，所有右侧元素都不小于它

最后，将key更新为left，尽管在这个代码片段中，这个赋值操作对于后续流程并不是必需的，因为key的值在这之后没有再被使用。如果这是分区函数的一部分，key（或者这里应该是left）的新值可能会被用来指示下一步递归操作的分界点。

2.2相遇位置小于枢轴元素

这里我们就可以分多种情况进行讨论：

right遇到left：注意，代码中我们是先让right移动的，意味着left所指向的是上一此交换后小于枢轴元素的数，所以当相遇后，key与left交换，left指向的元素一定小于key指向的元素

left遇到right：由于right先动，意味着right已经找到了一个比key小的元素，当left遇到right使，此时right，left指向的元素一定小于key指向的元素。

2.3递归实现整个函数

一旦枢轴元素被放置在其正确位置上，数组就被分成了两部分。左边的子数组包含了所有小于枢轴的元素，而右边的子数组包含了所有大于枢轴的元素。这时，独立地对左右两个子数组应用同样的快速排序过程。这就是递归的步骤，因为同一个过程被用来排序较小的数组

递归终止条件：递归的终止条件是子数组的大小减到0或1，这时不需要做任何操作：

大小为0的子数组意味着在分区过程中，没有元素被划分到某一侧。例如，如果枢轴是最小（或最大）元素，并且所有其他元素都被划分到了枢轴的另一侧，那么这一侧实际上就没有元素，子数组的长度为0

大小为1的子数组意味着在分区过程结束后，某一侧只有一个元素。由于任何单一元素的集合自然是已排序的（因为没有其他元素可以与之比较大小），这意味着不需要对这样的子数组进行进一步的排序操作

代码实现如下：

1. void Quicksort(int* a, int begin, int end)
2. {
3. 
4.  if (begin >= end)
5.  {
6.   return;
7.  }
8.  int left = begin;
9.  int right = end;
10.   int key = begin;
11.   while (left < right)
12.   {
13.   while (left < right && a[right] >= a[key])
14.   {
15.     right--;
16.   }
17.   while (left < right && a[left] <= a[key])
18.   {
19.     left++;
20.   }
21.   Swap(&a[right], &a[left]);
22.   }
23.   Swap(&a[left], &a[key]);
24.   key = left;
25.   Quicksort(a, begin, key - 1);
26.   Quicksort(a, key + 1, end);
27. }

递归的终止条件：if (begin >= end)检查当前的子数组是否已经是不可分割的，即长度为0或1。如果满足这个条件，函数就会直接返回，不再继续执行后续的排序操作

初始化变量：变量left和right被初始化为子数组的起始和结束索引。变量key作为枢轴的索引也被初始化为begin，即子数组的第一个元素

2.4复杂度分析

每一层的时间复杂度：每一层的时间复杂度在快速排序中的推导基于对数组的分区操作。对于一个包含(n)个元素的数组，分区操作的时间复杂度是(O(n))。这是因为在分区过程中，每个元素都会被检查一次以确定它们是应该放在枢轴的左边还是右边。

最好情况、平均情况和最坏情况：

最好情况：当每次分区操作都能将数组均等分成两部分，快速排序的性能接近其理论最优。这种情况下，递归树的深度是 log n ，其中每一层的处理时间总和是( O(n) )）。因此，最好情况下的时间复杂度是( O(n log n) )。

平均情况：在随机选择的数组中，快速排序的平均时间复杂度也是( O(n \log n) )。虽然每次分区可能不会完全平等，但平均而言，递归树的深度依然保持在( \log n )的数量级，每一层的处理时间总和为( O(n) )

最坏情况：最坏情况发生在每次分区操作时，都将数组分成大小极度不平衡的两部分，如一个元素和其余元素，即在有序的情况下。这种情况下，递归树的深度增长到( n )，每次分区操作依然需要( O(n) )的时间，因此最坏情况下的时间复杂度是( O(n^2) )

空间复杂度：快速排序的空间复杂度主要由递归调用栈的深度决定。在最好情况下，递归树的深度是( log n )，因此空间复杂度是( O(log n) )。在最坏情况下，递归树的深度可以达到( n )，此时空间复杂度为( O(n) )。这是因为每一层递归调用都需要一定的空间，而递归树的深度直接影响调用栈的大小

2.5 代码优化：三数取中法选key

三数取中法是在实现快速排序时用来提高性能并降低遇到最坏情况概率的一种技术。该方法通过选择一个较为接近中值的枢轴元素来分区数组，以避免每次都产生不平衡的分区，从而增加算法的效率

在三数取中法中，我们通常取数组中以下三个值：

起始值（通常是数组的第一个元素）

结束值（通常是数组的最后一个元素）

中间值（数组中间位置的元素，可以通过(begin + end) / 2计算得出）

然后，比较这三个元素的大小，并选择处于中间大小的元素作为枢轴元素。这样做的目的是尽量避免选择最小或最大的元素作为枢轴，因为这会产生不平衡的分区。这个选取枢轴的过程实际上是一个非常简单的大小比较和交换操作

三数取中法选取key的具体实现可能如下：

1. int Getmidi(int* a, int begin, int end)
2. {
3.  int midi = (begin + end) / 2;
4.  if (a[begin] < a[midi])
5.  {
6.   if (a[midi] < a[end])
7.    return midi;
8.   else if (a[begin] > a[end])
9.    return begin;
10.   else
11.     return end;
12.   }
13.   else
14.   {
15.   if (a[midi] > a[end])
16.     return midi;
17.   else if (a[end] < a[begin])
18.     return end;
19.   else
20.     return begin;
21.   }
22. }
23. void Quicksort(int* a, int begin,int end)
24. {
25. 
26.   if (begin >= end)
27.   {
28.   return;
29.   }
30.   int midi = Getmidi(a, begin, end);
31.   Swap(&a[midi], &a[begin]);
32.   int left = begin;
33.   int right = end;
34.   int key = begin;
35.   while (left < right)
36.   {
37.   while (left=a[key])
38.   {
39.     right--;
40.   }
41.   while (left < right && a[left] <= a[key])
42.   {
43.     left++;
44.   }
45.   Swap(&a[right], &a[left]);
46.   }
47.   Swap(&a[left], &a[key]);
48.   key = left;
49.   Quicksort(a, begin, key - 1);
50.   Quicksort(a, key+1, end);
51. }

函数Getmidi尝试从数组的begin、end和midi（中间）位置选取一个"中间值"（不是数值上的中位数，而是在三个数中大小排在中间的数）。然后，Quicksort1函数利用三数取中的方法来选择枢轴元素(key)并执行快速排序过程。

Getmidi 函数详解：

Getmidi函数通过比较三个位置（起始位置、中间位置和结束位置）的元素大小来返回中间值的索引。这里的中间值是指这三个元素中不是最大也不是最小的那个。判断条件覆盖了所有可能的大小顺序，来确保正确选取中间值。

Quicksort1 函数详解：

Quicksort1首先检查递归调用的终止条件if (begin >= end)。当当前子数组长度为0或1时，函数返回

接下来，函数调用Getmidi来获取中间值的索引并将该位置的元素与起始位置的元素交换，这样枢轴（pivot）选取就是三数取中法选出的元素

left和right分别初始化为子数组的起始和结束索引，此时始终将begin位置的元素视为枢轴元素

剩余部分执行的是典型的快速排序分区操作，此时key是枢轴索引，最后将枢轴位置的元素放到正确位置上

在分区完成后，枢轴左侧和右侧的子数组通过递归调用Quicksort1函数来进行排序

在进行这些更改后，Quicksort1函数应该能够正确地使用三数取中法对数组进行排序，通常能够避免最坏情况的(O(n^2))时间复杂度，同时保持期望的平均时间复杂度(O(n log n))

2.6挖坑法实现快排

挖坑法是实现快速排序的一种方法，它简化了元素交换的步骤，通过"挖坑填数"来完成元素的位置调整。这个方法的基本思想是选定一个枢轴值（pivot），然后将小于枢轴值的元素移动到枢轴的左边，将大于枢轴值的元素移动到枢轴的右边，最终将枢轴值放入正确的位置。下面是使用挖坑法实现快速排序的示例代码：

1. void QuickSortHole(int* arr, int begin, int end) {
2.  if (begin >= end) {
3.   return; // 递归结束条件
4.  }
5. 
6.  int key = arr[begin]; // 选取第一个元素作为枢轴
7.  int left = begin;
8.  int right = end;
9. 
10.   while (left < right) {
11.   // 从右向左找到第一个小于枢轴的元素，填入左边的坑
12.   while (left < right && arr[right] >= key) {
13.     right--;
14.   }
15.   arr[left] = arr[right]; // 将找到的较小元素填到左边的坑里，此时右边形成一个新的坑
16. 
17.   while (left < right && arr[left] <= key) {
18.     left++;
19.   }
20.   arr[right] = arr[left]; 
21.   }
22. 
23. 
24.   arr[left] = key;
25.   QuickSortHole(arr, begin, left - 1);
26.   QuickSortHole(arr, left + 1, end);
27. }

先将第一个数据存放在临时变量key中形成一个坑位

让我们通过一个具体的例子来解释挖坑法如何在快速排序中工作。假设我们有以下数组：

[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]

我们要对这个数组进行快速排序。选择第一个元素作为枢轴值（pivot），这里是6。我们现在开始挖坑法的过程：

初始化：枢轴值为6，因此数组的第一个位置成了一个“坑”，我们用这个“坑”来存放接下来找到的符合条件的元素。此时数组状态和指针位置如下：

[6*, 1, 2, 7, 9, 3, 4, 5, 10, 8]  // *表示坑位
left                            right

从右向左扫描：找到第一个小于6的元素，这里是5。我们将5放入左边的“坑”中，并将5的位置变成新的“坑”。数组现在看起来是这样：

[5, 1, 2, 7, 9, 3, 4, 6*, 10, 8]  // 将5移动到左边的坑位，6的位置成为新的坑位
     left                     right

从左向右扫描：找到第一个大于6的元素，这里是7。我们将7放入右边的“坑”中，并将7的位置变成新的“坑”。数组更新为：

[5, 1, 2, 6*, 9, 3, 4, 7, 10, 8]  // 将7移动到右边的坑位，6的位置再次成为新的坑位
        left              right

重复这个过程，直到left和right指针相遇。在这个例子中，当两个指针相遇时，我们发现它们都指向了索引3的位置（现在是一个“坑”），这个位置正是枢轴值6最终应该放置的位置。所以，我们把枢轴值放回这个“坑”里。数组现在是：

[5, 1, 2, 6, 9, 3, 4, 7, 10, 8]

1

此时，枢轴值6已经放到了它最终的位置上，所有在它左边的元素都比它小，所有在它右边的元素都比它大。现在，我们对6左边和右边的子数组递归执行相同的排序过程。

这种方法减少了元素的直接交换，通过移动“坑”位置来调整元素的位置

当然我们也可以继续使用三数取中法选key对代码再次优化：

1. void QuickSortHole(int* arr, int begin, int end) {
2.  if (begin >= end) {
3.   return;
4.  }
5.  int midi = Getmidi(arr, begin, end);
6.  Swap(&arr[midi], &arr[begin]);
7. 
8.  int key = arr[begin]; 
9.  int left = begin;
10.   int right = end;
11. 
12.   while (left < right) {
13.   while (left < right && arr[right] >= key) {
14.     right--;
15.   }
16.   arr[left] = arr[right];
17. 
18.   while (left < right && arr[left] <= key) {
19.     left++;
20.   }
21.   arr[right] = arr[left];
22.   }
23. 
24.   arr[left] = key; 
25.   QuickSortHole(arr, begin, left - 1);
26.   QuickSortHole(arr, left + 1, end);
27. }

2.7前后指针实现快排

void QuickSort3(int* arr, int begin, int end) {
  if (begin >= end) {
    return;
  }
  int keyi = Getmidi(arr, begin, end);  
  Swap(&arr[keyi], &arr[begin]);
  int key = arr[begin];  
  int cur = begin + 1;     
  int pre = begin;        
  for (; cur <= end; ++cur) {
    if (arr[cur] < key) {
    ++pre;  
    Swap(&arr[pre], &arr[cur]);
    }
  }
  Swap(&arr[begin], &arr[pre]);
  QuickSort3(arr, begin, pre - 1);
  QuickSort3(arr, pre + 1, end);
}

设置指针

设置两个指针cur（当前指针）和pre（前指针）。cur从枢轴元素的下一个位置开始，即begin + 1，而pre从枢轴元素的位置开始，即begin。这样设置是为了准备遍历数组进行分区。

遍历与交换

遍历数组从cur到end的所有元素。对于每个元素，比较其与枢轴元素的大小：

如果当前cur指向的元素小于枢轴元素，则表示这个元素应该位于枢轴的左侧。

为了将其移动到正确位置，首先将pre指针向右移动一个位置（即++pre），然后交换pre和cur指向的元素的位置。这一步确保了pre左侧的所有元素（包括pre指向的元素）都不大于枢轴元素。

枢轴归位

遍历结束后，pre指向的是最后一个小于枢轴的元素的位置。由于初始时枢轴元素被置于数组的起始位置（即begin），现在需要将枢轴元素与pre指向的元素进行交换。

这样做的结果是，枢轴元素被放置到了其最终的正确位置上。至此，枢轴元素的左侧都是不大于它的元素，右侧都是不小于它的元素。

让我们通过一个具体的例子来演示快速排序的分区过程，假设我们有以下数组：

arr = [3, 6, 8, 10, 1, 2, 1]

1

我们选择数组的第一个元素作为枢轴（pivot），即3。

枢轴选择

这一步已经完成，枢轴3已经在数组的起始位置。

设置指针

设置两个指针cur和pre。初始时，cur = begin + 1 = 1，pre = begin = 0。

遍历与交换

我们开始遍历数组，从索引1到数组的结束，比较每个元素与枢轴3的大小。

cur = 1, arr[cur] = 6，因为6 > 3，pre和cur都不动。

cur = 2, arr[cur] = 8，因为8 > 3，pre和cur都不动。

cur = 3, arr[cur] = 10，同样，10 > 3，pre和cur都不动。

cur = 4, arr[cur] = 1，因为1 < 3，此时pre向右移动一位变为1，然后交换arr[pre]和arr[cur]，即6和1交换位置。现在数组变为[3, 1, 8, 10, 6, 2, 1]。

cur = 5, arr[cur] = 2，因为2 < 3，pre再次向右移动一位变为2，然后交换arr[pre]和arr[cur]，即8和2交换。数组变为[3, 1, 2, 10, 6, 8, 1]。

cur = 6, arr[cur] = 1，同样，1 < 3，pre移动到3，然后10和1交换。数组现在看起来是[3, 1, 2, 1, 6, 8, 10]。

枢轴归位

遍历完成后，pre = 3，指向最后一个小于3的元素。现在，我们将枢轴元素3与pre所在位置的元素1交换。交换后的数组是[1, 1, 2, 3, 6, 8, 10]。

递归分区

现在，枢轴3已经处于其正确的位置，我们对枢轴左侧的[1, 1, 2]和右侧的[6, 8, 10]分别递归执行上述步骤，直到子数组长度为1或者为空，这意味着整个数组已经排序完成。

本节内容到此结束，感谢大家阅读！！！