c++插入排序的递归实现代码
时间: 2023-11-20 10:52:21 浏览: 65
以下是C++插入排序的递归实现代码:
```
void insertionSortRecursive(int arr[], int n)
{
// Base case
if (n <= 1)
return;
// Sort first n-1 elements
insertionSortRecursive( arr, n-1 );
// Insert last element at its correct position
// in sorted array.
int last = arr[n-1];
int j = n-2;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
}
```
相关问题
c++插入排序的递归实现和非递归实现
插入排序是一种简单直观的排序算法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增加1的有序表。C++中插入排序可以通过递归和非递归两种方式实现。
递归实现插入排序的基本思路是:将待排序序列分为已排序和未排序两部分,每次从未排序的部分中取出一个元素,插入到已排序的部分中,直到未排序部分为空。具体实现过程如下:
1. 递归函数的参数为待排序数组和数组长度。
2. 如果数组长度为1,则返回。
3. 递归调用函数对前n-1个元素进行排序。
4. 将第n个元素插入到已排序的前n-1个元素中,使得前n个元素有序。
非递归实现插入排序的基本思路是:将待排序序列分为已排序和未排序两部分,每次从未排序的部分中取出一个元素,插入到已排序的部分中,直到未排序部分为空。具体实现过程如下:
1. 遍历待排序数组,从第二个元素开始,将其插入到已排序的部分中。
2. 对于第i个元素,从i-1开始向前遍历已排序的部分,找到第一个比它小的元素,将它插入到该元素后面。
需要注意的是,插入排序是一种稳定排序算法,即相同元素的相对位置不会改变。
插入排序的递归实现C++
void insertSortRecursion(int arr[], int n){
if(n<=1){
return;
}
insertSortRecursion(arr,n-1);
int last=arr[n-1];
int j=n-2;
while(j>=0 && arr[j]>last){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=last;
}