减治法插入排序c++
时间: 2023-06-29 15:04:55 浏览: 73
下面是使用减治法实现的插入排序的 C++ 代码:
```c++
#include <iostream>
using namespace std;
void insertSort(int arr[], int n) {
// i 表示待排序元素的下标,j 表示已排序元素的下标
for (int i = 1; i < n; i++) {
int temp = arr[i], j = i - 1;
while (j >= 0 && arr[j] > temp) { // 需要移动元素
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp; // 将待排序元素插入到正确的位置
}
}
int main() {
int arr[] = { 5, 2, 4, 6, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
insertSort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
其中,insertSort 函数使用了减治法的思想,将待排序的序列分为已排序和未排序两部分,每次从未排序中取出一个元素,与已排序中的元素比较,找到其正确的位置插入,直到所有元素都被插入到已排序序列中。
相关问题
c减治法实现插入排序伪代码
C减治法是一种优化的插入排序算法,它通过减少比较次数来提高排序效率。下面是C减治法实现插入排序的伪代码:
```
void cInsertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 在已排序的部分中找到合适的位置插入元素
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 将元素插入到正确的位置
arr[j + 1] = key;
}
}
```
排序中减治法的程序设计
减治法是一种常见的排序算法,其基本思想是从待排序的序列中找到一个关键字,然后将序列分成两部分,一部分小于等于关键字,一部分大于关键字,然后对两部分分别进行递归排序,最终合并两个有序序列即可。以下是使用减治法实现排序的程序设计过程:
1. 定义一个函数,传入待排序的数组和左右端点(即数组的起始下标和结束下标)。
2. 如果左右端点相等(即数组长度为1),则无需排序,直接返回。
3. 取数组的中间位置作为关键字,将数组分为左右两部分。
4. 递归调用函数对左右两部分进行排序(即传入左右端点对应的下标)。
5. 合并左右两部分已排序的结果,即将两个有序序列按大小顺序合并成一个有序序列。
6. 返回合并后的有序序列作为结果。
下面是使用减治法实现排序的代码示例(使用C++语言):
```
void mergeSort(int arr[], int left, int right) {
if (left >= right) return; // 如果左右端点相等,无需排序
int mid = (left + right) / 2; // 取数组中间位置作为关键字
mergeSort(arr, left, mid); // 递归调用函数对左半部分进行排序
mergeSort(arr, mid + 1, right); // 递归调用函数对右半部分进行排序
// 合并已排序的左右两部分
int i = left, j = mid + 1;
vector<int> temp; // 定义一个临时数组,用于存放合并后的结果
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push_back(arr[i]);
i++;
} else {
temp.push_back(arr[j]);
j++;
}
}
while (i <= mid) {
temp.push_back(arr[i]);
i++;
}
while (j <= right) {
temp.push_back(arr[j]);
j++;
}
// 将合并后的结果复制回原数组
for (int k = left; k <= right; k++) {
arr[k] = temp[k - left];
}
}
```
注意:以上代码仅为示例,实际使用时还需考虑边界情况和性能优化等问题。