插入排序和带哨兵的插入排序有什么区别?
时间: 2023-12-03 07:40:06 浏览: 40
插入排序和带哨兵的插入排序的区别在于是否使用哨兵位。哨兵位是指在待排序序列的第一个位置留出来设立为哨兵位置,这样做的好处是不用设立临时变量。在插入排序中,每次插入一个元素时,需要将该元素与已排序序列中的元素逐一比较,找到插入位置后再进行插入。而在带哨兵的插入排序中,待排序的值放到哨兵位即arr,然后从待排序值的下标开始向前遍历已排序序列,找到插入位置后再进行插入。这样做的好处是可以减少比较次数和交换次数,提高排序效率。
以下是两种排序算法的代码实现:
1.插入排序
```c
void InsertionSort(int arr[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
temp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
```
2.带哨兵的插入排序
```c
void InsertionSortWithSentinel(int arr[], int n) {
int i, j;
for (i = 2; i <= n; i++) {
arr[0] = arr[i];
j = i - 1;
while (arr[0] < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = arr[0];
}
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)