数据结构——排序2

今天，我们来讲解一下选择排序和冒泡排序还有堆排序。

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

下图中只选取了它的最小值，但是我们不妨将最大值和最小值都记录下来，因为最小值是放最左边。而最大值是放最右边，它们并不会相互影响的，所以我们接下来会把按照我说的做法来讲解。

它的基本思路如下：

由于我们接下来的排序当中，使用到的交换的函数非常的频繁，所以我们单独弄个函数

交换函数

void Swap(int* p1,int* p2)
{int x = *p1;*p1 = *p2;*p2 = x;
}

选择排序的代码：


void SelectSort(int* a, int n)
{int left=0, right=n-1;while (left < right){int min=left, max=left;for (int i = left+1; i < right; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[left], &a[min]);Swap(&a[right], &a[max]);left++;right--;}
}

这里需要注意的是

如果写出了上面的代码后，会发现一些小问题：如下

就是当left和max相互重叠后，你又交换了Swap(&a[left], &a[min]);

那么，我们想想，max的值是不是也发生变化了，但是我们上面没有随之改变，所以变成了max的下标位置的值变成了min的值了。因此出现了问题。所以我们得在交换后，还要改变max的下标的位置过去

void SelectSort(int* a, int n)
{int left=0, right=n-1;while (left < right){int min=left, max=left;for (int i = left+1; i < right; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[left], &a[min]);增加部分if (left == max){max = min;}Swap(&a[right], &a[max]);left++;right--;}
}

冒泡排序

对于冒泡排序，想必我们在学习c语言时，也有了解过了，因此，我们现在来简单了解了解。

下面给出它的动图：

它的基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

void BullbleSort(int* a, int n)
{for (int j = 0; j < n; j++){//单趟for (int i = 1; i < n-j; i++){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);}}}
}

解释：

第一个for循环你可以理解为趟数就是当数据量为n是你需要排序的趟数然后第一趟排序可以把数组中最大的放到最后

然后里面的放循环是什么，就是我现在这一趟对吧，我要我第一趟要把最大的数据放到最后，那我比较的次数应该是怎么样的？

那我把最大的放到最后了对吧，那我最后这个数据是不是不用访问了对不对，那我就比较的是前N减一个数据对吧？我比较的是前N减一个数据，那我这是我的第二趟，我把倒倒数第二大的放到倒数第二个位置是这样的。

那么这是我们之前写单独版本，现在我们来提升一下它的效率吧：

void BullbleSort(int* a, int n)
{for (int j = 0; j < n; j++){//单趟bool exchange = false;for (int i = 1; i < n-j; i++){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = true;}}if (exchange == false){break;}}
}

这里加一个布尔判断，如果它一开始就有序了，那么就不进循环，直接退出。

堆排序：

堆排序的话，我们在讲解堆时有讲解过，如果感兴趣，可以去了解一下：

数据结构——二叉树——堆（1）-CSDN博客

那么我们在这里就简单来讲解一下：

1.我们了解到，如果要升序的话，就要建大堆。

AdjustDown(int* a, int parent,int n)
{int child = parent * 2 + 1;while (child <n){if (child + 1 <n && a[child + 1] > a[child]){child ++;}if (a[child] > a[parent]){ Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//建堆for (int i =(n-1-1)/2 ; i>=0; i--){AdjustDown(a, i, n);}//排序int end = n - 1;while(end>0){Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;}
}