void InsertSort(int left, int right) {
时间: 2023-12-29 16:03:50 浏览: 24
这是一个插入排序的函数,它可以对一个数组中的元素进行排序。left和right分别表示数组的左右边界。
函数的具体实现如下:
1. 从left+1开始遍历数组,依次将元素插入到前面已经排好序的序列中。
2. 对于每一个待插入的元素,将它与前面的元素进行比较,直到找到一个位置,使得它前面的元素都比它小,后面的元素都比它大。
3. 将该元素插入到该位置,然后继续遍历下一个待插入的元素,直到遍历完整个数组。
函数的代码如下:
```
void InsertSort(int left, int right) {
for(int i=left+1; i<=right; i++) {
int j = i-1;
int temp = a[i];
while(j>=left && a[j]>temp) {
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}
```
其中,a是待排序的数组。
相关问题
将第二段代码和第三段代码和第一段代码函数格式相统一//冒泡排序 void maopaoSort(int nums[], int n) { int size = n; for (int i = 1; i < size; i++) { bool flag = true; for (int j = 0; j < size - i; j++) { if (nums[j] > nums[j + 1]) { swap(nums[j], nums[j + 1]); flag = false; } } if (flag) { break; } } } void quickSort(int nums[], int left, int right) { if (left >= right) return; // 只有一个元素或者没有元素,直接返回 if (right - left + 1 < 10) { // 数组长度小于 10,使用插入排序 insertSort(nums, left, right); return ;0 } int pivot = nums[left]; // 选取最左边的元素作为基准值 int i = left, j = right; while (i < j) { while (i < j && nums[j] >= pivot) j--; nums[i] = nums[j]; while (i < j && nums[i] <= pivot) i++; nums[j] = nums[i]; } nums[i] = pivot; // 基准值归位 quickSort(nums, left, i - 1); // 递归排序左边部分 quickSort(nums, i + 1, right); // 递归排序右边部分 } void xuanzeSort(int nums[],int n) { int n = nums.size(); for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (nums[j] < nums[minIndex]) { minIndex = j; } } if (minIndex != i) { swap(nums[i], nums[minIndex]); } } }
可以将第二段和第三段代码的函数格式与第一段代码相统一,修改后的代码如下:
```
// 冒泡排序
void maopaoSort(int nums[], int n) {
int size = n;
for (int i = 1; i < size; i++) {
bool flag = true;
for (int j = 0; j < size - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
flag = false;
}
}
if (flag) {
break;
}
}
}
// 快速排序
void quickSort(int nums[], int left, int right) {
if (left >= right) {
return;
}
// 只有一个元素或者没有元素,直接返回
if (right - left + 1 < 10) {
// 数组长度小于 10,使用插入排序
insertSort(nums, left, right);
return;
}
int pivot = nums[left]; // 选取最左边的元素作为基准值
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= pivot) {
j--;
}
nums[i] = nums[j];
while (i < j && nums[i] <= pivot) {
i++;
}
nums[j] = nums[i];
}
nums[i] = pivot; // 基准值归位
quickSort(nums, left, i - 1); // 递归排序左边部分
quickSort(nums, i + 1, right); // 递归排序右边部分
}
// 选择排序
void xuanzeSort(int nums[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(nums[i], nums[minIndex]);
}
}
}
```
优化这段代码void kuaisuSort(int nums[],int n) { if (left >= right) return; // 只有一个元素或者没有元素,直接返回 int pivot = nums[left]; // 选取最左边的元素作为基准值 int i = left, j = right; while (i < j) { while (i < j && nums[j] >= pivot) j--; nums[i] = nums[j]; while (i < j && nums[i] <= pivot) i++; nums[j] = nums[i]; } nums[i] = pivot; // 基准值归位 kuaisuSort(nums, left, i - 1); // 递归排序左边部分 kuaisuSort(nums, i + 1, right); // 递归排序右边部分 }
这段代码实现的是快速排序算法,其中存在一些问题。首先,在函数定义中只有两个参数,而函数内部却使用了三个参数,因此需要修改函数定义。其次,在递归调用快速排序时,传递的参数不正确,应该是 left 和 i-1 以及 i+1 和 right,而不是 left 和 right。最后,虽然快速排序是一种高效的排序算法,但是在数组长度较小时,其效率不如插入排序等其他排序算法,因此可以增加一个判断条件,在数组长度小于某个值时使用其他排序算法。
修改后的代码如下:
```
void quickSort(int nums[], int left, int right) {
if (left >= right) return; // 只有一个元素或者没有元素,直接返回
if (right - left + 1 < 10) { // 数组长度小于 10,使用插入排序
insertSort(nums, left, right);
return;
}
int pivot = nums[left]; // 选取最左边的元素作为基准值
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= pivot) j--;
nums[i] = nums[j];
while (i < j && nums[i] <= pivot) i++;
nums[j] = nums[i];
}
nums[i] = pivot; // 基准值归位
quickSort(nums, left, i - 1); // 递归排序左边部分
quickSort(nums, i + 1, right); // 递归排序右边部分
}
```