数据结构——排序（2）：选择排序+交换排序

一、选择排序

（1）直接选择排序

①思路

②过程图示

③代码实现

④代码解释

⑤优化

1.代码实现

2.过程图示

3.代码解释

4.注意

⑥直接选择排序的复杂度

（2）堆排序

①注意

②代码实现

二、交换排序

（1）冒泡排序

①思路

②过程图示

③代码实现

④代码解释

⑤复杂度

（2）快速排序

①思路

②主要框架

三、写在最后

一、选择排序

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

（1）直接选择排序

①思路

首先在元素集合中（i ~ n-1）选择出最大（或最小）的数据元素。若它不是这组元素中的最后一个（或第一个）元素，则将它与最后一个（或第一个）元素交换。然后在剩余的集合中（i ~ n-2 或 i+1 ~ n-1）重复上述步骤，直到集合中只剩下1个元素。

②过程图示

我们以数组{2，3，9，6，5}为例：

③代码实现

void SelectSort(int* arr, int n)
{for(int i = 0 ; i < n; i ++){//先假设第一个元素为最小int min = i;//找最小值for(int j = i ; j < n; j ++){if(arr[j] < arr[min]){min = j;}}}//将最小值与无序区间的第一个元素交换swap(&arr[i],&arr[min]);
}

④代码解释

第一个for循环用来遍历数组所有数据，第二个for循环用来遍历后面的无序区间，找出最小值后将其放在无序区间的第一个位置。然后缩小无序区间之后重复循环。

⑤优化

上述代码的实现相当于将每一个数据都与其后面的数据进行比较，是不是觉得复杂度不是很理想呢？如果能够同时将最大值和最小值都找到并分别放在该区间的第一个和最后一个位置，效率一定会变高！

1.代码实现

void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while(begin < end){int min = begin;int max = begin;for(int i = begin + 1; i <= end; i++){if(arr[i] < arr[min]){min = i;}if(arr[i] > arr[max]){max = i;}}//避免max和begin在同一个位置，begin和min交换之后，max变成了最小的数据if(max == begin){max = min;}//将begin和min的位置交换//将end和max的位置交换swap(&arr[begin], &arr[min]);swap(&arr[end], &arr[max]);begin++;end--;}
}

2.过程图示

我们以数组{5，3，9，6，2}为例：

3.代码解释

定义begin、end来确定无序区间的界限，在区间合法的情况下找到最小值和最大值，并分别将最小值和最大值与begin和end位置的数据进行交换。

4.注意

不能忽略max和begin在同一位置的情况，否则会出错！

下面我们以数组{9，3，1}为例：

首先请看错误情况：

最小值和最大值与begin和end位置的数据进行交换之后，end位置不是最大值的数据！这时，min和begin交换之后，max却成了最小值，这不符合我们之前的思路。

那么当max和begin在同一个位置时，我们应该让max的值等于min，这样交换之后end位置为最大值。

⑥直接选择排序的复杂度

直接选择排序的思路好理解，但是效率不是太高：时间复杂度：O(N^2)，空间复杂度：O(1)。

（2）堆排序

堆排序是利用堆积树这种数据结构所涉设计的一种排序算法，是选择排序的一种。

①注意

排升序建大堆，排降序建小堆。

②代码实现

我们在二叉树章节已经讲解，在此不再赘述，代码如下：

void HeapSort(int* a, int n)
{// a数组直接建堆 O(N)for (int i = (n-1-1)/2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

二、交换排序

思想：将序列中两个数据通过比较结果来对换位置。

特点：将数值大的元素向序列尾部移动，将数值小的元素向序列前部移动。

（1）冒泡排序

在C语言的学习过程中，我们已经接触了冒泡排序。之所以叫做冒泡排序，是因为每一个元素可以像一个小气泡一样，根据自身大小一点一点向数组一侧移动。

①思路

通过for循环遍历数组中的数据，将最大值放在最后面，完成排序。

②过程图示

③代码实现

void BubbleSort(int* arr, int n)
{int flag = 0;for(int i = 0; i < n; i ++){for(int j = 0; j < n - 1 - i; j ++){if(arr[j] > arr[j + 1]){flag = 1;swap(&arr[j], &arr[j + 1]);}}if(flag == 0){break;}}
}

④代码解释

外层for循环用来遍历数组的数据，内层循环用来比较相邻的数据的大小，将小数据放在大数据前面。内层循环每进行一次，将最大值放在j范围的最后。最终将每次范围内的最大值放在最后，完成排序。

⑤复杂度

冒泡排序的时间复杂度：O(N^2)，空间复杂度：O(1)。

（2）快速排序

①思路

任取待排序元素序列中的某元素作为基准值，按照该基准值将序列分割为两子序列，其中左序列中的元素均小于基准值，右序列中的元素均大于基准值，然后再将左右序列重复该过程，直到所有元素排序完成。

②主要框架

void QuickSort(int* arr, int left, int right)
{if(left >= right){return;}int key = _QuickSort(arr, left, right);QuickSort(arr, left, key -1);QuickSort(arr, key + 1, right);
}

首先得到基准值key，然后分别将左右子树进行相同的操作，直至left >= right。（递归）